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:
# 木全体の根が決まっているのでふつうにbfsでいい気がするが...
# 毎回探索するんじゃなくて、各枝にポイントをつけておいて、探索するときに1回だけ渡して更新していく
# 考え方は累積和
# なんかafter_contestってテストケースでハネられるんだが。。。。。なんだこれ
# i<jのときiのほうが根に近い、というのを決め打ちしても通ってしまう防止らしい
# 回避するべく
# 両方のノードからエッジを貼り(graph[b].append(a))、
# 探索のときに訪問済みの場所は抜くことにした(if node not in used:)

n, q = map(int, input().split())
graph = [[] for _ in range(n)]
points = [0 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)

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

path = [0]
used = set()
used.add(0)
while len(path) > 0:
    cur_node = path.pop()
    cur_point = points[cur_node]
    for node in graph[cur_node]:
        if node not in used:
            used.add(node)
            points[node] += cur_point
            path.append(node)
print(" ".join(list(map(str, points))))

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

 seen=set([0])

 dq=deque()
 dq.append(0)

 while dq:
  x=dq.popleft()
  for i in tree[x]:
#  if cnt[i]==-1:
   if i not in seen:
    seen.add(i)
    dq.append(i)
    cnt[i]+=cnt[x]

 print(*cnt)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

 seen=set([0])

 dq=deque()
 dq.append(0)

 while dq:
  x=dq.popleft()
  for i in tree[x]:
#  if cnt[i]==-1:
   if i not in seen:
    seen.add(i)
    dq.append(i)
    cnt[i]+=cnt[x]

 print(*cnt)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

seen=set([0])

dq=deque()
dq.append(0)

while dq:
 x=dq.popleft()
 for i in tree[x]:
#  if cnt[i]==-1:
  if i not in seen:
   seen.add(i)
   dq.append(i)
   cnt[i]+=cnt[x]

print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

cnt=[-1]*n
cnt[0]=t_cnt[0]

seen=set([0])

dq=deque()
dq.append(0)

while dq:
 x=dq.popleft()
 ref_v=cnt[x]
 for i in tree[x]:
#  if cnt[i]==-1:
  if i not in seen:
   seen.add(i)
   dq.append(i)
   cnt[i]=ref_v+t_cnt[i]

print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

cnt=[-1]*n
cnt[0]=t_cnt[0]

seen=set([0])

dq=deque()
dq.append(0)

while dq:
 x=dq.popleft()
 for i in tree[x]:
#  if cnt[i]==-1:
#  if i in seen:
#   continue
#  else:
   if i not in seen:
    seen.add(i)
    dq.append(i)
    cnt[i]=cnt[x]+t_cnt[i]

print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

cnt=[-1]*n
cnt[0]=t_cnt[0]

seen=set([0])

dq=deque()
dq.append(0)

while dq:
 x=dq.popleft()
 for i in tree[x]:
#  if cnt[i]==-1:
   if i in seen:
    continue
   else:
    seen.add(i)
    dq.append(i)
    cnt[i]=cnt[x]+t_cnt[i]

print(*cnt)

Submission status: Accepted

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

sys.setrecursionlimit(10**6)


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

A=[[] for i in range(N)]
c=[0]*N

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

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

def dfs(now,prev=-1):
    for next in A[now]:
        if next==prev:continue
        else:
            c[next]+=c[now]
            dfs(next,now)
dfs(0)
print(*c)

Submission status: Accepted

Solution code:


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

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

parent = [-1 for i in range(N)]
parent[0] = 0

q = collections.deque()
q.append(0)

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

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

while(q):
    x = q.popleft()
    for y in g[x]:
        if parent[y] == -1:
            q.append(y)
            parent[y] = x
            point[y] += point[x]

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

Submission status: Accepted

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


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

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

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

def dfs(now, prev):
    for vertex in GRAPH[now]:
        if vertex == prev:
            continue
        else:
            next = vertex
        COUNTS[next] += COUNTS[now]
        dfs(next, now)
dfs(1, 0)

answer = " ".join(map(str, COUNTS[1:]))
print(answer)

Submission status: Accepted

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

# def denpan(oya,ko):
#     for i in range(len(ne[ko])):
#         if ne[ko][i]!=oya:
#             cnt[ne[ko][i]]+=cnt[ko]
#             denpan(ko,ne[ko][i])

ne=[[] for i in range(n+1)]
for i in range(n-1):
    ne[ab[i][0]].append(ab[i][1])
    ne[ab[i][1]].append(ab[i][0])
# print(ne)
cnt=[0]*(n+1)
for i in range(q):
    cnt[px[i][0]]+=px[i][1]
par=[-1]*(n+1)
stack=deque([1])
while(stack):
    v=stack.pop()
    for i in range(len(ne[v])):
        if ne[v][i]!=par[v]:
            cnt[ne[v][i]]+=cnt[v]
            par[ne[v][i]]=v
            stack.append(ne[v][i])
cnt.remove(0)
print(' '.join(map(str,cnt)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
#パクリゆるして
#グラフのようななにか

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)

from collections import deque


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

tree=[[]*(N+1) for i in range(N+1)]
point=[0]*(N+1)

for _ in range(N-1):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    
for _ in range(Q):
    p,x=map(int,input().split())
    point[p]+=x
#print(point)

d=deque([[1,0]])

while d:
    node,parent=d.popleft()
    point[node]+=point[parent]
    lis=tree[node]
    for child in lis:
        if child==parent:
            continue
        d.append([child,node])
    #print(d)

print(*point[1:])

Submission status: Accepted

Solution code:
# ABC-138-D
# 参考 https://atcoder.jp/contests/abc138/submissions/7003989

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[2]には頂点2に繋がる全ての頂点が記録される。
    #グラフ2の親が1, 子が2,3の場合は、graph[2]=[1,2,3] ※この時点で親か子かは記録されない。
    graph[a].append(b)
    graph[b].append(a)

#(頂点の数+1)個分の要素を含む配列を作る。
value  =[0] * (N+1)
#「頂点p以下の部分木にxを加算する」という指示に応じて頂点pにx点加算する。pの子に対する加算は後の処理で行う。
for p,x in PX:
    value[p] += x
    
#各pの子に対する加算を行う。
#(加算対象となる頂点、親)という形でキューを持つ。最初の１発目は頂点0を親に持つ頂点1に加算を行う。という形で実行。
#2発目以降でgraphに記載された頂点の中から子に当たる頂点を見つけて、valueに加算をおこなっていく。
queue = [(1,0)]
while queue:#queue=[]になったら終了。
    x, parent = queue.pop()
    value[x] += value[parent]
    #頂点xに繋がる全ての頂点をループで確認していき、parentでなければqueueに入れていく。
    for y in graph[x]:
        if y == parent:
            continue
        #次はparentが現在加算をおこなってる頂点xという形で進んでいく。
        queue.append((y, x))

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from collections import deque
 
N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort()
 
kid = deque(ki)
ver = []
check = []
for i in range(N):
    ver.append(0)
    check.append(False)
 
for c in co:
    ver[c[0]-1] += c[1]
 
check[0] = True
 
kid2 = deque()
 
while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.append(k)
 
while len(kid2) != 0:
    k = kid2.pop()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.appendleft(k)
 
 
print(' '.join(map(str,ver)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)

    # Euler tour
    Q=[(~0,-1),(0,-1)]
    begin=[None]*n
    end=[None]*n
    cnt=-1
    while(Q):
        v,p=Q.pop()
        cnt+=1
        if(v>=0):
            if(begin[v] is None): begin[v]=cnt
            for nv in E[v][::-1]:
                if(nv==p): continue
                Q.append((~nv,v))
                Q.append((nv,v))
        else:
            end[~v]=cnt

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

    for i in range(2*n-1):
        imos[i+1]+=imos[i]

    # output
    print(*(imos[begin[v]] for v in range(n)))
resolve()

Submission status: Accepted

Solution code:
import sys
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


from collections import deque

def main():

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

  li=[[] for i in range(n+1)]
  ans=[0]*(n+1)

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

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

  Q=deque([1])
  sumi=set([1])

  while Q:
  #  print(Q)
    now=Q.pop()
    for i in li[now]:
      if i in sumi:
        continue
      else:
        sumi.add(i)
        Q.append(i)
        ans[i]+=ans[now]
  print(*ans[1:])
      
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque

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

li=[[] for i in range(n+1)]
ans=[0]*(n+1)

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

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

Q=deque([1])
sumi=set([1])

while Q:
#  print(Q)
  now=Q.pop()
  for i in li[now]:
    if i in sumi:
      continue
    else:
      sumi.add(i)
      Q.append(i)
      ans[i]+=ans[now]
print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque

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

li=[[] for i in range(n+1)]
ans=[0]*(n+1)

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

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

Q=deque([1])
sumi=set([1])

while Q:
#  print(Q)
  now=Q.pop()
  for i in li[now]:
    if i in sumi:
      continue
    else:
      sumi.add(i)
      Q.append(i)
      ans[i]+=ans[now]
print(*ans[1:])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
ki = [[]for _ in range(n)]
P = [0]*n
visited = [0] * n
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    
    ki[a].append(b)
    ki[b].append(a)
for i in range(q):
    p,x = map(int,input().split())
    p -= 1
    P[p] += x
stack = [0]
while stack:
    a = []
    for now in stack:
        visited[now] = 1
      
        for next in ki[now]:
            if visited[next]:continue
            P[next]+= P[now]
            a.append(next)
    stack = a
    
print(*P)

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)
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, 0)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque #pypyでも使える
n,q=map(int,input().split())

edges=[[] for i in range(n)] #枝がどことどこをつなぐかの情報を入れておく二次元配列
for i in range(n-1):
	a,b=map(lambda x:int(x)-1,input().split()) #ラムダ式は必見
	#もっといい感じの書き方ないかな?
	edges[a].append(b) #edges[a]には、ノードaの相方を格納
	edges[b].append(a) #edges[b]には、ノードbの相方を格納する決まり

#nodesの重さを格納
nodes=[0]*n
for i in range(q):
	p,x=map(int,input().split())
	nodes[p-1]+=x

#oyakoを、親についての単調増加にしたい->デフォで先頭要素でのソートになるので安心
#oyako.sort()
#と思ったけどソートじゃ無理っぽい
#根から順に処理->bfs幅優先探索
que=deque([0])
color=[0]*n #全てのノードに対して、未探索の0を入れる
color[0]=0 #colorは親としての処理を終えたかどうかを入れる。終えたら1にする
#TLEなった。二重ループはだめねえ。
# ->oyako(edges)を、二次元配列にしてインデックスの数字を持つものをedges[i]に格納すれば
while que: #qが空でないのはこう表現できる
	i=que.popleft()
	if color[i]==0:
		for edge in edges[i]:
			if color[edge]==0: #相方が親じゃなければ(親ならすでに探索済みのはず)
				nodes[edge]+=nodes[i]
				que.append(edge)
		color[i]=1

#綺麗にかけそうでこの書き方をしたけど大丈夫かな?
for node in nodes:
	print(node,end=' ')

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readlines()

n, q = map(int, inputs[0].split())
edges = [tuple(map(int, inputs[1+i].split())) for i in range(n-1)]
weights = [tuple(map(int, inputs[n+i].split())) for i in range(q)]

tree = [[] for _ in range(n)]
for x, y in edges:
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)

val = [0] * n
for p, w in weights:
    val[p-1] += w

stack, parents = [0], [0] * n
while stack:
    x = stack.pop()
    for y in tree[x]:
        if y == parents[x]:
            continue
        parents[y] = x
        stack.append(y)
        val[y] += val[x]

print(*val)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q = map(int,readline().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:N+N-2])
PX = iter(ABPX[N+N-2:])

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

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

stack = [1]

parent = [0] * (N+1)
while stack:
    x = stack.pop()
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        val[y] += val[x]

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

Submission status: Accepted

Solution code:
from collections import deque

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

score = [0]*n
for i in range(q):
    a,b = map(int,input().split())
    score[a-1] += b

def bfs(i):
    s = -1
    q = deque([])
    q.append((i-1,s))
    while q:
        
        num,bef = q.pop()
        for j in E[num]:
            if j == bef:
                continue
            else:
                score[j] += score[num]
                q.append((j,num))
            
    return score
print(*bfs(1))

Submission status: Accepted

Solution code:
from collections import deque

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

score = [0]*n
for i in range(q):
    a,b = map(int,input().split())
    score[a-1] += b

def bfs(i):
    s = -1
    q = deque([])
    q.append((i-1,s))
    while q:
        
        num,bef = q.popleft()
        for j in E[num]:
            if j == bef:
                continue
            else:
                score[j] += score[num]
                q.append((j,num))
            
    return score
print(*bfs(1))

Submission status: Accepted

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


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

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

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


def dfs(current, parent):
    for child in G[current]:
        if child == parent:
            continue
        P[child] += P[current]
        dfs(child, current)


dfs(0, -1)

print(' '.join([str(p) for p in P]))

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

v = [[] for i in range(N)]
score = [0]*N

def dfs(cur,par):
  for chi in v[cur]:
    if chi == par:
      continue
    score[chi] += score[cur]
    dfs(chi, cur)
      
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  v[a].append(b)
  v[b].append(a)

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

dfs(0,-1)
score_int=[str(a) for a in score]
output= ' '.join(score_int)
print(output)

Submission status: Accepted

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

from collections import defaultdict
dic = defaultdict(int)
for _ in range(q):
   p,x = map(int,input().split())
   dic[p-1] += x

ans = [0 for i in range(n)]
ans[0] = dic[0]

used = [0 for i in range(n)]
used[0] = 1
quu = [0]
while quu:
   k = quu.pop()
   for l in m[k]:
      if used[l] == 0:
         used[l] = 1
         quu.append(l)
         ans[l] = ans[k] + dic[l]

for i in ans:
   print(i)

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

v = [[] for i in range(N)]
score = [0]*N

def dfs(cur,par):
  for chi in v[cur]:
    if chi == par:
      continue
    score[chi] += score[cur]
    dfs(chi, cur)
      
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  v[a].append(b)
  v[b].append(a)

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

dfs(0,-1)
score_int=[str(a) for a in score]
output= ' '.join(score_int)
print(output)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(x, w):
    q = deque()
    q.append((x, w))

    while len(q):
        x, w = q.popleft()
        leaves[x] += w
        w = leaves[x]
        for nx in edge[x]:
            if V[nx] == 0:
                V[nx] = 1
                q.append((nx, w))


N, Q = map(int, input().split())
edge = [[] for _ in range(N)]
leaves = [0] * N
V = [0] * N

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

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

V[0] = 1
bfs(0, 0)
for i in range(N - 1):
    print(leaves[i], end=' ')
print(leaves[N - 1])

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)
  tree_index[b].append(a)

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

def dfs(cur, par):
  for child in tree_index[cur]:
    if child == par:
      continue
    ans[child] += ans[cur]
    dfs(child, cur)
dfs(0, -1)
print(*ans)

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): #各頂点についてcount[v]を計算
  v,val=map(int,input().split())
  cnt[v]+=val
q=collections.deque()
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:
N, Q = map(int, input().split())
graph = [[] for i in range(N)]

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

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

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

    ans[p] += x

seen = [False for i in range(N)]

stack = [0]

# dfs
while stack != []:
    v = stack.pop()
    seen[v] = True

    for i in graph[v]:
        if seen[i] == True:
            continue
        ans[i] += ans[v]
        stack.append(i)

print(*ans)

Submission status: Accepted

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

# visited = [False for _ in range(N)]
# def dfs(v): # vertices & parent idx
#     visited[v]=True
#     for child in to[v]:
#         if visited[child]==True:
#             continue
#         ans[child]+=ans[v]
#         dfs(child)
# def dfs(v,p=-1): # vertices & parent idx
#     for child in to[v]:
#         if child==p:
#             continue
#         ans[child]+=ans[v]
#         dfs(child,v)

to=[[] for j in range(N)] # N points
ans=[0]*N # N points

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

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

# dfs(0)
stack=[0]
visited=[False]*N
while stack:
    v=stack.pop()
    visited[v]=True
    for child in to[v]:
        if visited[child] ==False:
            # visited[v]=True
            ans[child]+=ans[v]
            stack.append(child)
for i in range(N):
    print(ans[i],end=' ')
# print(ans)

Submission status: Accepted

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

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):
    pa, x = map(int, input().split())
    pa -= 1
    ans[pa] += x

q = [(0, -1)]
while(q):
    v, p = q.pop()
    for nv in to[v]:
        if nv == p: continue
        ans[nv] += ans[v]
        q.append((nv, v))

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

d = deque([[1, 0]])
while d:
  node, parent = d.popleft()
  counter[node] += counter[parent]
  children = tree[node]
  for child in children:
    if child == parent:
      continue
      
    d.append([child, node])
    
  
print(' '.join(map(str, counter[1:])))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,Q = map(int, input().split(' '))
ab = [list(map(int, input().split(' '))) for i in range(n-1)]
q = [list(map(int, input().split(' '))) for i in range(Q)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
root = 1
order = []
stack = [root]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)
cnt = [0]*(n+1)
for i,x in q:
    cnt[i] += x
ans = [0]*(n+1)
for x in order:
    ans[x] += cnt[x]+ans[parent[x]]
print(*ans[1:],sep=" ")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,Q = map(int, input().split(' '))
ab = [list(map(int, input().split(' '))) for i in range(n-1)]
q = [list(map(int, input().split(' '))) for i in range(Q)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
root = 1
order = []
stack = [root]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)
cnt = [0]*(n+1)
for i,x in q:
    cnt[i] += x
ans = [0]*(n+1)
for x in order:
    if x == 1:
        ans[1] += cnt[1]
        continue
    ans[x] += cnt[x]+ans[parent[x]]
del ans[0]
print(*ans,sep=" ")

Submission status: Accepted

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

graph = [[] for _ in range(N + 1)]
for A, B in AB:
  graph[A].append(B)
  graph[B].append(A)
graph = tuple(graph)
#print("graph:", graph)
  
X = [0] * (N + 1)
for p, x in PX:
  X[p] += x
#print("X:", X)

stack = [1]
check = [0] * (N + 1)
check[1] = 1
cnt = [0] * (N + 1)
cnt[1] = X[1]

while stack:
  s = stack.pop()
  for g in graph[s]:
    if check[g] == 0:
      check[g] = 1
      cnt[g] = cnt[s] + X[g]
      stack.append(g)
print(*cnt[1::])

Submission status: Accepted

Solution code:
N,Q = map(int, input().split())
v = [[] for _ in range(N+1)]
w = [0]*(N+1)

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

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

q=[(1,0)]
while q:
    c,p = q.pop()
    w[c]+=w[p]
    for x in v[c]:
        if x==p:
            continue
        q.append((x,c))

print(' '.join([str(x) for x in w[1:]]))

Submission status: Accepted

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

for i in range(Q):
  p,x = map(int, input().split())
  c[p] += x
#print(AB)
#print(*c[1:])

from collections import deque
stack = deque([1])
 
parent = [0] * (N+1)
while stack:
    x = stack.popleft()
    for y in AB[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        c[y] += c[x]

print(*c[1:])

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input=stdin.readline
    
    n, q = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    px = [list(map(int, input().split())) for _ in [0]*q]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d2 = list(sorted(enumerate(d), key=lambda x: x[1]))

    ans = [0]*n
    for p, x in px:
        ans[p-1] += x
    for i, j in d2:
        for k in g[i]:
            if d[k] == j+1:
                ans[k] += ans[i]
    print(*ans)


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,Q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)

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

    # DFS で子に伝播させる
    Q=[(0,-1)]
    while(Q):
        v,p=Q.pop()
        for nv in E[v]:
            if(nv==p): continue
            ans[nv]+=ans[v]
            Q.append((nv,v))

    print(*ans)
resolve()