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: Accepted

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


N, M = map(int, input().split())
G = [[] for _ in [0]*N]
for _ in [0]*(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

add = [0]*N
for _ in [0]*M:
    p, x = map(int, input().split())
    p -= 1
    add[p] += x
counter = [0]*N


def dfs(v, p, x):
    counter[v] = x
    for u in G[v]:
        if u == p:
            continue
        dfs(u, v, x+add[u])


dfs(0, -1, add[0])

print(*counter)

Submission status: Accepted

Solution code:
from collections import deque

N, Q = map(int, input().split())

# N個の頂点について、隣接要素を格納
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

# 各piにxiを追加しておく（子要素は見ない）
points = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    points[p - 1] += x

# 答え
result = [0] * N

# 訪れたら1, まだ訪れていなかったら0
visited = [0] * N
visited[0] = 1

# [ [頂点、累計ポイント], [頂点、累計ポイント], ...]
dq = deque([[0, points[0]]])

# 深さ優先探索(DFS)
while dq:
    node, count = dq.pop()
    result[node] = count
    # 今見ている頂点が持つ隣接要素について
    for ni in G[node]:
        # 未訪問の要素がある場合
        if visited[ni] != 1:
            visited[ni] = 1
            dq.append([ni, points[ni] + count])

print(*result)

Submission status: Accepted

Solution code:
N,Q = [int(i) for i in input().split()]
graph = [[] for _ in range(N+1)]
ans = [0] * (N+1)
for i in range(N-1):
    a,b = [int(j) for j in input().split()]
    graph[a].append(b)
    graph[b].append(a)
for i in range(Q):
    pa,xaa = [int(j) for j in input().split()]
    ans[pa] += xaa

seen = [False] * (N+1)

import collections
from collections import deque
que = deque()
que.append(1)
seen[1] = True
while len(que) != 0:
    x = que.popleft()
    seta = set(graph[x])
    for i in seta:
        if seen[i]:
            continue
        ans[i] += ans[x]
        que.append(i)
        seen[i] = True
print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque, defaultdict


def main():
    n, q = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(n - 1)]
    PX = [[int(e) for e in input().split()] for i in range(q)]

    G = defaultdict(set)
    for a, b in AB:
        G[a].add(b)
        G[b].add(a)

    Ans = [0] * (n + 1)
    for p, x in PX:
        Ans[p] += x

    Q = deque([1])
    Visited = [False] * (n + 1)
    Visited[1] = True
    while len(Q) > 0:
        v = Q.popleft()
        for vc in G[v]:
            if Visited[vc]:
                continue

            Ans[vc] += Ans[v]
            Q.append(vc)
            Visited[vc] = True

    print(*Ans[1:])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)

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

from collections import deque
que = deque([[0, counter[0]]])
visited = [0] * n
visited[0] = 1
while que:
    node, point = que.pop()
    for nn in G[node]:
        if visited[nn] == 1:
            continue
        visited[nn] = 1
        counter[nn] += point
        que.append([nn, counter[nn]]) 

print(*counter)

Submission status: Accepted

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

from collections import deque
st = deque([[0, points[0]]])
result = ['0'] * N
visited = [0] * N
visited[0] = 1
while st:
    idx, count = st.pop()
    result[idx] = str(count)
    for ni in G[idx]:
        if visited[ni] != 1:
            visited[ni] = 1
            st.append([ni, count+points[ni]])
            
print(" ".join(result))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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)]
#print(AB)

C = [[] for i in range(n)] #Cはグラフ表示
for a,b in AB:
  C[b-1].append(a-1)
  C[a-1].append(b-1)
Q = [0] * n
for p,x in PX:
  Q[p-1] += x
#print(Q)
  
STACK = [0]
VISITED = [0] * n
ANS = [0] * n
ANS[0] = Q[0]
VISITED[0] = 1

while STACK:
  d = STACK.pop()
  for i in C[d]:
    if VISITED[i]:
      continue
    else:
      VISITED[i] = 1
      ANS[i] = ANS[d] + Q[i]
      STACK.append(i)

print(*ANS)

Submission status: Accepted

Solution code:
from collections import deque
N, Q = map(int, input().split())
graph = [[] for _ in range(N)]

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

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

que = deque([0])
parent = [-1]*N
while que:
    node = que.pop()
    for v in graph[node]:
        if v == parent[node]:
            continue
        parent[v] = node
        que.append(v)
        ans[v] += ans[node] 

print(*ans)

Submission status: Accepted

Solution code:

from collections import deque


from collections import deque

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)]

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

ctr = [0] * (N + 1)
for p, x in Y:
    ctr[p] += x

ans = [0] * (N + 1)
ans[1] = ctr[1]
visited = [False] * (N + 1)
visited[1] = True
q = deque([1])
while q:
    u = q.popleft()
    for v in tree[u]:
        if not visited[v]:
            ans[v] = ans[u] + ctr[v]
            visited[v] = True
            q.append(v)

print(*ans[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
 
N, Q = map(int, input().split())
graph = [[] for i in range(N)]
cnt = [0]*N

# 入力しながらグラフを作成
for i in range(N-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  graph[a].append(b)
  graph[b].append(a)

# 初期値を設定
for i in range(Q):
  p, x = map(int, input().split())
  cnt[p-1] += x

v = [False]*N

# stack=[]
def dfs(n,prv):
  # stack.append(n)
  if v[n]: return
  cnt[n] += prv
  v[n] = True
  for nv in graph[n]:
    dfs(nv, cnt[n])
   
dfs(0,0)
print(*cnt)
# print(stack)

Submission status: Accepted

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

graph = [[] for _ in range(n+1)]
for i, j in li_nq:
    graph[i].append(j)
    graph[j].append(i)

ans = [0 for _ in range(n+1)]
for i, j in li_px:
    ans[i] += j

check_list = [None] * (n+1)
stack = [1]

while stack:
    num = stack.pop()
    for i in graph[num]:
        if check_list[num] == i:
            continue
        stack.append(i)
        ans[i] += ans[num]
        check_list[i] = num

print(*ans[1:])

Submission status: Accepted

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
import sys

sys.setrecursionlimit(500000)

visited = set()

n,q = nm()

tval = [0]*n
t = [[] for _ in range(n)]

for i in range(n-1):
    a,b = nm()
    t[a-1].append(b-1)
    t[b-1].append(a-1)

for i in range(q):
    p,x = nm()
    tval[p-1] += x

ans = [0]*n
def dfs(num,val):
    visited.add(num)
    now = val+tval[num]
    ans[num] = now
    for nn in t[num]:
        if nn not in visited:
            dfs(nn,now)

dfs(0,0)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
tree=[deque([]) for _ in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
ans=[0]*(n+1)
for i in range(q):
  p,x=map(int,input().split())
  ans[p]+=x
seen=[0]*(n+1)
stack=[]
def dfs():
  stack.append(1)
  seen[1]=1
  while stack:
    s=stack.pop()
    if not tree[s]:
      continue
    for j in range(len(tree[s])):
      g_NO = tree[s].popleft()
      if seen[g_NO]:
        continue
      seen[g_NO] = 1
      stack.append(g_NO)
      ans[g_NO] += ans[s]


dfs()
print(*ans[1:])

Submission status: Accepted

Solution code:
import sys, collections
input = sys.stdin.readline

n, q = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
add = [0 for i in range(n + 1)]
for i in range(q):
    p, x = map(int, input().split())
    add[p] += x
flag = [False for i in range(n + 1)]
check = collections.deque([1])
while check:
    test = check.popleft()
    flag[test] = True
    num_list = graph[test]
    for i in num_list:
        if flag[i] == True:
            pass
        else:
            add[i] += add[test]
            check.append(i)
for i in range(n):
    print(add[i + 1], end = " ")
print()

Submission status: Accepted

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

n, q = map(int, input().split())
Graph = [[] for i in range(n)]
seen = [False]*n
point = [0]*n


def dfs(g, v, p):
    # vを訪問済みにする
    seen[v] = True
    if p != -1: point[v] += point[p]

    # vから行ける各頂点について
    for next_v in g[v]:

        # next_vが訪問済みだったらスルー
        if seen[next_v]: continue

        # 再帰的に探索
        dfs(g, next_v, v)


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

    # 無向グラフを想定
    Graph[a].append(b)
    Graph[b].append(a)


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


dfs(Graph, 0, -1)


print(*point)

Submission status: Accepted

Solution code:
from collections import deque
N,Q=map(int,input().split())
tree=[[] for i in range(N+1)]
counter=[0]*(N+1)
for i in range(N-1):
  a,b=map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
for i in range(Q):
  p,x=map(int,input().split())
  counter[p]+=x
d=deque([1])
parent=[0]*(N+1)
while d:
  a=d.popleft()
  for b in tree[a]:
    if b!=parent[a]:
      counter[b]+=counter[a]
      parent[b]=a
      d.append(b)
print(*counter[1:])

Submission status: Accepted

Solution code:
from collections import deque
N,Q = map(int,input().split())
tree = [[] for _ in range(N+1)]
counter = [0]*(N+1)
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
for i in range(Q):
    p,x = map(int,input().split())
    counter[p] += x
parent = [0]*(N+1)
d = deque([1])

while d:
    a = d.popleft()
    for b in tree[a]:
        if parent[a] == b:
            continue
        counter[b] += counter[a]
        parent[b] = a
        d.append(b)

print(*counter[1:])

Submission status: Accepted

Solution code:
from collections import deque
N,Q = map(int,input().split())
tree = [[] for _ in range(N+1)]
counter = [0]*(N+1)
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
for i in range(Q):
    p,x = map(int,input().split())
    counter[p] += x
already = set()
d = deque([1])

while d:
    a = d.popleft()
    for b in tree[a]:
        if not b in already:
            counter[b] += counter[a]
            d.append(b)
    already.add(a)

print(*counter[1:])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)


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


def main():
    N, Q = map(int, input().split())
    to = [[] for _ in range(N)]
    ans = [0] * N

    for _ in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        to[a].append(b)
        to[b].append(a)
    
    for _ in range(Q):
        p, x = map(int, input().split())
        ans[p-1] += x
    dfs(0, to, ans)
    
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    n, q = map(int, input().split())

    graph = [[] for _ in range(n+1)]

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

    clist = [0]*(n+1)

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

    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 0

    ans = [0]*(n+1)
    d = deque()
    d.append(1)
    ans[1]=clist[1]
    while d:
        v = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            ans[i]=ans[v]+clist[i]
            d.append(i)
    
    ans = ans[1:]
    print(*ans, sep=" ")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

n,q = map(int, input().split())
cnt = [0] * (n+1)
g = [[] for _ in range(n+1)]

for _ in range(n-1):    #隣接リストの生成
    a,b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

for _ in range(q):
    v,val = map(int, input().split())
    cnt[v] += val

q = collections.deque()
q.append(1)
checked = [0]*(n+1)

while q:
    v = q.pop()
    checked[v] = 1
    for u in g[v]:
        if checked[u] == 1:
            continue
        cnt[u] += cnt[v]
        q.append(u)
print(*cnt[1:])

Submission status: Accepted

Solution code:
import sys,collections
input = sys.stdin.readline

N,Q = list(map(int,input().split()))
road = [[] for i in range(N+1)]
for _ in range(N-1):
    a,b = map(int,input().split())
    road[a].append(b)
    road[b].append(a)
point = [0]*(N+1)

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

q = collections.deque([1])
visit = [0]*(N+1)
visit[1]=1

while q:
    now = q.pop()
    for i in road[now]:
        if visit[i] == 0:
            q.append(i)
            point[i] += point[now]
            visit[i]=1

print(*point[1:])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, Q = map(int, readline().split())
    AB = list(list(map(int, readline().split())) for _ in range(N-1))
    PX = list(list(map(int, readline().split())) for _ in range(Q))

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

    value = [0] * N
    for p, x in PX:
        value[p-1] += x

    que = deque([0])
    visited = [False]*N
    while que:
        x = que.popleft()
        visited[x] = True
        for y in graph[x]:
            if visited[y]:
                continue
            else:
                value[y] += value[x]
                que.append(y)
    print(' '.join(map(str, value)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N - 1)]
px = [list(map(int, input().split())) for i in range(Q)]
 
root = [[] for i in range(N + 1)]
result = [0 for i in range(N + 1)]
 
for i in range(N - 1):
    a = ab[i][0]
    b = ab[i][1]
    root[a].append(b)
    root[b].append(a)
 
for i in range(Q):
    p = px[i][0]
    x = px[i][1]
    result[p] = result[p] + x
 
 
def dfs(now, prev):
    if len(root[now]) == 0:
        return
    else:
        for i in range(len(root[now])):
            next_point = root[now][i]
            if next_point == prev:
                continue
            else:
                result[next_point] = result[next_point] + result[now]
                dfs(next_point, now)
 
 
dfs(1, -1)
print(*result[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
import sys
def input():
    return sys.stdin.readline()[:-1]
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: Accepted

Solution code:
import sys
input = sys.stdin.readline   #sys.std.readlineのほうが10倍速い
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)]
es = [[] for _ in range(N)]  #グラフ配列

for a,b in AB:
  a -= 1
  b -= 1
  es[a].append(b)
  es[b].append(a)
ps = [0] * N   #処理配列(当該のものをプラスする)
for p,x in PX:
  ps[p-1] += x
  
#print(es)
#print(ps)

ans = [0] * N #回答配列
ans[0] = ps[0]
stack = [0]  #待ち配列
visited = [0] * N #訪れたかどうか配列、最初は0、訪れたら1
visited[0] = 1
while stack: #空であればFalse、中身が入ってればTrueを返す性質
  v = stack.pop()
  for i in es[v]:
    if visited[i]:
      continue
    visited[i] = 1
    ans[i] = ans[v] + ps[i]
    stack.append(i)
print(*ans)

Submission status: Accepted

Solution code:
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

    n, q = map(int, input().split())
    adj = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        adj[a].append(b)
        adj[b].append(a)
    ans = [0]*n
    for _ in range(q):
        p, x = map(int, input().split())
        p -=1
        ans[p] += x
    
    from collections import deque
    que = deque([0])
    parent = [-1]*n
    while que:
        node = que.pop()
        for v in adj[node]:
            if v == parent[node]:
                continue
            parent[v] = node
            que.append(v)
            ans[v] += ans[node]
    for a in ans:
        print(a)

        

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
G = [[] for _ 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)

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

from collections import deque
visited = [-1]*N
q = deque()
q.append(0)

while q:
    cur = q.popleft()
    visited[cur] = 0
    for nx in G[cur]:
        if visited[nx] != -1: continue
        counter[nx] += counter[cur]
        q.append(nx)

print(*counter)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
cnt=[0]*(n+1)
g=[[] for _ in range(n+1)]
for _ in range(n-1): #木グラフの隣接リストを作成
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
for _ in range(q): #各頂点についてcount[v]を計算
 v,val=map(int,input().split())
 cnt[v]+=val
q=[]
q.append(1) #DFSのスタックによる実装、まずスタックに始点1を積む
checked=[0]*(n+1) #各頂点を見たかどうかのフラグを持っておく
while q:
 v=q.pop()
 checked[v]=1 #頂点を見たかどうかのフラグを更新する
 for u in g[v]:
   if checked[u]==1: #vの子ノードuについて、まだ見ていない頂点であればcount[u]をcount[u]+=count[v]として更新する
     continue
   cnt[u]+=cnt[v]
   q.append(u) #スタックに子ノードuを積む
print(*cnt[1:]) #各頂点のcountが答えとなる

Submission status: Accepted

Solution code:
from collections import deque

N, Q = [int(x) for x in input().split()]

tree = {}
result = [0] * N

for _ in range(N-1):
    a, b = [int(x) - 1 for x in 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]


add = [0] * N
for _ in range(Q):
    p, x = [int(x) for x in input().split()]

    add[p-1] += x

queue = deque()
queue.appendleft((0, add[0]))

finished = set()

while queue:
    target = queue.pop()
    node = target[0]
    count = target[1]

    result[node] = count
    finished.add(node)

    if node in tree:
        for next_node in tree[node]:
            if not next_node in finished:
                queue.appendleft((next_node, count + add[next_node]))

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

Submission status: Accepted

Solution code:
from collections import deque
N,Q=map(int,input().split())

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

ans=[0]*N
for i in range(Q):
    p,x=map(int,input().split())
    ans[p-1] += x
    
q=deque([0])
visited=set()
while q:
    now =q.popleft()
    visited.add(now)
    for n in T[now]:
        if n not in visited:
            ans[n] += ans[now]
            q.append(n)
print(*ans)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,k=f()
g=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1]+=[b-1]
  g[b-1]+=[a-1]
l=[0]*n
for _ in range(k):
  p,x=f()
  l[p-1]+=x
u=[0]*n
q=[0]
while q:
  v=q.pop()
  u[v]=1
  for c in g[v]:
    if u[c]: continue
    l[c]+=l[v]
    q+=[c]
print(*l)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
f=lambda:map(int,input().split())
n,k=f()
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=f()
  g[a-1]+=[b-1]
  g[b-1]+=[a-1]
l=[0]*n
for _ in range(k):
  p,x=f()
  l[p-1]+=x
def dfs(v,p=-1):
  for c in g[v]:
    if c==p: continue
    l[c]+=l[v]
    dfs(c,v)
dfs(0)
print(*l)

Submission status: Accepted

Solution code:
(n,q),*abpx = [list(map(int, s.split())) for s in open(0)]
ab,px = abpx[:n-1],abpx[n-1:]

from collections import defaultdict, deque
add = defaultdict(int)

for p,x in px:
    add[p] += x

links = defaultdict(set)

for a,b in ab:
    links[a].add(b)
    links[b].add(a)

passed = set()

dq = deque()
dq.append((0,1))

ans = {}

while dq:
    to_add, cur = dq.popleft()
    tmp = to_add + add[cur]
    ans[cur] = tmp
    for nx in links[cur]:
        links[nx].remove(cur)
        dq.append((tmp, nx))

print(*(ans[i] for i in range(1,n+1)))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
n, q = map(int, input().split())

edges = [[] for _ in range(n)]
for _ in range(n - 1):
    frm, to = map(int, input().split())
    # 0-index
    edges[frm - 1].append(to - 1)
    edges[to - 1].append(frm - 1)


scores = [0] * n
for _ in range(q):
    v, s = map(int, input().split())
    scores[v - 1] += s


stack = [0]
visited = [False] * n
visited[0] = True
while len(stack):
    frm = stack.pop()
    for to in edges[frm]:
        if not visited[to]:
            scores[to] += scores[frm]
            visited[to] = True
            stack.append(to)


print(" ".join([str(w) for w in scores]))

Submission status: Accepted

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

def dfs(G, v, p):
    for nv in G[v]:
        if nv == p:
            continue
        point[nv] += point[v]
        dfs(G, nv, v)

n, q = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(n-1):
    x, y =  map(int, input().split())
    x, y = x-1, y-1
    G[x].append(y)
    G[y].append(x)

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

dfs(G, 0, -1)
print(*point)

Submission status: Accepted

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

def dfs(v, p):
    for nv in G[v]:
        if nv == p:
            continue
        point[nv] += point[v]
        dfs(nv, v)

n, q = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(n-1):
    x, y =  map(int, input().split())
    x, y = x-1, y-1
    G[x].append(y)
    G[y].append(x)

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

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

Submission status: Accepted

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

def dfs(G, v):
    seen[v] = True

    for nv in G[v]:
        if seen[nv]:
            continue
        point[nv] += point[v]
        dfs(G, nv)

n, q = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(n-1):
    x, y =  map(int, input().split())
    x, y = x-1, y-1
    G[x].append(y)
    G[y].append(x)

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

dfs(G, root)
print(*point)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left
MOD = int(1e9)+7
INF = float('inf')


def solve():
    # n, m = [int(x) for x in input().split()]  
    n, q = [int(x) for x in input().split()]  
    g = defaultdict(list)
    cnt = [0] * (n+1)

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

    for _ in range(q):
        v, x = [int(x) for x in input().split()]
        cnt[v] += x
    
    q = deque([(1, 0)])
    w = set([1])
    while q:
        v, val = q.popleft()
        cnt[v] += val
        for to in g[v]:
            if to not in w:
                q.append((to, cnt[v]))
                w.add(to)

    print(*cnt[1:])


    
t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""
a b a
d c d
a b a
"""

Submission status: Accepted

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

N, Q = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)
point = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    point[p-1] += x
q = deque([[0, -1, point[0]]])
done = [-1]*N
while q:
    cur, fr, p = q.popleft()
    done[cur] = p
    for nex in G[cur]:
        if nex == fr: continue
        q.append([nex, cur, p+point[nex]])
ans = []
for i in range(N):
    ans.append(done[i])
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

n, q = map(int, input().split())
eg = [[] for _ in range(n + 1)]

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

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


q = deque()
q.append(1)
seen = {1}
ans = [0] * (n + 1)
ans[1] = cnt[1]
while q:
    v = q.pop()
    for t in eg[v]:
        if t in seen:
            continue
        q.append(t)
        seen.add(t)
        ans[t] = ans[v] + cnt[t]

print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque

n, q = map(int, input().split())
eg = [[] for _ in range(n + 1)]

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

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


q = deque()
q.append(1)
seen = {1}
ans = [0] * (n + 1)
ans[1] = cnt[1]
while len(q) > 0:
    v = q.pop()
    for t in eg[v]:
        if t in seen:
            continue
        q.append(t)
        seen.add(t)
        ans[t] = ans[v] + cnt[t]

print(*ans[1:])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
tree = [[] for _ in range(n)]
point = [0] * n
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

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

stack = [[0, 0, -1]]
while stack:
  v, p, parent = stack.pop()
  point[v] += p
  for child in tree[v]:
    if child == parent:
      continue
    stack.append([child,point[v],v])

print(*point)

Submission status: Accepted

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

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

# tree[i]: i番目の頂点とつながっている頂点（リスト）を入れる
for _ in range(N-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

# x_list[i]: iの配下に足す数を入れる
x_list = [0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    x_list[p-1] += x

ans = [0]*N

def dfs(child, parent):
    ans[child] = ans[parent] + x_list[child]
    for v in tree[child]:
        if v != parent:
            dfs(v, child)

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

Submission status: Accepted

Solution code:
from collections import deque

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)

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

def bfs(s):
    seen = [0 for i in range(N+1)]
    prev = [0 for i in range(N+1)]
    todo = deque([])
    now = s
    seen[now]=1
    todo.append(now)
    while 1:
      if len(todo)==0:break
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          P[b] += P[a]

bfs(1)
print(*P[1:])