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:
N,Q = map(int,input().split())
G = [[]for i in range(N+1)]

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
C = [0]*(N+1)
for i in range(Q):
    p,x = map(int,input().split())
    C[p] += x

stack = [1]
list = []
while len(stack) > 0:
    a = stack.pop(0)
    list.append(a)
    for b in G[a]:
        if b not in list:
            stack.append(b)
            C[b] += C[a]
C.pop(0)
print(*C)

Submission status: Time Limit Exceeded

Solution code:
from queue import *
from sys import stdin
input = stdin.readline

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

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

unused = [1]*n
que = Queue()
que.put(0)
while que.qsize():
    m = que.get()
    unused[m] = 0
    for v in link[m]:
        if unused[v]:
            weight[v] += weight[m]
            que.put(v)
print(*weight)

Submission status: Time Limit Exceeded

Solution code:
from queue import *

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

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

used = [0]*n
que = Queue()
que.put(0)
while(que.qsize()):
	m = que.get()
	used[m] = 1
	for v in link[m]:
		if 1^used[v]:
			weight[v] += weight[m]
			que.put(v)
print(*weight)

Submission status: Time Limit Exceeded

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

n,q=map(int,input().split())
g=[[]for _ in range(n)]
res=[0 for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)

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


def my_add(v,par):
    for vn in g[v]:
        if vn==par:
            continue
        res[vn]+=res[v]
        my_add(vn,v)

my_add(0,-1)
print(*res)

Submission status: Time Limit Exceeded

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

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

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


def my_add(v,par):
    for vn in g[v]:
        if vn==par:
            continue
        res[vn]+=res[v]
        my_add(vn,v)

my_add(0,-1)
print(*res)

Submission status: Time Limit Exceeded

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

def main():
    n, q = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        g[a].append(b); g[b].append(a)
    node = [0]*n
    for i in range(q):
        p, x = map(int, input().split())
        p -= 1
        node[p] += x

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * 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)

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

def dfs(v, p=-1):
    for u in g[v]:
        if u == p: continue
        node[u] += node[v]
        dfs(u, v)

dfs(0)
print(*node)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
 
n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * 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)
 
for i in range(q):
    p, x = map(int, input().split())
    node[p-1] += x
 
def dfs(v, p=-1):
    for u in g[v]:
        if u == p: continue
        node[u] += node[v]
        dfs(u, v)
 
dfs(0)
print(*node)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * 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)

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

def dfs(v, p=-1):
    for u in g[v]:
        if u == p: continue
        node[u] += node[v]
        dfs(u, v)

dfs(0)
print(*node)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * 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)

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

def dfs(v, p=-1):
    for u in g[v]:
        if u == p: continue
        node[u] += node[v]
        dfs(u, v)

dfs(0)
print(*node)

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
vals = [0] * n
node_idxes = [[] for _ in range(n)]

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

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

def dfs(chi_idx, parent):
	for child in node_idxes[chi_idx]:
		if child == parent:
			continue
		vals[child] += vals[chi_idx]
		dfs(child, chi_idx)

dfs(0, -1)
print(*vals)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
from itertools import groupby
sys.setrecursionlimit(10**6) 
n,q = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n-1)]
lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]

kazu = [[]for _ in range(n)]
point = [0]*n

for i in range(len(li)):
    kazu[li[i][0]-1].append(li[i][1]-1)
    kazu[li[i][1]-1].append(li[i][0]-1)
for i in range(q):
    point[lin[i][0]-1] += lin[i][1]

def dfs(li,li2,now,before):
    for i in (li[now]):
        if i == before:
            continue
        li2[i] += li2[now]
        dfs(kazu,point,i,now)
dfs(kazu,point,0,-1)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))

Submission status: Time Limit Exceeded

Solution code:
import sys
def solve():
    sys.setrecursionlimit(1000000)
    N, Q = map(int, input().split())
    tree = [[] for i in range(N)]
    counter = [0] * N
    arrived = [False] * 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)
    
    for i in range(Q):
        p, x = map(int, input().split())
        counter[p-1] += x
    
    arrived[0] = True
    adder(0, counter, tree, arrived)

    print(*counter)

def adder(ind, counter, tree, arrived):
    for i in tree[ind]:
        if arrived[i]:
            continue
        counter[i] += counter[ind]
        arrived[i] = True
        adder(i, counter, tree, arrived)
    if not tree[ind]:
        return

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
ki = [[[],0] for i in range(N)]
result = [0]*N

def dfs(i, num, parent):
    num_tmp = num+ki[i][1]
    result[i] = num_tmp
    if not ki[i][0]:
        return
    for j in ki[i][0]:
        if j == parent:
            continue
        dfs(j, num_tmp, i)
    return

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

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

dfs(0, 0, -1)
print(*result)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N, Q = LI()
P = [0] * N
V = [[] for _ in range(N)]

w = [0]*N
for i in range(N-1):
    A, B = LI()
    V[A-1].append(B-1)
    V[B-1].append(A-1)
#    AB[i] = LI()
for i in range(Q):
    p, x = LI()
    P[p-1] += x

#print(V)
for i in range(N):
    w[i] += P[i]

#i = int(0)
#for l in V:
#   for j in l:
#        print(i, j)
#        w[j] += w[i]
#        print(w)
#    i +=1
def solve(v,i):
#    print(v,i)
#    print(w)
#    print("#####")
    if not v[i]:
        return
    else:
        for l in v[i]:
            w[l] += w[i]
            v[l].remove(i)
            solve(v,l)
        return
i =int(0)
solve(V,i)

print(" ".join(map(str,w)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

def dfs(node):
    tmp = data[node]
    for v in G[node]:
        if not visited[v]:
            visited[v]=1
            data[v]+=tmp
            dfs(v)
    return 0



n,q=map(int,input().split())
G=[[] for i 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)
data=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    data[p-1]+=x
visited=[0]*n
visited[0]=1
dfs(0)
print(*data)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

def dfs(node):
    for v in G[node]:
        if not visited[v]:
            visited[v]=1
            data[v]+=data[node]
            dfs(v)
    return 0



n,q=map(int,input().split())
G=[[] for i 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)
data=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    data[p-1]+=x
visited=[0]*n
visited[0]=1
dfs(0)
print(*data)

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * 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)

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

def dfs(v, p=-1):
    for u in g[v]:
        if u == p: continue
        node[u] += node[v]
        dfs(u, v)

dfs(0)
print(*node)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, q = map(int, input().split(' '))
    import sys
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = [0]
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop(0)
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# N: ノードの数
# Q: 数値をノードに付与する回数
N, Q = list(map(int, input().split()))

links =  [[] for x in range(N)]
values = [0 for _ in range(N)]

for i in range(N - 1):
    edge1, edge2 = [x - 1 for x in list(map(int, input().split()))]
    links[edge1].append(edge2)
    links[edge2].append(edge1)

for i in range(Q):
    node, val = list(map(int, input().split()))
    values[node - 1] += val

# 値の計算
queue = [(0, -1)]  # [(ノードID, 親ノードID)] のリスト (-1 は番兵)
while queue:
    node = queue[0]
    queue = queue[1:]

    for linked_node in links[node[0]]:
        if linked_node == node[1]:  # link が親ノード向けでなければ
            continue

        values[linked_node] += values[node[0]]
        queue.append((linked_node, node[0]))

print(*values)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# N: ノードの数
# Q: 数値をノードに付与する回数
N, Q = list(map(int, input().split()))

# {0: [], 1: [], ...} のような辞書を作る
links = { x:[] for x in range(N) }

values = [ 0 for _ in range(N) ]

for i in range(N - 1):
    edge1, edge2 = [x - 1 for x in list(map(int, input().split()))]
    links[edge1].append(edge2)
    links[edge2].append(edge1)

for i in range(Q):
    node, val = list(map(int, input().split()))
    values[node - 1] += val

# 値の計算
queue = [(0, -1)]  # [(ノードID, 親ノードID)] のリスト (-1 は番兵)
while queue:
    node = queue[0]
    queue = queue[1:]

    for linked_node in links[node[0]]:
        if linked_node == node[1]:  # link が親ノード向けでなければ
            continue

        values[linked_node] += values[node[0]]
        queue.append((linked_node, node[0]))

print(*values)

Submission status: Time Limit Exceeded

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

flag = [1]*N
q = [0]
flag[0] = 1
while q:
    temp = q.pop(0)
    flag[temp] = 0
    for i in L[temp]:
        if flag[i]:
            q.append(i)
            cnt[i] += cnt[temp]
            
print(*cnt)

Submission status: Time Limit Exceeded

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

flag = [1]*N
q = [0]
flag[0] = 1
while q:
    temp = q.pop(0)
    flag[temp] = 0
    for i in L[temp]:
        if flag[i]:
            q.append(i)
            cnt[i] += cnt[temp]
            
for i in range(N):
    print(cnt[i])

Submission status: Time Limit Exceeded

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


flag = [-1]*N
q = [0]
flag[0] = 1
while q:
    temp = q.pop(0)
    for i in L[temp]:
        if flag[i] < 0:
            q.append(i)
            cnt[i] += cnt[temp]
            flag[i] = 1
            
print(*cnt)

Submission status: Time Limit Exceeded

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


flag = [-1]*N
q = [0]
flag[0] = 1
while q:
    temp = q.pop(0)
    for i in L[temp]:
        if flag[i] < 0:
            q.append(i)
            cnt[i] += cnt[temp]
            flag[i] = 1
            
for i in range(N):
    print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
qlist = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    qlist[p-1] += x


cnt = [-1]*N
q = [0]
cnt[0] = qlist[0]
while q:
    temp = q.pop(0)
    for i in L[temp]:
        if cnt[i] < 0:
            q.append(i)
            cnt[i] = cnt[temp]+qlist[i]
            
for i in range(N):
    print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
qlist = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    qlist[p-1] += x

g = 10**6
cnt = [-1]*N
q = [qlist[0]*g]
cnt[0] = qlist[0]
while q:
    temp = q.pop(0)
    c = temp//g
    v = temp%g
    for i in L[v]:
        if cnt[i] < 0:
            q.append((c+qlist[i])*g + i)
            cnt[i] = c+qlist[i]
            
for i in range(N):
    print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
qlist = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    qlist[p-1] += x

    
cnt = [-1]*N
q = [qlist[0]]
cnt[0] = qlist[0]
g = 10**10
while q:
    temp = q.pop(0)
    v = temp//g
    c = temp%g
    for i in L[v]:
        if cnt[i] < 0:
            q.append(i*g + c+qlist[i])
            cnt[i] = c+qlist[i]
            
for i in range(N):
    cnt[i] = str(cnt[i])
print(" ".join(cnt))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())

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

question = [[int(q) for q in input().split()] for _ in range(Q)]
    
qlist = [0]*N
for i in range(Q):
    qlist[question[i][0]-1] += question[i][1]
    
cnt = [-1]*N
q = [[0, qlist[0]]]
cnt[0] = qlist[0]
while q:
    temp = q.pop(0)
    v = temp[0]
    c = temp[1]
    for i in L[v]:
        if cnt[i] < 0:
            q.append([i, c+qlist[i]])
            cnt[i] = c+qlist[i]
            
for i in range(N):
    cnt[i] = str(cnt[i])
print(" ".join(cnt))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


def PX(T, P, X):
    if not P:
        return 0
    for p in P:
        if T in memo[p]:
            memo[p].remove(T)
        ans[p] += X
        PX(p, memo[p], ans[p])
    return 0


N, Q = map(int, input().split())
memo = [[] for _ in range(N + 1)]
ans = [0 for _ in range(N + 1)]
for i in range(1, N):
    a, b = map(int, input().split())
    memo[a] += [b]
    memo[b] += [a]
for j in range(Q):
    p, x = map(int, input().split())
    ans[p] += x
PX(1, memo[1], ans[1])
ans.pop(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


def PX(T, P, X):
    if not P:
        return 0
    for p in P:
        if T in memo[p]:
            memo[p].pop(memo[p].index(T))
        ans[p] += X
        PX(p, memo[p], ans[p])
    return 0


N, Q = map(int, input().split())
memo = [[] for _ in range(N + 1)]
ans = [0 for _ in range(N + 1)]
for i in range(1, N):
    a, b = map(int, input().split())
    memo[a] += [b]
    memo[b] += [a]
for j in range(Q):
    p, x = map(int, input().split())
    ans[p] += x
PX(1, memo[1], ans[1])
ans.pop(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10 ** 7)

# input & solve
N, Q = map(int, input().split())

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

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

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

dfs(0)

# output
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**7)

# input & solve
N, Q = map(int, input().split())

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

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

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

dfs(0)

# output
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**7)
N, Q = [int(x) for x in input().split()]
to = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = [int(x)-1 for x in input().split()]
    to[b].append(a)
    to[a].append(b)
ans = [0] * N
for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    p -= 1
    ans[p] += x

def dfs(v, p=-1):
    for u in to[v]:
        if (u == p): continue
        ans[u] += ans[v]
        dfs(u, v)        
dfs(0)
print(' '.join([str(i) for i in ans]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, Q = map(int, input().split())
V = {v: 0 for v in range(1, N+1)}
E = {v: [] for v in V.keys()}
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
added = defaultdict(int)
for _ in range(Q):
    p, x = map(int, input().split())
    added[p] += x
stack = [(1, added[1])]
visited = {v: False for v in V.keys()}
while stack:
    v, value = stack.pop()
    visited[v] = True
    V[v] += value
    for u in E[v]:
        if not visited[u]:
            stack.append((u, value + added[u]))
print(*[val for val in V.values()])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
#print(graph)
for _ in range(Q):
    a , b = map(int,input().split())
    a = a - 1
    point[a] += b

# dfsを用いて累積和を計算する
# 初期状態だと前の値がないためデフォルト引数に-1を代入
def dfs(now , prev = -1):
    for next in graph[now]:
        # 次のノードが前に参照した値の時はcontinue
        if next == prev:
            continue

        # 現在の値を次のポイントに加算することで累積和をとる
        point[next] += point[now]

        # 次のノードと現在のノードを引数にdfsを継続する
        dfs(next , now)

dfs(0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline()

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

cnt = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x
 
 
def dfs(now, bef):
    for nxt in edge[now-1]:
        if nxt != bef:
            cnt[nxt-1] += cnt[now-1]
            dfs(nxt, now)
 
 
dfs(1, -1)
print(*cnt)

Submission status: Time Limit Exceeded

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

n,q = map(int,input().split())
t = [[] for _ in range(n+1)]
for _ in range(n-1):
  a,b = map(int,input().split())
  t[a].append(b)
  t[b].append(a)
cnt = [0]*(n+1)
for _ in range(q):
  p,x = map(int,input().split())
  cnt[p] += x
def csum(now,bef):
  for i in t[now]:
    if i != bef:
      cnt[i] += cnt[now]
      csum(i,now)
csum(1,0)
for i in range(1,n+1):
  print(cnt[i],end=" ")

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(N-1) :
    a, b = map(int, input().split())
    v[a-1].append(b-1)
    v[b-1].append(a-1)
    
pq = [0 for _ in range(N)]
for _ in range(Q) :
    p, q = map(int, input().split())
    pq[p-1] += q
    
visited = [False] * N
visited[0] = True

ret = [0] * N
def bfs(cur, score) :
    ret[cur] = score + pq[cur]
    for nex in v[cur] :
        if not visited[nex] :
            visited[nex] = True
            bfs(nex, ret[cur])

bfs(0, 0)
    
print(*ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

tmp = list(map(int, (input().split())))
n = tmp[0]
q = tmp[1]

edge = defaultdict(list)
fixed = [False] * (n + 1)
fixed[1] = True
point = [0] * (n + 1)

for i in range(1, n):
  tmp = list(map(int, (input().split())))
  edge[tmp[0]].append(tmp[1])
  edge[tmp[1]].append(tmp[0])

for i in range(1, q+1):
  tmp = list(map(int, (input().split())))
  point[tmp[0]] += tmp[1]

que = []
for i in edge[1]:
  que.append(i)
  
while len(que) != 0:
  cur = que.pop()
  for i in edge[cur]:
    if fixed[i] == 1:
      point[cur] += point[i]
    else:
      que.append(i)
  fixed[cur] = True

for i in range(1, n+1):
  print (point[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

L=[list(map(int,input().split())) for i in range(q)]
ctL=[0]*n
for i in range(q):
  ctL[L[i][0]-1]+=L[i][1]

def bfs(v):
  distance=[-1]*n
  distance[v]=ctL[v]
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            distance[connection[next[i]][j]]=distance[next[i]]+ctL[connection[next[i]][j]]
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

x=bfs(0)
for i in range(n):
  x[i]=str(x[i])
print(' '.join(x))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

L=[list(map(int,input().split())) for i in range(q)]
ctL=[0]*n
for i in range(q):
  ctL[L[i][0]-1]+=L[i][1]

def bfs(v):
  distance=[-1]*n
  distance[v]=ctL[v]
  next=connection[v]
  for i in range(len(next)):
    next[i]=(next[i],v)
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i][0]]==-1:
        distance[next[i][0]]=distance[next[i][1]]+ctL[next[i][0]]
        visited[next[i][0]]=1
        visitct+=1
        for j in range(len(connection[next[i][0]])):
          if visited[connection[next[i][0]][j]]==-1:
            next2.add((connection[next[i][0]][j],next[i][0]))
    next=list(next2)
    next2=set()
  return distance

x=bfs(0)
for i in range(n):
  x[i]=str(x[i])
print(' '.join(x))

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
ab = [map(int, input().split()) for _ in range(n-1)]
px = [map(int, input().split()) for _ in range(q)]

cnt = [0 for _ in range(n)]
for p, x in px:
    cnt[p-1] += x

edge = [[] for _ in range(n)]
for a, b in ab:
    edge[a-1].append(b)
    edge[b-1].append(a)


def dfs(now, bef):
    for nxt in edge[now-1]:
        if nxt != bef:
            cnt[nxt-1] += cnt[now-1]
            dfs(nxt, now)


dfs(1, -1)
print(*cnt)

Submission status: Time Limit Exceeded

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

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

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

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


def dfs(now, bef):
    for nxt in edge[now-1]:
        if nxt != bef:
            cnt[nxt-1] += cnt[now-1]
            dfs(nxt, now)


dfs(1, -1)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
ab = [map(int, input().split()) for _ in range(n-1)]
px = [map(int, input().split()) for _ in range(q)]

cnt = [0 for _ in range(n)]
for p, x in px:
    cnt[p-1] += x

edge = [[] for _ in range(n)]
for a, b in ab:
    edge[a-1].append(b)
    edge[b-1].append(a)


def dfs(now, bef):
    for nxt in edge[now-1]:
        if nxt != bef:
            cnt[nxt-1] += cnt[now-1]
            dfs(nxt, now)


dfs(1, 0)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

N, Q = map(int, stdin.readline().split())

a = []
b = []
for i in range(N-1):
    temp_a, temp_b = map(int, stdin.readline().split())
    a.append(temp_a)
    b.append(temp_b)

p = []
x = []
for i in range(Q):
    temp_p, temp_x = map(int, stdin.readline().split())
    p.append(temp_p)
    x.append(temp_x)

c = [0 for i in range(N)]
parent_node = [0 for i in range(N)]
for i in range(N-1):
    parent_node[b[i]-1] = a[i]

route = []
for i in range(N):
    temp_list = [i]
    current_node = i
    while current_node != 0:
        #print(current_node)
        current_node = parent_node[current_node] - 1
        temp_list.append(current_node)
    route.append(temp_list)
#print(route)

point = [0 for i in range(N)]
for i in range(Q):
    point[p[i]-1] += x[i]
#print(point)



for i in range(N):
    for j in route[i]:
        c[i] += point[j]

print(*c)