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:
from collections import deque

# BFSで通す
N, Q = map(int, input().split())  # N頂点, Q個の命令

G = [[] for _ in range(N)]
count = [0]*N
for i in range(N-1):  # 辺はN-1本
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)

for i in range(Q):  # Q個の操作について
    p, x = map(int, input().split())
    count[p-1] += x

q = deque([0])
flag = [False]*N

while len(q):
    v = q.pop()
    flag[v] = True
    for e in G[v]:  # vを親にもつノードについてループを回す
        if flag[e]:  # 頂点eに到達済みであれば
            continue
        count[e] += count[v]  # それぞれの子たちに親の値を伝播させる
        q.append(e)

print(*count)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)

#print(tree_index)


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

def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur]
      dfs(chl, cur)
dfs(0, -1)
print(*ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
G=[[] 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)
imos=[0]*n
count=[-1]*n
for i in range(q):
    p,x=map(int,input().split())
    imos[p-1]+=x
stack=[(0,0)]
while len(stack)>0:
    now=stack.pop()
    x=now[0]
    y=now[1]
    c=y+imos[x]
    count[x]=c
    for i in G[x]:
        if count[i]==-1:
            stack.append((i,c))
for i in count:
    print(i,end='')
    print(' ',end='')

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


# 親に付いている重み
r = [0,] * (N+1)
for p, x in W:
    r[p] += x



# 木の隣接関係
M = [[] for _ in range(N+1)]
for g in G:
    M[g[0]].append(g[1])
    M[g[1]].append(g[0])

# print(M)

# 木の親子関係
P = [[] for _ in range(N+1)]
visited = [0,] * (N+1)

def dfs(start):
    q = []
    q.append(start)
    while q:
        now = q.pop()
        visited[now] = 1
        for child in M[now]:
            if not visited[child]:
                r[child] += r[now]
                q.append(child)


dfs(1)

print(*r[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200005) 
input = sys.stdin.readline
n, q = map(int, input().split())
to = [[] for i in range(n)]
ans = [0 for i in range(n)]
def dfs(v, p = -1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)
for i in range(n - 1):
    a, b = map(int, input().split())
    to[a - 1].append(b - 1)
    to[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    ans[p - 1] += x
dfs(0)
print(*ans)

Submission status: Accepted

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

Cnt = [0 for i in range(N+1)]
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) #親ノードの保存意味ある？
for i in range(Q):
    p,x = map(int,input().split())
    Cnt[p] += x

q = collections.deque()
q.append(1)
flag = [False for i in range(N+1)]
while q:
    v = q.pop()
    flag[v] = True
    for i in G[v]:
        if flag[i]:
            continue
        Cnt[i] += Cnt[v]
        q.append(i)

print(*Cnt[1:])

Submission status: Accepted

Solution code:
from sys import stdin
def main():
  from builtins import int, map, range
  readline = stdin.readline
  n, q = map(int, readline().split())
  values = [0] * n
  links = [[] for _ in range(n)]
  for _ in range(n - 1):
    a, b = map(int, readline().split())
    links[a - 1].append(b - 1)
    links[b - 1].append(a - 1)
  for _ in range(q):
    p, x = map(int, readline().split())
    values[p - 1] += x
  s = [(0, -1)]
  while s:
    i, p = s.pop()
    for j in links[i]:
      if j == p:
        continue
      values[j] += values[i]
      s.append((j, i))
  print(*values)
main()

Submission status: Accepted

Solution code:
from sys import stdin
def main():
  from builtins import int, map, range
  readline = stdin.readline
  n, q = map(int, readline().split())
  values = [0] * n
  links = [[] for _ in range(n)]
  for _ in range(n - 1):
    a, b = map(int, readline().split())
    links[a - 1].append(b - 1)
    links[b - 1].append(a - 1)
  for _ in range(q):
    p, x = map(int, readline().split())
    values[p - 1] += x
  q = [(0, -1)]
  while q:
    i, p = q.pop()
    for j in links[i]:
      if j == p:
        continue
      values[j] += values[i]
      q.append((j, i))
  print(*values)
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N, Q = map(int, input().split())

AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

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

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

def dfs(v, parent):  
  for i in graph[v]:
    if i == parent:
      continue
    value[i] += value[v]
    dfs(i, v)

dfs(1, 0)    
ans = ' '.join(map(str, value[1:]))
print(ans)

Submission status: Accepted

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

# 隣接グラフ
to=[[] for i in range(n)] 
ans=[0 for i in range(n)]


# 深さ優先探索(再帰)
def dfs(v, p=-1):
    global ans
    for u in to[v]:
        if u==p:
            continue
        ans[u]+=ans[v]
        dfs(u,v)

# 深さ優先探索(ループ)
def dfs2():
    global ans
    queue=list()
    visit=dict()

    queue.append(0)
    for v in queue:
        visit.setdefault(v,True)
        for u in to[v]:
            if u in visit:
                continue
            ans[u]+=ans[v]
            queue.append(u)

# 隣接グラフ作成
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)

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

#dfs(0)
dfs2()

for i in ans:
    print(i)

Submission status: Accepted

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

def main():
    N, Q = map(int, input().split())
    E = [[] for i in range(N+1)]
    counter = [0] * (N+1)

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

    for i in range(Q):
        # 頂点p を根とする部分木に含まれるカウンターにxを足す
        p, x = map(int, input().split())
        counter[p] += x

    queue = []

    parent = [1]
    def mktree(v, parent, E):
        children = E[v]
        children.remove(parent)
        for child in children:
            mktree(child, v, E)

    while parent:
        p = parent.pop()
        for child in E[p]:
            E[child].remove(p)
            parent.append(child)

    def get(v, children, counter):
        c = counter[v]
        for child in children[v]:
            counter[child] += c
            get(child, children, counter)
    """
    parent = [1]
    while parent:
        p = parent.pop()
        c = counter[p]
        for child in E[p]:
            counter[child] += c
            parent.append(child)
    """
    get(1, E, counter)
    print(" ".join(str(x) for x in counter[1:]))

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(2*10**5)
    N, Q = map(int, input().split())
    E = [[] for i in range(N+1)]
    counter = [0] * (N+1)

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

    for i in range(Q):
        # 頂点p を根とする部分木に含まれるカウンターにxを足す
        p, x = map(int, input().split())
        counter[p] += x

    queue = []

    parent = [1]
    def mktree(v, parent, E):
        children = E[v]
        children.remove(parent)
        for child in children:
            mktree(child, v, E)

    while parent:
        p = parent.pop()
        for child in E[p]:
            E[child].remove(p)
            parent.append(child)

    def get(v, children, counter):
        c = counter[v]
        for child in children[v]:
            counter[child] += c
            get(child, children, counter)

    parent = [1]
    while parent:
        p = parent.pop()
        c = counter[p]
        for child in E[p]:
            counter[child] += c
            parent.append(child)

    print(" ".join(str(x) for x in counter[1:]))

main()

Submission status: Accepted

Solution code:
import sys, collections

def solve():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    edge = [[] for i in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

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

    q = collections.deque()
    q.append(0)
    while q:
        now = q.popleft()
        if not visited[now]:
            visited[now] = True
            cnow = counter[now]
            for next in edge[now]:
                if not visited[next]:
                    counter[next] += cnow
                    q.append(next)

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

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

sys.setrecursionlimit(10**6)

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

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

seen = [False] * (N + 1)
ans = [0] * (N + 1)


def dfs(e, v, x):
    seen[v] = True
    ans[v] += x
    for next_v in e[v]:
        if seen[next_v]:
            continue
        else:
            dfs(e, next_v, x + q[next_v])


dfs(e, 1, q[1])
print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque

n,q = input().split()
n = int(n)
q = int(q)
T = [0] * (n+1)

to = [[] for i in range(n+1)]
cnt = [0] * (n)
for i in range(1,n):
    a,b = [int(j) for j in input().split()]
    to[a].append(b)
    to[b].append(a)
for i in range(1,q+1):
    P,X = [int(j) for j in input().split()]
    T[P] += X
NIL = -1

q =deque()
q.append((1,0,NIL))
while len(q)>0:
    p,x,prev = q.pop()
    x += T[p]
    cnt[p-1] = x
    for i in to[p]:
        if i != prev:
            q.append((i,x,p))
print(*cnt)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
G=[[] 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)
X=[0 for i in range(N)]
for i in range(Q):
    p,x=map(int,input().split())
    X[p-1]+=x
q=[0]
reached=[0 for i in range(N)]
ans=[0 for i in range(N)]
#print(X)
while(len(q)>0):
    r=q.pop()
    ans[r]+=X[r]
    reached[r]=1
    for p in G[r]:
        if reached[p]==0:
            ans[p]+=ans[r]
            q.append(p)
print(*ans)

Submission status: Accepted

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

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

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

value = [0] * (N+1)
for p,x in PX:
    value[p] += x
    
q = [(1,0)]
while q:
    x,parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y,x))

answer = ' '.join(map(str,value[1:]))
print(answer)

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

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

value = [0] * (N+1)
for p,x in PX:
    value[p] += x
    
q = [(1,0)]
while q:
    x,parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y,x))

answer = ' '.join(map(str,value[1:]))
print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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

lazy = [0]*(n+1)

graph = defaultdict(lambda:list([]))
for i in range(n-1):
	x, y = map(int, sys.stdin.readline().split())
	# x, y = arr[i]
	graph[x].append(y)
	graph[y].append(x)

def dfs(src):
	visited ={src, }
	stack = [src]

	while stack:
		v = stack.pop()
		for next_v in graph[v]:
			if not next_v in visited:
				visited.add(next_v)
				lazy[next_v] += lazy[v]
				stack.append(next_v)

# queries = [(1, 1), (2, 2)]
for i in range(q):
	idx, val = map(int, sys.stdin.readline().split())
	# idx, val = queries[i]
	lazy[idx] += val
dfs(1)
print(*lazy[1:])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/submissions/6992193
from collections import deque
 
N, Q = map(int, input().split())
to = [[] for _ in range(N)]

# to: つながっているノード番号を保持
for _ in range(N - 1):
    a, b = map(int, input().split())
    to[a - 1].append(b - 1)
    to[b - 1].append(a - 1)

# P: 各ノード番号にxの和を保持（後に累積和をとる準備）
P = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    P[p - 1] += x

# cnt: 累積和の計算用 
cnt = [0] * N

# rootから順に累積和をとっていく
q = deque()
q.append((0, 0, -1))  # ダミーの値で初期化
while len(q):
    p, x, prev = q.pop()  # スタックとして使用
    x += P[p]
    cnt[p] = x
    for b in to[p]:  # つながっているノードにもxを加算
        if b != prev:
            q.append((b, x, p))  # b: xを加算するノード, p: xが親（本ループですでに加算したノード）に波及して来ないようにするための制御用の値
print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
N, Q = map(int, input().split())
C = [0]* N
D = defaultdict(set)
for i in range(N-1):
  a, b = map(int, input().split())
  D[a-1].add(b-1)
  D[b-1].add(a-1)
for i in range(Q):
  p, x = map(int, input().split())
  C[p-1] += x

Q = deque([])
Q.append(0)
vstd = set()

while len(Q)>0:
  a = Q.popleft()
  vstd.add(a)
  for b in D[a]:
    if b in vstd:
      continue
    C[b] += C[a]
    Q.append(b)

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

Submission status: Accepted

Solution code:
from collections import deque

def solve(n, q, a, b, p, x):
    E = [[] for i in range(n+1)]
    for a_i, b_i in zip(a, b):
        E[a_i].append(b_i)
        E[b_i].append(a_i)
    res = {i: 0 for i in range(1, n+1)}
    for j in range(q):
        res[p[j]] += x[j]
    used = [False] * (n+1)
    used[1] = True
    que = deque([1])
    while que:
        u = que.popleft()
        for v in E[u]:
            if not used[v]:
                used[v] = True
                res[v] += res[u]
                que.append(v)
    return " ".join(map(str, [res[i] for i in range(1,n+1)]))

n, q = map(int, input().split())
a = [0] * (n-1)
b = [0] * (n-1)
for i in range(n-1):
    a[i], b[i] = map(int, input().split())
p = [0] * q
x = [0] * q
for j in range(q):
    p[j], x[j] = map(int, input().split())
print(solve(n, q, a, b, p, x))

Submission status: Accepted

Solution code:
import collections
N, Q = map(int, input().split())
counts = [0] * (N + 1)
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)
for _ in range(Q):
  p, x = map(int, input().split())
  counts[p] += x
visited = [0] * (N + 1)
queue = collections.deque()
queue.append(1)
while queue:
  v = queue.pop()
  visited[v] = 1
  x = counts[v]
  for child in T[v]:
    if visited[child] == 1:
      continue
    counts[child] += x
    queue.append(child)
print(*counts[1:])

Submission status: Accepted

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

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

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

value = [0] * (N+1)
for p,x in PX:
    value[p] += x
    
q = [(1,0)]
while q:
    x,parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y,x))

answer = ' '.join(map(str,value[1:]))
print(answer)

Submission status: Accepted

Solution code:
(n,q),*t=[map(int,t.split())for t in open(0)]
s=[0]
d=s*n
f=s*n
e=[[]for _ in d]
for a,b in t:
 if~-n:n-=1;e[a-1]+=b-1,;e[b-1]+=a-1,
 else:d[a-1]+=b
while s:
 v=s.pop();f[v]=-1
 for w in e[v]:
  if~f[w]:d[w]+=d[v];s+=w,
print(*d)

Submission status: Accepted

Solution code:
(n,q),*t=[map(int,t.split())for t in open(0)]
s=[0]
d=s*n
f=s*n
e=[[]for _ in d]
for t in t:
 a,b=t
 if~-n:n-=1;e[a-1]+=b-1,;e[b-1]+=a-1,
 else:d[a-1]+=b
while s:
 v=s.pop();f[v]=-1
 for w in e[v]:
  if~f[w]:d[w]+=d[v];s+=w,
print(*d)

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:
from collections import deque

N, Q = list(map(int, input().split()))
edges = {n:[] for n in range(N+1)}
nodes = [0 for _ in range(N+1)]
cr = deque()

# 経路
for n in range(N-1):
    a, b = list(map(int, input().split()))
    edges[a].append(b)
    edges[b].append(a)

# 各ノードの点数
for q in range(Q):
    p, x = list(map(int, input().split()))
    nodes[p] += x

# 各ノードを通ったことを覚えておく
flags = [False]*(N+1)

# ルートから探索
cr.append(1)
flags[1] = True

# ルートから葉っぱまで点数を行き渡らせる
while cr:
    c = cr.popleft()
    flags[c] = True

    # 続く幹がないならば飛ばす
    if not edges[c]:
        continue

    # 幹に点数を与え、幹を伸ばす
    pts = nodes[c]
    for trunk in edges[c]:
        if not flags[trunk]:
            flags[trunk] = True
            nodes[trunk] += pts
            cr.append(trunk)

print(*nodes[1:])

Submission status: Accepted

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

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

for i,j in AB:
  g[i].append(j)
  g[j].append(i)
 
def BTS(a, b):
  for i in g[a]:
    if i == b:
      continue
    C[i-1] += C[a-1]
    BTS(i,a)
    
BTS(1,-1)
 
print(*C)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
ans = [0]*N

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

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

judge = [False]*N
judge[0] = True
queue = [0]
while queue:
    a = queue.pop()
    for i in G[a]:
        if not judge[i]:
            judge[i] = True
            ans[i] += ans[a]
            if G[i]:
                queue.append(i)

print(*ans)

Submission status: Accepted

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

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

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

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

ans = [0] * n


def f(par, node, count):
    count += counter[node]
    ans[node] = count
    for n in edges[node]:
        if n == par:
            continue
        f(node, n, count)


f(-1, 0, 0)
print(*ans)

Submission status: Accepted

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


def dfs(v, p):
    for next_v in g[v]:
        if next_v == p:
            continue
        cnt[next_v] += cnt[v]
        dfs(next_v, v)


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

g = {i:[] for i in range(N+1)}
cnt = {i:0 for i in range(N+1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

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

dfs(1, -1)

print(*list(cnt.values())[1:])

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


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

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

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

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


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

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

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

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


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

    for _ in range(N - 1):
        a, b = map(int, input().split())
        con[a - 1].append(b - 1)
        con[b - 1].append(a - 1)
        
    for _ in range(Q):
        p, v = map(int, input().split())
        ans[p-1] += v

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


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

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

    for op in ops:
        node = op[0] - 1
        pnt = op[1]
        ans[node] += pnt

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


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

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

    for op in ops:
        node = op[0] - 1
        pnt = op[1]
        ans[node] += pnt

    stack = deque()
    stack.append((0, -1))

    while stack:
        st = stack.pop()
        node, parent = st[0], st[1]
        children = edge[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stack.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N, Q = map(int, input().split())
    edge = [[] for i in range(N)]
    ops = []
    ans = [0] * N
    
    for _ in range(N - 1):
        a, b = map(int, input().split())
        edge[a - 1].append(b - 1)
        edge[b - 1].append(a - 1)
    for _ in range(Q):
        ops.append(tuple(map(int, input().split())))
    
    for op in ops:
        node = op[0] - 1
        pnt = op[1]
        ans[node] += pnt
    
    stack = deque()
    stack.append((0, -1))
    
    while stack:
        st = stack.pop()
        node, parent = st[0], st[1]
        children = edge[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stack.append((child, node))
    
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, Q = map(int, input().split())
edge = [[] for i in range(N)]
ops = []
ans = [0] * N

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

for op in ops:
    node = op[0] - 1
    pnt = op[1]
    ans[node] += pnt

stack = deque()
stack.append((0, -1))

while stack:
    st = stack.pop()
    node, parent = st[0], st[1]
    children = edge[node]
    for child in children:
        if child == parent:
            continue
        ans[child] += ans[node]
        stack.append((child, node))

print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, Q = map(int, input().split())
 
tree = defaultdict(set)
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)

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

cur_node = set()
cur_node.add(1)
pre_node = set()
while len(cur_node) != 0:
  next_node = set()
  for ni in cur_node:
    for nj in tree[ni]:
      if nj in pre_node:
        continue
      counter[nj] += counter[ni]
      next_node.add(nj)
  pre_node = cur_node
  cur_node = next_node
print(' '.join((str(counter[i]) for i in range(1, N + 1))))

Submission status: Accepted

Solution code:
from collections import deque

N, Q = map(int, input().split())
edge = [[] for i in range(N)]
ops = []
ans = [0] * N

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

for op in ops:
    node = op[0]-1
    pnt = op[1]
    ans[node] += pnt

stack = deque()
stack.append((0, -1))

while stack:
    st = stack.pop()
    node, parent = st[0], st[1]
    children = edge[node]
    for child in children:
        if child == parent:
            continue
        ans[child] += ans[node]
        stack.append((child, node))

print(*ans)