Problem:


Score : 400 points

Problem Statement

Given is a rooted tree with N vertices numbered 1 to N.
The root is Vertex 1, and the i-th edge (1 \leq i \leq N - 1) connects Vertex a_i and b_i.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0.

Now, the following Q operations will be performed:

Operation j (1 \leq j \leq Q): Increment by x_j the counter on every vertex contained in the subtree rooted at Vertex p_j.

Find the value of the counter on each vertex after all operations.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq Q \leq 2 \times 10^5

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

Sample Input 1

4 3
1 2
2 3
2 4
2 10
1 100
3 1

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:

Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.

Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.

Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Sample Input 2

6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10

Sample Output 2

20 20 20 20 20 20



Sample input:
4 3
1 2
2 3
2 4
2 10
1 100
3 1


Sample output:
100 110 111 110

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
        
N,Q = (int(i) for i in input().split())
A = [() for i in range(N)]

for _ in range(N-1):
    a,b = (int(i) for i in input().split())
    A[a-1] += (b-1,)
    A[b-1] += (a-1,)

cnt = [0]*N   
for q in range(Q):
   p,x = (int(i) for i in input().split())
   cnt[p-1] += x

st = deque([(0,-1)])
while st:
    n,par = st.popleft()
    val = cnt[n]   
    for node in A[n]:
        if node == par:
            continue
        else:
            cnt[node] += val
            st.append([node,n])

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    st = deque([(0,-1)])
    while st:
        n,par = st.popleft()
        val = cnt[n]   
        for node in A[n]:
            if node == par:
                continue
            else:
                cnt[node] += val
                st.append([node,n])
    return cnt

        
N,Q = (int(i) for i in input().split())
A = [() for i in range(N)]

for _ in range(N-1):
    a,b = (int(i) for i in input().split())
    A[a-1] += (b-1,)
    A[b-1] += (a-1,)

cnt = [0]*N   
for q in range(Q):
   p,x = (int(i) for i in input().split())
   cnt[p-1] += x

bfs()

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def bfs(count,adj):
    st = deque([(0,-1)])
    while st:
        n,par = st.popleft()
        val = count[n]   
        for node in adj[n]:
            if node == par:
                continue
            else:
                count[node] += val
                st.append([node,n])
    return count

        
N,Q = (int(i) for i in input().split())
A = [() for i in range(N)]

for _ in range(N-1):
    a,b = (int(i) for i in input().split())
    A[a-1] += (b-1,)
    A[b-1] += (a-1,)

cnt = [0]*N   
for q in range(Q):
   p,x = (int(i) for i in input().split())
   cnt[p-1] += x

cnt = bfs(cnt,A)

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q = map(int,input().split())
tree = {}
px = []
counter = [0 for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = [b]
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = [a]
for _ in range(Q):
    ip,ix = map(int,input().split())
    px.append([ip,ix])


oya = deque([1])

while oya:
    oyai = oya.popleft()
    for ko in tree[oyai]:
        tree[ko].remove(oyai)
        oya.append(ko)


for pi,xi in px:
    oya = deque([pi])
    
    while oya:
        oyai = oya.popleft()
        counter[oyai-1] +=xi
        for ko in tree[oyai]:
            oya.append(ko)  
[print(i,end=" ") for i in counter]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def bfs(count,adj):
    st = deque([(0,-1)])
    while st:
        n,par = st.popleft()
        val = count[n]   
        for node in adj[n]:
            if node == par:
                continue
            else:
                count[node] += val
                st.append([node,n])
    return count

        
N,Q = map(int, input().split())
A = [() for i in range(N)]

for _ in range(N-1):
    a,b = map(int, input().split())
    A[a-1] += (b-1,)
    A[b-1] += (a-1,)

cnt = [0]*N   
for q in range(Q):
   p,x = map(int, input().split())
   cnt[p-1] += x

cnt = bfs(cnt,A)

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(count,adj):
    st = deque([(0,-1)])
    while st:
        n,par = st.popleft()
        val = count[n]   
        for node in adj[n]:
            if node == par:
                continue
            else:
                count[node] += val
                st.append([node,n])
    return count

        
N,Q = map(int, input().split())
A = [[] for i in range(N)]

for _ in range(N-1):
    a,b = map(int, input().split())
    A[a-1].append(b-1)
    A[b-1].append(a-1)

cnt = [0]*N   
for q in range(Q):
   p,x = map(int, input().split())
   cnt[p-1] += x

cnt = bfs(cnt,A)

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(count,adj):
    st = deque([(0,-1)])
    while st:
        n,par = st.popleft()
        val = count[n]   
        for node in adj[n]:
            if node == par:
                continue
            else:
                count[node] += val
                st.append([node,n])
    return count

        
N,Q = map(int, input().split())
A = [() for i in range(N)]

for _ in range(N-1):
    a,b = map(int, input().split())
    A[a-1] += (b-1,)
    A[b-1] += (a-1,)

cnt = [0]*N   
for q in range(Q):
   p,x = map(int, input().split())
   cnt[p-1] += x

cnt = bfs(cnt,A)

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
from collections import deque
N,Q = map(int,input().split())
tree = {}
px = []
counter = [0 for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = [b]
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = [a]
for _ in range(Q):
    ip,ix = map(int,input().split())
    px.append([ip,ix])


oya = deque([1])

while oya:
    oyai = oya.popleft()
    for ko in tree[oyai]:
        tree[ko].remove(oyai)
        oya.append(ko)


for pi,xi in px:
    oya = deque([pi])
    
    while oya:
        oyai = oya.popleft()
        counter[oyai-1] +=xi
        for ko in tree[oyai]:
            oya.append(ko)  
print(' '.join(map(str,counter)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N,Q = map(int,input().split())
tree = {}
px = []
counter = [0 for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    if a in tree:
        tree[a] |= {b}
    else:
        tree[a] = {b}
    if b in tree:
        tree[b] |= {a}
    else:
        tree[b] = {a}
for _ in range(Q):
    ip,ix = map(int,input().split())
    px.append([ip,ix])


oya = [1]

while oya:
    oyai = oya.pop(0)
    for ko in tree[oyai]:
        tree[ko].remove(oyai)
        oya.append(ko)


for pi,xi in px:
    oya = [pi]
    
    while oya:
        oyai = oya.pop(0)
        counter[oyai-1] +=xi
        for ko in tree[oyai]:
            oya.append(ko)  
print(' '.join(map(str,counter)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(count,adj):
    check = [0]*N
    st = deque()
    push,pop = st.append, st.pop
    push(0)
    check[0] = 1
    while st:
        n = []
        while st:
            n.append(pop())
        for ni in n:
            for i in adj[ni]:
                #print(ni,i,count)
                if check[i] == 0:
                    count[i] += count[ni]
                    check[i] = 1
                    push(i)
    return count

        
N,Q = map(int, input().split())
A = [() for i in range(N)]

for _ in range(N-1):
    a,b = map(int, input().split())
    A[a-1] += (b-1,)
    A[b-1] += (a-1,)

cnt = [0]*N   
for q in range(Q):
   p,x = map(int, input().split())
   cnt[p-1] += x

cnt = bfs(cnt,A)

for n in range(N):
    print(cnt[n], end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(count,adj):
    check = [0]*N
    st = deque()
    sts = deque()
    push,pop = st.append, st.pop
    pushs,pops = sts.append, sts.pop
    push(0)
    check[0] = 1
    while st:
        n = []
        while st:
            n.append(pop())
        for ni in n:
            for i in adj[ni]:
                #print(ni,i,count)
                if check[i] == 0:
                    count[i] += count[ni]
                    check[i] = 1
                    pushs(i)
        while sts:
            push(pops())
    return count

        
N,Q = map(int, input().split())
A = [() for i in range(N)]

for _ in range(N-1):
    a,b = map(int, input().split())
    A[a-1] += (b-1,)
    A[b-1] += (a-1,)
       
cnt = [0]*N   
for q in range(Q):
   p,x = map(int, input().split())
   cnt[p-1] += x

cnt = bfs(cnt,A)

for n in range(N):
    print(cnt[n], end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = lambda: sys.stdin.readline()[:-1]
n,q=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
px=[tuple(map(int,input().split())) for i in range(q)]
# ab.sort(key=lambda tup:(tup[0],tup[1]))
visited=[0]*(n+1)
cnt=[0]*(n+1)
data=[[] for i in range(n+1)]

for i in ab:
	data[i[0]].append(i[1])
	data[i[1]].append(i[0])
for j in px:
	cnt[j[0]]+=j[1]
	# print(cnt)
# count=0
def plus(now,value,parent):
	for i in data[now]:
		# global count
		# count+=1
		if i==parent:continue
			
		cnt[i]+=value
		visited[i]=1
		# print(cnt)	
		
		plus(i,cnt[i],now)
		
		
visited[1]=1
plus(1,cnt[1],0)
print(*cnt[1:])
# print(count)

# ans=sorted(cnt.items())
# print(*[i[1] for i in ans])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from collections import defaultdict
sys.setrecursionlimit(10**8)
input = lambda: sys.stdin.readline()[:-1]
n,q=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
px=[tuple(map(int,input().split())) for i in range(q)]
ab.sort(key=lambda tup:(tup[0],tup[1]))
visited=[0]*(n+1)
cnt=[0]*(n+1)
data=[[] for i in range(n+1)]

for i in ab:
	data[i[0]].append(i[1])
	data[i[1]].append(i[0])
for j in px:
	cnt[j[0]]+=j[1]
	# print(cnt)

def plus(now,value):
	for i in data[now]:
		if not visited[i]:
			cnt[i]+=value
			visited[i]=1
			# print(cnt)	
			plus(i,cnt[i])
		
		
visited[1]=1
plus(1,cnt[1])
print(*cnt[1:])

# ans=sorted(cnt.items())
# print(*[i[1] for i in ans])

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N-1)]
Y = [list(map(int,input().split())) for _ in range(Q)]

con = [[] for _ in range(N)]
for i in range(N-1):
    con[X[i][0]-1]+=[X[i][1]-1]
    con[X[i][1]-1]+=[X[i][0]-1]

dif = [0]*N
for i in range(Q):
    dif[Y[i][0]-1] += Y[i][1]

root = [0]
while root:
    cur = root.pop()
    for i in con[cur]:
        dif[i] += dif[cur]
        con[i].remove(cur)
        root.append(i) 

print(*dif)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from collections import defaultdict
sys.setrecursionlimit(10**8)
input = lambda: sys.stdin.readline()[:-1]
cnt=Counter()
data=defaultdict(set)
visited=Counter()
n,q=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
px=[tuple(map(int,input().split())) for i in range(q)]
ab.sort(key=lambda tup:(tup[0],tup[1]))
for i in ab:
	data[i[0]].add(i[1])
	data[i[1]].add(i[0])
for j in px:
	cnt[j[0]]+=j[1]

def plus(now,value):
	for i in data[now]:
		if not visited[i]:
			cnt[i]+=value
			visited[i]=1
			# print(cnt)	
			plus(i,cnt[i])
		
		
cnt[1]+=0
visited[1]=1
plus(1,cnt[1])
# print(cnt)

ans=sorted(cnt.items())
print(*[i[1] for i in ans])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

N,Q = map(int,input().split())
AB_list = [list(map(int,input().split())) for i in range(N-1)]
target_list = [list(map(int,input().split())) for i in range(Q)]
ab_tree = [[] for i in range(N)]
for i in range(N-1):
     a = AB_list[i][0] -1
     b = AB_list[i][1] -1
     ab_tree[a].append(b)
     ab_tree[b].append(a)

#print(ab_tree)
ans = [0] * N
#print(ans)
for t in target_list:
    ans[t[0]-1] += t[1]
#print(ans)
def dfs(cur,par):
    for child in ab_tree[cur]:
        if child == par:
            continue
        ans[child] += ans[cur]
        dfs(child,cur)

dfs(0,-1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, q = map(int, input().split())

tree = [[] for _ in range(n)]

for i in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

add = [0] * n

for i in range(q):
    p, x = map(int, input().split())
    add[p-1] += x

ans = [0] * n

def dfs(v, p, value):
    value += add[v]
    ans[v] = value
    for c in tree[v]:
        if c == p:
            continue
        dfs(c, v, value)

dfs(0, -1, 0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())

tree = [[] for _ in range(n)]

for i in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

add = [0] * n

for i in range(q):
    p, x = map(int, input().split())
    add[p-1] += x

ans = [0] * n

def dfs(v, p, value):
    value += add[v]
    ans[v] = value
    for c in tree[v]:
        if c == p:
            continue
        dfs(c, v, value)

dfs(0, -1, 0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

N, Q = map(int,input().split())
nord = [set() for i in range(N)]

for i in range(N-1):
    a, b = map(int,input().split())
    nord[a-1].add(b-1)
    nord[b-1].add(a-1)

nord_num = [0 for i in range(N)]
for i in range(Q):
    p, x = map(int,input().split())
    nord_num[p-1] = nord_num[p-1] + x
    
currentN = set([0])
stockList = set()
arrive = set([0])
count = 1
while count<N:
    nextN = set()
    for i in currentN:
        stockList = nord[i] - currentN - arrive
        for j in stockList:
            arrive.add(j)
            nord_num[j] = nord_num[j] + nord_num[i]
            count += 1
        nextN = nextN | stockList
    currentN = nextN
    
        

count = 1
for i in nord_num:
    if count == N:
        print(i)
    else:
        print(i, end=" ")
        count += 1

Submission status: Time Limit Exceeded

Solution code:
def search(tree, p, callback):
    if tree[0] == p:
        callback(tree)
        return True         # 見つかったら加算に入って検索を停止
    else:
        for sub in tree[2]:
            if search(sub, p, callback):
                return True
        return False

def add_and_propagate(tree, x=0):
    tree[1] += x
    for sub in tree[2]:
        add_and_propagate(sub, tree[1])
    
def get_nodes(tree):
    yield tree[:2]
    for sub in tree[2]:
        yield from get_nodes(sub)

def add_children(tree, p, qs, counts):
    def callback(tree):
        tree[2].extend([[q, counts[q-1], []] for q in qs])
    return search(tree, p, callback)

def find_next(p, edges):
    to_remove = set()
    for e in edges:
        if p in e:
            to_remove.add(e)
            yield e[0] if p == e[1] else e[1]
    edges.difference_update(to_remove)

def output(tree):
    print(*(c for n, c in sorted(get_nodes(tree))))

def readlines(N):
    for _ in range(N):
        yield tuple(map(int, input().split()))

N, Q = next(readlines(1))
edges = set(readlines(N - 1))
counts = [0 for _ in range(N)]
for p, x in readlines(Q):
    counts[p-1] += x
tree = [1, counts[0], []]
frontier = [1]
for f in frontier:
    nexts = list(find_next(f, edges))
    frontier.extend(nexts)
    add_children(tree, f, nexts, counts)
add_and_propagate(tree)

output(tree)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def bfs(graph, start, query, n):
    queue = deque([])
    acc = query[start] if start in query else 0
    queue.append([start, acc])
    ans = [-1] * n
    ans[start] = acc

    while queue:
        idx, acc = queue.popleft()
        for child in graph[idx].keys():
            if ans[child] >= 0:
                continue
            ans[child] = acc
            if child in query:
                ans[child] += query[child]
            queue.append([child, ans[child]])
    
    print(' '.join(map(str, ans)))

n,q = map(int, input().split())
tree = {}
start = 0
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    if a not in tree:
        tree[a] = {}
    tree[a][b] = 1
    if b not in tree:
        tree[b] = {}
    tree[b][a] = 1

query = {}
for _ in range(q):
    p, x = map(int,input().split())
    p -= 1
    if p not in query:
        query[p] = x
    else:
        query[p] += x
bfs(tree, start, query, n)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def bfs(graph, start, query):
    queue = deque([])
    acc = query[start] if start in query else 0
    queue.append([start, acc])
    ans = {start:acc}

    while queue:
        idx, acc = queue.popleft()
        for child in graph[idx].keys():
            if child in ans:
                continue
            ans[child] = acc
            if child in query:
                ans[child] += query[child]
            queue.append([child, ans[child]])
    return ans

n,q = map(int, input().split())
tree = {}
start = 1
for i in range(n-1):
    a,b = map(int, input().split())
    if a not in tree:
        tree[a] = {}
    tree[a][b] = 1
    if b not in tree:
        tree[b] = {}
    tree[b][a] = 1

query = {}
for _ in range(q):
    p, x = map(int,input().split())
    if p not in query:
        query[p] = x
    else:
        query[p] += x
ans = bfs(tree, start, query)
[print(ans[i], end=' ') for i in range(1, n+1)]

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def bfs(graph, start, query):
    queue = deque([])
    acc = query[start] if start in query else 0
    queue.append([start, acc])
    ans = {start:acc}

    while queue:
        idx, acc = queue.popleft()
        for child in graph[idx].keys():
            ans[child] = acc
            if child in query:
                ans[child] += query[child]
            queue.append([child, ans[child]])
            del graph[child][idx]
    [print(ans[i], end=' ') for i in range(1, n+1)]

n,q = map(int, input().split())
tree = {}
start = 1
for i in range(n-1):
    a,b = map(int, input().split())
    if a not in tree:
        tree[a] = {}
    tree[a][b] = 1
    if b not in tree:
        tree[b] = {}
    tree[b][a] = 1

query = {}
for _ in range(q):
    p, x = map(int,input().split())
    if p not in query:
        query[p] = x
    else:
        query[p] += x
bfs(tree, start, query)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def bfs(graph, start, query):
    queue = deque([])
    acc = query[start] if start in query else 0
    queue.append([start, acc])
    ans = {start:acc}

    while queue:
        idx, acc = queue.popleft()
        for child in graph[idx].keys():
            if child in ans:
                continue
            ans[child] = acc
            if child in query:
                ans[child] += query[child]
            queue.append([child, ans[child]])
    [print(ans[i], end=' ') for i in range(1, n+1)]

n,q = map(int, input().split())
tree = {}
start = 1
for i in range(n-1):
    a,b = map(int, input().split())
    if a not in tree:
        tree[a] = {}
    tree[a][b] = 1
    if b not in tree:
        tree[b] = {}
    tree[b][a] = 1

query = {}
for _ in range(q):
    p, x = map(int,input().split())
    if p not in query:
        query[p] = x
    else:
        query[p] += x
bfs(tree, start, query)

Submission status: Time Limit Exceeded

Solution code:
#再帰のlimitを解除
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n, q = map(int, input().split())
#何と繋がっているか（隣接リスト）
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

memo = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    memo[p] += x

#深さ優先探索 累積和
def dfs(v, par):
    for nv in g[v]:
        if nv == par:
            continue
        #1つ先に情報を流す
        memo[nv] += memo[v]
        #dfsを更新
        dfs(nv, v)

dfs(0, -1)

print(*memo)

Submission status: Time Limit Exceeded

Solution code:
def main():

    # Input N, Q
    N, Q = [int(c) for c in input().split()]

    # Input edges
    edges = [[] for i in range(N)]
    for i in range(N-1):
        u, v = [int(c)-1 for c in input().split()]
        edges[u].append(v)
        edges[v].append(u)

    # Form tree
    parent = [None for i in range(N)]
    childs = [[] for i in range(N)]
    def dfs(root):
        parent[root] = -1
        stack = [root]
        while stack:
            now = stack.pop()
            for nex in edges[now]:
                if parent[nex] is None:
                    parent[nex] = now
                    childs[now].append(nex)
                    stack.append(nex)
    dfs(0)

    # Queries
    incremented = [0 for i in range(N)]
    for i in range(Q):
        v, add = [int(c) for c in input().split()]
        v -= 1
        incremented[v] += add

    # Lower propagate
    total = [0 for i in range(N)]
    def propagate(root):
        stack = [root]
        while stack:
            now = stack.pop()
            total[now] += incremented[now]
            for child in childs[now]:
                total[child] += total[now]
                stack.append(child)
    propagate(0)

    # Print
    print(" ".join(str(num) for num in total))

main()

Submission status: Time Limit Exceeded

Solution code:
# Input N, Q
N, Q = [int(c) for c in input().split()]

# Input edges
edges = [[] for i in range(N)]
for i in range(N-1):
    u, v = [int(c)-1 for c in input().split()]
    edges[u].append(v)
    edges[v].append(u)

# Form tree
parent = [None for i in range(N)]
childs = [[] for i in range(N)]
def dfs(root):
    parent[root] = -1
    stack = [root]
    while stack:
        now = stack.pop()
        for nex in edges[now]:
            if parent[nex] is None:
                parent[nex] = now
                childs[now].append(nex)
                stack.append(nex)
dfs(0)

# Queries
incremented = [0 for i in range(N)]
for i in range(Q):
    v, add = [int(c) for c in input().split()]
    v -= 1
    incremented[v] += add

# Lower propagate
total = [0 for i in range(N)]
def propagate(root):
    global total
    stack = [root]
    while stack:
        now = stack.pop()
        total[now] += incremented[now]
        for child in childs[now]:
            total[child] += total[now]
            stack.append(child)
propagate(0)

# Print
print(" ".join(str(num) for num in total))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]
 
g = [[] for _ in range(N+1)]
for a,b in AB:
    g[a].append(b)
    g[b].append(a)
    
cnt = [0] * (N+1)
for p,x in PX:
    cnt[p] += x

# v: node, p: parent node, add: parent value
def dfs(v, p, add):
    cnt[v] += add
    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, cnt[v])
 
dfs(1, 0, 0)

print(' '.join(map(str, cnt[1:])))

Submission status: Time Limit Exceeded

Solution code:
import collections
N, QQ = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1)]
PX = [[int(_) for _ in input().split()] for _ in range(QQ)]
cd = collections.defaultdict
G = cd(set)
for ab in AB:
    a, b = ab
    G[a].add(b)
    G[b].add(a)
count = [0] * (N + 1)
for px in PX:
    p, x = px
    count[p] += x
ans = [0] * (N + 1)
visited = [False] * (N + 1)
visited[1] = 1
Q = [1]
while Q:
    q = Q.pop()
    for nq in G[q]:
        if not visited[nq]:
            visited[nq] = True
            Q += [nq]
            count[nq] += count[q]
print(*count[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N,Q = map(int,input().split())
to = [[] for _ in range(N+1)]
ans = [0 for _ in range(N+1)]

for _ in range(N-1):
    a,b=map(int,input().split())
    to[a].append(b)
    to[b].append(a)
for _ in range(Q):
    px = list(map(int,input().split()))
    ans[px[0]] += px[1]

def dfs(v, p):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)
dfs(1, -1)
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n-1)]
P = [list(map(int,input().split())) for i in range(q)]

ANS = [0] * (n+1)

C_plus = [0] * (n+1)
for i in range(q):
    C_plus[P[i][0]] += P[i][1]

E = [[] for i in range(n+1)]
V = [0] * (n+1)
Q = [1]
t = 0

V[1] = 1
ANS[1] = C_plus[1]

for i in range(n-1):
    E[A[i][0]].append(A[i][1])
    E[A[i][1]].append(A[i][0])

def tansaku(x):
    for i in E[x]:
        if V[i] == 0:
            ANS[i] = C_plus[i] + ANS[x]
            V[i] = 1
            Q.append(i)
            #print(Q)

while t < len(Q):
    tansaku(Q[t])
    t += 1

#print(ANS)

for i in range(n+1):
    ANS[i] = str(ANS[i])
print(" ".join(ANS[1:]))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n-1)]
P = [list(map(int,input().split())) for i in range(q)]

ANS = [0] * (n+1)

C_plus = [0] * (n+1)
for i in range(q):
    C_plus[P[i][0]] += P[i][1]

oya = [0] * (n+1)
E = [[] for i in range(n+1)]
V = [0] * (n+1)
Q = [1]
t = 0

V[1] = 1
ANS[1] = C_plus[1]

for i in range(n-1):
    E[A[i][0]].append(A[i][1])
    E[A[i][1]].append(A[i][0])

def tansaku(x):
    for i in E[x]:
        if V[i] == 0:
            oya[i] = x
            ANS[i] = C_plus[i] + ANS[x]
            V[i] = 1
            Q.append(i)
            #print(Q)

while t < len(Q):
    tansaku(Q[t])
    t += 1

#print(ANS)

for i in range(n+1):
    ANS[i] = str(ANS[i])
print(" ".join(ANS[1:]))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
connections = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    pa, ki = map(int, input().split())
    connections[pa].append(ki)
    connections[ki].append(pa)

scores = [0 for _ in range(N + 1)]
for _ in range(Q):
    tag, p = map(int, input().split())
    scores[tag] += p

i = 1

def dfs(k=1,bef=-1):
    global scores
    global fins
    kids = connections[k]
    if len(kids)==1 and bef==kids[0]:
        return
    for kid in kids:
        # print(f'k:{k} kids:{kids}')
        if bef==kid:
            continue
        scores[kid]+=scores[k]
        dfs(kid,k)


dfs()



print(*scores[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
connections = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    pa, ki = map(int, input().split())
    connections[pa].append(ki)
    connections[ki].append(pa)

scores = [0 for _ in range(N + 1)]
for _ in range(Q):
    tag, p = map(int, input().split())
    scores[tag] += p

i = 1
fins = []

def dfs(k=1,bef=-1):
    global scores
    global fins
    kids = connections[k]
    if len(kids)==1 and bef==kids[0]:
        return
    for kid in kids:
        # print(f'k:{k} kids:{kids}')
        if bef==kid:
            continue
        scores[kid]+=scores[k]
        fins.append(kid)
        dfs(kid,k)


dfs()



print(*scores[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**9)
N, Q = map(int, input().split())
connections = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    pa, ki = map(int, input().split())
    connections[pa].append(ki)
    connections[ki].append(pa)

scores = [0 for _ in range(N + 1)]
for _ in range(Q):
    tag, p = map(int, input().split())
    scores[tag] += p

i = 1
fins = []

def dfs(k=1):
    global scores
    global fins
    if k in fins:
        return
    fins.append(k)
    kids = connections[k]
    if not kids:
        return
    for kid in kids:
        if kid in fins:
            continue
        scores[kid]+=scores[k]
        dfs(kid)


dfs()



print(*scores[1:])

Submission status: Time Limit Exceeded

Solution code:
import copy

N, Q = map(int,input().split())
nord = [[0 for i in range(N)] for j in range(N)]
parents = [0]

for i in range(N-1):
    a, b = map(int,input().split())
    nord[a-1][b-1] = 1
    nord[b-1][a-1] = 1

saveNord = copy.deepcopy(nord)
currentN = []
nextN = []
check = 0
for i in range(N):
    if nord[0][i]==1:
        currentN.append(i)
        nord[0][i]=0
        nord[i][0]=0
        check += 1
while check<N-1:
    for i in currentN:
        for j in range(N):
            if nord[i][j]==1:
                nextN.append(j)
                nord[j][i]=0
                nord[i][j]=0
                check += 1
    parents.extend(currentN)
    currentN = nextN
parents.extend(currentN)

nord_num = [0 for i in range(N)]
for i in range(Q):
    p, x = map(int,input().split())
    nord_num[p-1] = nord_num[p-1] + x
    
arrive = set()
for i in parents:
    arrive.add(i)
    for j in range(N):
        if (saveNord[i][j]==1) and (j in arrive):
            nord_num[i] = nord_num[j] + nord_num[i]


count = 1
for i in nord_num:
    if count == N:
        print(i)
    else:
        print(i, end=" ")
        count += 1