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:
def d_ki():
    N, Q = [int(i) for i in input().split()]

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

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

    # 1次元配列だったら単純に累積和を取ればいいのだが、木なので
    # DFSをしなければならない
    q = [0]
    is_visited = [False] * N
    while q:
        current = q.pop()
        is_visited[current] = True
        for child in tree[current]:
            if is_visited[child]:
                continue
            ans[child] += ans[current]
            q.append(child)
    return ' '.join(map(str, ans))

print(d_ki())

Submission status: Time Limit Exceeded

Solution code:
def main():
        N,Q = map(int,input().split())
        ab = []
        for _ in range(N - 1):
        	ab.append(list(map(int,input().split())))
        px =[]
        for _ in range(Q):
        	px.append(list(map(int,input().split())))
        ab.sort()
        # px.sort()
        plus = []
        for _ in range(N):
        	plus.append(0)

        for p,x in px:
                plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

if __name__ == '__main__':
        main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, q = map(int, input().split())
d = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append(b)
    d[b].append(a)
d2 = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    d2[p-1] += x

ans = [0] * n

def dfs(cur, pre, point):
    point += d2[cur]
    ans[cur] = point
    for e in d[cur]:
        if e != pre:
            dfs(e, cur, point)
dfs(0, -1, 0)
print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:

NQ = input().split(' ')
N = int(NQ[0])
Q = int(NQ[1])
candidate_list = []
tree_list = [[]] * N
out_put_list = [0] * N

for i in range(N-1):
    ab = input().split(' ')
    a = int(ab[0])
    b = int(ab[1])
    tree_list[a-1] = tree_list[a-1] + [b-1]

for _ in range(Q):
    px = input().split(' ')
    p = int(px[0])
    x = int(px[1])
    out_put_list[p-1] += x

for i in range(len(tree_list)):
    for num in tree_list[i]:
        out_put_list[num] += out_put_list[i]

print(*out_put_list)

Submission status: Time Limit Exceeded

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

A=[[0]*2 for i in range(N)]
Ans=[0]*(N+1)
P=[[0]*2 for i in range(Q)]

for i in range(N-1):
    A[i][0],A[i][1] = map(int, input().split())
for i in range(Q):
    P[i][0],P[i][1] = map(int, input().split())
    Ans[P[i][0]]+=P[i][1]

A.sort()

for i in range(N):
    Ans[A[i][1]]+=Ans[A[i][0]]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,Q = list(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)]
v_list = np.zeros(N+1, dtype=np.int)
dic_tree = {}
for i in range(N):
    dic_tree[i+1] = [] 

for i in range(N-1):
    # a, b = list(map(int, input().split(" ")))
    a,b = ab[i]
    dic_tree[a].append(b)
        
for i in range(Q):
    # p, x = list(map(int, input().split(" ")))
    p,x = px[i]
    
    # v_list[dic_tree[p]] += x # Too Heavy...
    v_list[p] += x

for i in range(N):
    v_list[dic_tree[i+1]] += v_list[i+1]
    if i > 0:
        print(" ", end='') 
    print(v_list[i+1], end='')

Submission status: Time Limit Exceeded

Solution code:
def main():
        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)]
        ab.sort()
        # px.sort()
        plus = [0 for _ in range(N)]

        for p,x in px:
                plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

if __name__ == '__main__':
        main()

Submission status: Time Limit Exceeded

Solution code:
n , q = map(int, input().split())

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

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

for root, reaf in tree.items():
    for i in reaf:
        op[i] += op[root]

print(*op[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
NQ = input().split(' ')
N = int(NQ[0])
Q = int(NQ[1])
candidate_list = []
tree_list = [[]] * N
out_put_list = [0] * N
def f(p,x):
    out_put_list[p] += x
    for idx in tree_list[p]:
        f(idx,x)

for i in range(N-1):
    ab = input().split(' ')
    a = int(ab[0])
    b = int(ab[1])
    tree_list[a-1] = tree_list[a-1] + [b-1]

for _ in range(Q):
    px = input().split(' ')
    p = int(px[0])
    x = int(px[1])
    f(p-1,x)

print(*out_put_list)

Submission status: Time Limit Exceeded

Solution code:
n , q = map(int, input().split())

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

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

for root in tree:
    for i in tree[root]:
        op[i] += op[root]

print(*op[1:])

Submission status: Time Limit Exceeded

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

A=[[0]*2 for i in range(N)]
Ans=[0]*(N+1)
P=[[0]*2 for i in range(Q)]
X=[0]*Q

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

for i in range(Q):
    P[i][0],P[i][1] = map(int, input().split())

A.sort()
P.sort()

for i in range(Q):
    Ans[P[i][0]]+=P[i][1]

for i in range(N):
    Ans[A[i][1]]+=Ans[A[i][0]]

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

Submission status: Time Limit Exceeded

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

#%%
def dfs(gr,li,pt,n,fr):
    li[n] += pt
    if(len(gr[n])==1 and gr[n][0]==fr):
        return True
    else:
        for i in gr[n]:
            if(i==fr):continue
            dfs(gr,li,li[n],i,n)
        return True
#%%
def main():
    N,Q = [int(x) for x in input().split()]
    li = [0]*N
    gp = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = [int(x) for x in input().split()]
        gp[a-1].append(b-1)
        gp[b-1].append(a-1)

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

    dfs(gp,li,0,0,-1)
    print(*li)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def d_ki():
    import sys
    sys.setrecursionlimit(10**6)
    N, Q = [int(i) for i in input().split()]
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]
    Queries = [[int(i) for i in input().split()] for j in range(Q)]

    tree = [[] for _ in range(N)]
    for a, b in Edges:
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    ans = [0] * N
    # 1次元配列だったら累積和を取ればいいのだが、木なので
    # dfsをしなければならない
    for p, x in Queries:
        ans[p - 1] += x

    def dfs(current, parent=-1):
        for child in tree[current]:
            if child == parent:
                continue
            ans[child] += ans[current]
            dfs(child, current)
    dfs(0)
    return ' '.join(map(str, ans))

print(d_ki())

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split(" "))
A = []

B = [0 for j in range(N)]
for i in range(N-1):
    A.append(list(map(int,input().split(" "))))
    
A = sorted(A)
for j in range(Q):
    tmp = list(map(int,input().split(" ")))
    B[tmp[0]-1] += tmp[1]


for i in range(N-1):
        B[A[i][1]-1] += B[A[i][0]-1]

for i in range(N):
        print(B[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
n , q = map(int, input().split())

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

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

for root in tree.keys():
    for i in tree[root]:
        op[i] += op[root]

print(*op[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

#%%
def dfs(gr,li,pt,n,fr):
    li[n] += pt
    if(len(gr[n])==1 and gr[n][0]==fr):
        return True
    else:
        for i in gr[n]:
            if(i==fr):continue
            dfs(gr,li,li[n],i,n)
        return True
#%%
N,Q = [int(x) for x in input().split()]
li = [0]*N
gp = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = [int(x) for x in input().split()]
    gp[a-1].append(b-1)
    gp[b-1].append(a-1)

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

dfs(gp,li,0,0,-1)
print(*li)

Submission status: Time Limit Exceeded

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

class Node:
    def __init__(self):
        self.list = []
        self.score = 0

    def add(self, node):
        self.list.append(node)

nodes = []
for i in range(0, N):
    nodes.append(Node())

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

    nodes[a].add(nodes[b])

for i in range(0, Q):
    p, x = [int(v) for v in input().split()]

    nodes[p-1].score += x

l = [nodes[0]]

i = 0
while i < len(l):
    node = l[i]
    i += 1
    for child in node.list:
        child.score += node.score
        l.append(child)

print(' '.join(map(lambda n: str(n.score), nodes)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
from collections import defaultdict
N, Q = map(int, input().split())

to = defaultdict(list)

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

for _ 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 _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

dfs(0)

for i in range(N):
    print(ans[i], end=' ')

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split(" "))
A = []

B = [0 for j in range(N)]
for i in range(N-1):
    tmp = list(map(int,input().split(" ")))
    A.append(tmp)
A.sort()
for j in range(Q):
    tmp = list(map(int,input().split(" ")))
    B[tmp[0]-1] += tmp[1]


for i in range(N-1):
        B[A[i][1]-1] += B[A[i][0]-1]

for i in range(N):
        print(B[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    nodes[a-1].append(b-1)

ans = [0] * N
for i in range(Q):
    p, x = MAP()
    ans[p-1] += x

def dfs(u, prev, cnt):
    ans[u] += cnt
    for v in nodes[u]:
        dfs(v, u, ans[u])
dfs(0, -1, 0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop
 
import re
# import numpy as np
# from scipy.misc import comb
 
# 再帰がやばいとき
import sys
sys.setrecursionlimit(10**9)
 
def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W
 
# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]
 
INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7
 
# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]
 
########
 
def main():
    graph = defaultdict(list)
    scores = defaultdict(int)
    N, Q = l_inpl()
    for _ in range(N-1):
        a, b = l_inpl()
        graph[a].append(b)
    for _ in range(Q):
        p, x = l_inpl()
        scores[p] += x
 
    ans = [0] * N
    def dfs(graph, node_start, scores, score):
        score += scores[node_start]
        ans[node_start-1] = score
        for node_end in graph[node_start]:
            dfs(graph, node_end, scores, score)
        return 
 
    dfs(graph, 1, scores, 0)
    for s in ans:
        print(s)
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(300000)
from collections import defaultdict

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

ans = [0] * N


def dfs(to, fr, score):
    score += scores[to]
    ans[to] = score
    for u in adjacent[to]:
        if u == fr:
            continue
        dfs(u, to, score)


dfs(0, -1, 0)
print(' '.join([str(ans[i]) for i in range(N)]))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n, q = map(int, input().split())
cnt = [0]*n
root = [[] for i in range(n)]

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

for i in range(q):
    p, x = map(int, stdin.readline().split())

    tmpi = p-1
    tmparr = [tmpi]
    while tmparr:
        tmpi = tmparr.pop()
        cnt[tmpi] += x
        tmparr += root[tmpi]
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(gr,li,n,fr):
    if(len(gr[n])==1 and gr[n][0]==fr):
        li[n].add(n)
        return set([n])
    else:
        ans = set([n])
        for i in gr[n]:
            if(i==fr):continue
            ans |= dfs(gr,li,i,n)
        li[n] |= ans
        return ans
#%%
N,Q = [int(x) for x in input().split()]
nlist = [set() for _ in range(N)]
gp = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = [int(x) for x in input().split()]
    gp[a-1].append(b-1)
    gp[b-1].append(a-1)

qu = [[int(x) for x in input().split()]for _ in range(Q)]
#%%
li = [0]*N
dfs(gp,nlist,0,-1)
for p,x in qu:
    for j in nlist[p-1]:
        li[j] += x
print(*li)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1)]
CD=sorted(AB)
PX=[list(map(int,input().split())) for i in range(Q)]
counter=[0 for j in range(N)]
for k in range(Q):
    counter[PX[k][0]-1]+=PX[k][1]
for l in range(N-1):
    counter[CD[l][1]-1]+=counter[CD[l][0]-1]
for m in range(N):
    print(counter[m],end=' ')

Submission status: Time Limit Exceeded

Solution code:


MAX = 200005

def add_num(nn, x):
    if nn == -1:
        return
    Tree[nn][0] += x
    for ni in Tree[nn][1]:
        add_num(ni, x)


ipt = input().split()
N = int(ipt[0])
Q = int(ipt[1])



Tree = []
for m in range(MAX-1):
    Tree.append([-1, [-1]])

nodes = set()
nodes.add(1)

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

    Tree[a][0] = 0
    Tree[a][1].insert(0, b)
    Tree[b][0] = 0

    nodes.add(b)



for i in range(Q):
    ipti = input().split()
    p = int(ipti[0])
    x = int(ipti[1])

    cands = set()

    Tree[p][0] += x

    for pi in range(p,MAX-1):
        if Tree[pi] == -1:
            break
        for pii in Tree[pi][1]:
            cands.add(pii)
    for ci in cands:
        Tree[ci][0] += x

    #add_num(p, x)


for n in nodes:
    print(Tree[n][0])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
dd = defaultdict(list)
pq = defaultdict(int)
 
N, Q = map(int, input().split())
 
for _ in range(N-1):
    a,b = map(int, input().split())
    dd[a].append(b)
    dd[b].append(a)
 
for _ in range(Q):
    p,q = map(int, input().split())
    pq[p] += q
    
answer = [0]*N
queue = deque()
visited = {}
visited[1] = 1
queue.append(1)
 
while queue != deque():
    tmp = queue.popleft()
    answer[tmp-1] += pq[tmp]
    for i in dd[tmp]:
        if not i in visited:
            visited[i] = 1
            queue.append(i)
            answer[i-1] += answer[tmp-1]
            
print(*answer)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
cnt = [0]*n
root = [[] for i in range(n)]

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

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

tmparr = [0]
while tmparr:
    tmpi = tmparr.pop(0)
    for i in root[tmpi]:
        cnt[i] += cnt[tmpi]
    tmparr += root[tmpi]
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
arr = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    arr[a-1][b-1] += 1
    
ans = [0 for _ in range(n)] 

for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x
    
for i, c in enumerate(ans):
    for j, x in enumerate(arr[i]):
        if arr[i][j]==1:
            ans[j] += c
            
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
A = []
B = []
for i in range(N-1):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

P = []
X = []
for i in range(Q):
    p, x = map(int, input().split())
    P.append(p)
    X.append(x)

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

def get_list_of_targets(n):
    list_of_targets = []
    list_of_targets.append(n)
    for a, b in zip(A, B):
        if n == a:
            list_of_targets.append(a)
            list_of_targets.append(b)
            list_of_targets.extend(get_list_of_targets(b))
    return list(set(list_of_targets))
        
for p, x in zip(P, X):
    list_of_targets = []
    list_of_targets = get_list_of_targets(p)
    for target in list_of_targets:
        ans[target-1] += x
                        
for i in range(N):
    print(ans[i], end=' ')

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
A = [set([]) for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    A[a].add(b)
    A[b].add(a)
S = [1]
while S:
    a_1 = S[0]
    for a_2 in A[a_1]:
        A[a_2] -= {a_1}
        S += a_2,
    S.pop(0)
C = [0]*(n+1)
for _ in range(q):
    p, x = map(int, input().split())
    C[p] += x
for i in range(1, n+1):
    c = C[i]
    for a in A[i]:
        C[a] += c
print(*C[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

sys.setrecursionlimit(200000)

def resolve():
    N, Q = map(int, input().split())
    nodes = [[] for _ in range(N)]
    counter = [0] * (N)

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

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

    def send(numNode):
        for target in nodes[numNode]:
            counter[target] += counter[numNode]
            send(target)

    send(0)

    for count in counter:
        print(count, end=" ")

    print("")


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import defaultdict


def add(parent_n, edge_l):
    global result
    for edge in edge_l:
        if parent_n in edge:
            if parent_n == edge[0]:
                e_from = edge[0]
                e_to = edge[1]
            else:
                e_from = edge[1]
                e_to = edge[0]
            w = result[int(e_from) - 1]
            result[int(e_to) - 1] += w
            edge_l_c = copy.deepcopy(edge_l)
            edge_l_c.remove(edge)
            add(e_to, edge_l_c)


N, Q = input().split(' ')
N = int(N)
Q = int(Q)
ab = [input().split(' ') for i in range(N - 1)]
px = [input().split(' ') for i in range(Q)]

edge_list = sorted(ab)
start_edge_list = [e[0] for e in edge_list]

effect_weight = defaultdict(lambda: 0)
for impact in px:
    top_n = impact[0]
    val = int(impact[1])
    effect_weight[top_n] += val

result = [0 for i in range(N)]
for top_n, weight in effect_weight.items():
    result[int(top_n) - 1] = weight

add('1', ab)

result_str = [str(i) for i in result]
print(' '.join(result_str))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
memo = [[i] for i in range(N)]
flg = [False]*N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)

ans = [0]*N
add = [0]*N

for i in range(Q):
    p, x = map(int, input().split())
    if flg[p-1] is False:
        queue = [p-1]
        while queue:
            par = queue.pop(0)
            if flg[par]:
                memo[p-1].extend(memo[par])
            else:
                if G[par]:
                    for i in G[par]:
                        queue.append(i)
                        memo[p-1].append(i)
        flg[p-1] = True
    add[p-1] += x

for i in range(N):
    if flg[i]:
        for j in set(memo[i]):
            ans[j] += add[i]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(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)]

class Tree:
  C = {}
  N, D = None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def exe(s):
    L = [-1] * N
    A = [0] * N
    for p, x in px:
      p -= 1
      A[p] += x
    S = [0]
    while S != []:
      t = S.pop()
      L[t] = 1
      for i in s.C[t]:
        if L[i] == -1:
          L[i] = 1
          A[i] += A[t]
          S.append(i)
    for i in range(N):
      print(A[i], end = " ")

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.setC(a, b)

T.exe()

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
import queue


def solve(n, q, a, b, p, x):
    counter = [0] * n
    q_sum = [0] * n
    for i in range(q):
        q_sum[p[i]] += x[i]
    # pprint(q_sum)

    edges = {}
    for i in range(n-1):
        if a[i] not in edges:
            edges[a[i]] = []
        edges[a[i]].append(b[i])
    # pprint(edges)

    counter[0] = q_sum[0]
    children = queue.Queue()
    for child in edges[0]:
        counter[child] = q_sum[0]
        children.put(child)
    while not children.empty():
        child = children.get()
        counter[child] += q_sum[child]
        # print("child")
        # print(child, counter[child])
        if child in edges:
            for c in edges[child]:
                counter[c] = counter[child]
                # print("c")
                # print(c, counter[c])
                children.put(c)

    print(" ".join(list(map(str, counter))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    a = []
    b = []
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        a.append(a_i - 1)
        b.append(b_i - 1)

    p = []
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p.append(p_i-1)
        x.append(x_i)
    solve(n, q, a, b, p, x)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000) 

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

ans=[0]*N
results = {}
for word in a:
    results.setdefault(word[0], []).append(word[1])

for i in b:
    ans[i[0]-1] += i[1]

def sumup(ne):
    global ans
    if ne in results:    
        for k in results[ne]:
            ans[k-1] += ans[ne-1]
            sumup(k)

sumup(1)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:

import sys

sys.setrecursionlimit(10**6)    # 再起の深さがデフォルトだと、 glaph_2_tree で実行時エラー
                                # 再起の深さを十分にとると、実行時間がかかりすぎる


def count_add(info_lst, pi_xi_sum_lst, output_lst, current_node, adding):
    output_lst[current_node] += adding
    for i in info_lst[current_node]:   #先の枝についても再帰
        adding += pi_xi_sum_lst[i]
        count_add(info_lst, pi_xi_sum_lst, output_lst, i, adding)
        adding -= pi_xi_sum_lst[i]

def glaph_2_tree(info_lst, passed_place, current_node):
    next_nodes_lst = info_lst[current_node][:]

    for next_node in next_nodes_lst:
        if passed_place[next_node]: # 通ったことがあったら、
            info_lst[current_node].remove(next_node)
        else:
            passed_place[next_node] = True
            glaph_2_tree(info_lst, passed_place, next_node)
            passed_place[next_node] = False
    passed_place[next_node] = True

N, Q = map(int, input().split())
info_lst = [[] for _ in range(N+1)]
for _ in range(N-1): # 10**5 
    ai, bi = map(int, input().split())
    info_lst[ai].append(bi)
    info_lst[bi].append(ai)

passed_place = [False] * (N+1)
passed_place[1] = True
#########
glaph_2_tree(info_lst, passed_place, 1) # 10**5 ？　それより大きい疑惑
#########

pi_xi_sum_lst = [0]*(N+1)
for _ in range(Q): # 10**5
    pi, xi = map(int, input().split())
    pi_xi_sum_lst[pi] += xi

output_lst = [0]*(N+1)
count_add(info_lst, pi_xi_sum_lst, output_lst, current_node=1, adding=pi_xi_sum_lst[1]) # ここじゃない
output_str = ""
for i in range(1, N+1):
    output_str += str(output_lst[i]) + " "

print(output_str)

Submission status: Time Limit Exceeded

Solution code:
#入力n,q,の受け取り
n,q = map(int, input().split())

#ab[i]には頂点iにつながる頂点たちが列挙されている
#ただし、最後の数字は各頂点以下に加えるxの値
ab = [0]*n
for i in range(n):
    ab[i] = []
for i in range(n-1):
    inp = list(map(int, input().split()))
    inp.sort()
    ab[inp[0]-1].append(inp[1])
for i in range(n):
    ab[i].append(0)

#入力p,xの受け取り
for i in range(q):
    px = list(map(int, input().split()))
    ab[px[0]-1][-1] += px[1]

#あとは答えを出して行って終わり
for i in range(n):
    len_ = len(ab[i])-1
    for j in range(len_):
        ab[ ab[i][j]-1 ][-1] += ab[i][-1]
ans = [0]*n
for i in range(n):
    ans[i] = str(ab[i][-1])
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
i = 1
AB = list()
while i <= N-1:
    AB.append(list(map(int,input().split())))
    i += 1

i = 1
PX = list()
while i <= Q:
    PX.append(list(map(int,input().split())))
    i += 1

V = [0 for i in range(N)]

level = 0
tree = [[1]]
while AB:
    i = 0
    tree.append([])
    delis = list()
    for a, b in AB:
        if a in tree[level]:
            tree[level+1].append(b)
            delis.append(i)
        if b in tree[level]:
            tree[level+1].append(a)
            delis.append(i)
        i += 1

    level += 1
    for j in delis:
        AB[j] = 0
    AB = [i for i in AB if i != 0]


for p, x in PX:
    i = 0
    for t in tree:
        if p in t:
            break
        i+=1

    V[p-1] += x
    i += 1
    while i < len(tree):
        t = tree[i]
        for n in t:
            V[n-1] += x
        i+=1
print(' '.join(map(str,V)))


# print(T)
#
# j = 0
# for p,x in PX:
#     if p in AB[j]:
#         T[p-1] += x

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int,input().split())
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] += xi
sp = [0 for i in range(n)]
s = [0]
visited = [False for i in range(n)]
while len(s) > 0:
    x = s.pop(0)
    visited[x] = True
    sp[x] += px[x]
    for xc in d[x]:
        if not visited[xc]:
            s.append(xc)
            sp[xc] += sp[x]
for i in range(n):
    print(sp[i])