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
n, q = map(int, input().split())
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)
c = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    c[p-1] += x
used = [0]*n
used[0] = 1
next = [0]
while next:
    v = next.pop()
    cost = c[v]
    for nv in g[v]:
        if used[nv]:
            continue
        used[nv] = 1
        c[nv] += cost
        next.append(nv)

print(*c)

Submission status: Accepted

Solution code:
from collections import deque
n, q = map(int, input().split())
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)
c = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    c[p-1] += x
used = [0]*n
used[0] = 1
next = deque([0])
while next:
    v = next.popleft()
    cost = c[v]
    for nv in g[v]:
        if used[nv]:
            continue
        used[nv] = 1
        c[nv] += cost
        next.append(nv)

print(*c)

Submission status: Accepted

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

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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

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

ans = [-1] * N
st = deque([(0, 0)])
while st:
    now, val = st.pop()

    if ans[now] >= 0:
        continue
    val += P[now]
    ans[now] = val

    for to in edges[now]:
        st.append((to, val))

print(*ans)

Submission status: Accepted

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

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

def dfs(v, p):
    ans[v] = P[v] + p
    for vi in G[v]:
        if ans[vi] != -1:
            continue
        dfs(vi, ans[v])
dfs(0, 0)

print(' '.join(map(str, ans)))

Submission status: Accepted

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

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

def dfs(v, p):
    ans[v] = P[v] + p
    for vi in G[v]:
        if ans[vi] != -1:
            continue
        dfs(vi, ans[v])
dfs(0, 0)

print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
def o():return map(int,input().split())
n,q=o();a=[[]for i in range(n)];x=[0]*n;p=[[0,0]]
for i in range(n-1):u,v=o();a[u-1]+=[v-1];a[v-1]+=[u-1]
for i in range(q):u,v=o();x[u-1]+=v
while p:
  r,s=p.pop()
  for i in a[r]:
    if i!=s:
      p+=[[i,r]]
      x[i]+=x[r]
print(*x)

Submission status: Accepted

Solution code:
def o():return map(int,input().split())
n,q=o()
a=[[]for i in range(n)]
x=[0]*n
for i in range(n-1):
  u,v=o()
  a[u-1]+=[v-1]
  a[v-1]+=[u-1]
for i in range(q):
  u,v=o()
  x[u-1]+=v
p=[[0,0]]
s=0
while p:
  r,s=p.pop()
  for i in a[r]:
    if i!=s:
      p+=[[i,r]]
      x[i]+=x[r]
print(*x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())
tree = [[] for _ in range(N)]

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


def dfs(cur,par):
    for chl in tree[cur]:
        if chl == par: #これで木の流れの逆行を防ぐ
            continue
        ans[chl] += ans[cur]
        dfs(chl,cur)

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

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
tree = [[] for _ in range(N)]

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


def dfs(cur,par):
    for chl in tree[cur]:
        if chl == par: #これで木の流れの逆行を防ぐ
            continue
        ans[chl] += ans[cur]
        dfs(chl,cur)

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n,q=map(int,input().split())
    from collections import deque,defaultdict
    dic=defaultdict(list)
    for i in range(n-1):
        x,y=map(int,input().split())
        dic[x-1].append(y-1)
        dic[y-1].append(x-1)
    cnt=[0]*n
    for i in range(q):
        x,y=map(int,input().split())
        cnt[x-1]+=y
    
    d=deque()
    d.append(0)
    completed=[False]*n
    while d:
        now=d.popleft()
        completed[now]=True
        for x in dic[now]:
            if completed[x]==False:
                cnt[x]+=cnt[now]
                d.append(x)
    print(*cnt)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n,q=map(int,input().split())
    from collections import deque,defaultdict
    dic=defaultdict(list)
    for i in range(n-1):
        x,y=map(int,input().split())
        dic[x-1].append(y-1)
        dic[y-1].append(x-1)
    cnt=[0]*n
    for i in range(q):
        x,y=map(int,input().split())
        cnt[x-1]+=y
    
    d=deque()
    d.append(0)
    completed=[False]*n
    while d:
        now=d.popleft()
        completed[now]=True
        for x in dic[now]:
            if completed[x]==False:
                cnt[x]+=cnt[now]
                d.append(x)
    print(*cnt)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,q = map(int,input().split())
lst = [[]for i in range(n)]
ans = [0 for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    lst[a-1].append(b)
    lst[b-1].append(a)
for i in range(q):
    p,x = map(int,input().split())
    ans[p-1] += x
q = deque([1])
while q:
    x = q.popleft()
    for i in lst[x-1]:
        q.append(i)
        lst[i-1].remove(x)
        ans[i-1] += ans[x-1]
print(" ".join(map(str,ans)))

Submission status: Accepted

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

def solve(): 
  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)

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

  def dfs(v,pv):      
    for nv in G[v]:
      if nv != pv:
        P[nv] += P[v]
        dfs(nv,v)

  dfs(0,0)
  print(*P)

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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)

P = [0]*n
for i in range(q):
  p,x = map(int,input().split())
  P[p-1] += x
     
def dfs(v,pv):      
  for nv in G[v]:
    if nv != pv:
      P[nv] += P[v]
      dfs(nv,v)
        
dfs(0,0)
print(*P)

Submission status: Accepted

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

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)

l = [0]*n

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

visited = [False]*n
visited[0] = True

q = [0]

while q:
    v = q.pop()
    for w in g[v]:
        if not visited[w]:
            visited[w] = True
            l[w] += l[v]
            q.append(w)

print(*l)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
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)]

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

ans = [0]*n

# DFS for tree (再帰はpypyの方が遅かったりするので注意)
def dfs(v=0, parent=-1):# どこからきたかの情報を入れとく
    for to in es[v]:
        if to == parent: continue # 今回はcontinue

        ans[to] += ans[v]
        dfs(to, v)


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

dfs(0)

print(*ans, sep=' ')

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,q=map(int,input().split())
edge = [[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
Ans=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  Ans[p-1]+=x
S=[0]
C=[True]*n
C[0]=False
append=S.append
while S:
  s=S.pop()
  a=Ans[s]
  for g in edge[s]:
    if C[g]:
      Ans[g]+=Ans[s]
      append(g)
      C[g]=False
print(*Ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def main():
    vertex_num, operation_num = map(int, sys.stdin.buffer.readline().split())
    tree = [[] for _ in range(vertex_num)]
    for _ in range(vertex_num - 1):
        a, b = map(lambda x: int(x) - 1, sys.stdin.buffer.readline().split())
        tree[a].append(b)
        tree[b].append(a)
    answer = [0 for _ in range(vertex_num)]
    checked = [True for _ in range(vertex_num)]
    checked[0] = False
    for _ in range(operation_num):
        p, x = map(int, sys.stdin.buffer.readline().split())
        answer[p - 1] += x
    q = deque([0])
    empty_deque = deque()
    while not q == empty_deque:
        now = q.popleft()
        for next_vertex in tree[now]:
            if checked[next_vertex]:
                checked[next_vertex] = False
                answer[next_vertex] += answer[now]
                q.append(next_vertex)
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
def solve():
    input=sys.stdin.readline
    n,q=map(int, input().split())

    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for _ in range(n-1):
        a,b=map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    ans=[0]*n
    for _ in range(q):
        p,x=map(int,input().split())
        ans[p-1]+=x
    #(G,v,p)=(グラフ(木の情報),探索中の頂点,vの親)
    #vの子の頂点を決めて、vをpに移す
    q=deque()
    q.append((0,-1))
    while q:
        V,P=q.popleft()
        for new_v in G[V]:
            #new_vが頂点の時はアウト
            if new_v==P:continue
            ans[new_v]+=ans[V]
            q.append((new_v,V))
    print(*ans)
solve()

Submission status: Accepted

Solution code:
from collections import deque
import sys
def solve():
    input=sys.stdin.readline
    n,q=map(int, input().split())

    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for _ in range(n-1):
        a,b=map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    ans=[0]*n
    for _ in range(q):
        p,x=map(int,input().split())
        ans[p-1]+=x
    #(G,v,p)=(グラフ(木の情報),探索中の頂点,vの親)
    #vの子の頂点を決めて、vをpに移す
    q=deque()
    q.append((0,-1))
    while q:
        V,P=q.popleft()
        for new_v in G[V]:
            #new_vが頂点の時はアウト
            if new_v==P:continue
            ans[new_v]+=ans[V]
            q.append((new_v,V))
    print(*ans)
solve()

Submission status: Accepted

Solution code:
def Graph():
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for _ in range(n-1):
        a,b=map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    return G

from collections import deque
def bfs(G,v,p):
    #(G,v,p)=(グラフ(木の情報),探索中の頂点,vの親)
    #vの子の頂点を決めて、vをpに移す
    q=deque()
    q.append((v,p))
    while q:
        V,P=q.popleft()
        for new_v in G[V]:
            #new_vが頂点の時はアウト
            if new_v==P:continue
            ans[new_v]+=ans[V]
            q.append((new_v,V))
n,q=map(int,input().split())
G=Graph()
ans=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
bfs(G,0,-1)
print(*ans)

Submission status: Accepted

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


def dfs(cur, par):
    for child in edge[cur]:
        if child == par:
            continue
        counter[child] += counter[cur]
        dfs(child, cur)


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)]
counter = [0] * N

edge = [[] for _ in range(N)]
for i in range(N-1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    edge[a].append(b)
    edge[b].append(a)

for i in range(Q):
    p = px[i][0] - 1
    x = px[i][1]
    counter[p] += x


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

Submission status: Accepted

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

def main():
    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)]

    con = [[] for _ in range(N)]
    for i in range(N-1):
        con[X[i][0]-1]+=[X[i][1]-1]
        con[X[i][1]-1]+=[X[i][0]-1]

    dif = [0]*N
    for i in range(Q):
        dif[Y[i][0]-1] += Y[i][1]

    root = deque([0])
    go = [True for _ in range(N)]
    go[0] = False
    while root:
        cur = root.pop()
        for fol in con[cur]:
            if go[fol]:
                dif[fol] += dif[cur]
                go[fol] = False
                root.append(fol)

    print(*dif)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()

tree = defaultdict(list)

# ノードの重み

cnt = [0] * N

# tree 隣接リスト
for i in range(N-1):
    a, b = LIST()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(Q):
    node, point = LIST()
    cnt[node-1] += point

ans = [0] * N
q = deque([])
# 始点
q.append(0)
# 各頂点を見たかどうかのフラグ
checked = [0] * N
checked[0] = 1

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

Submission status: Accepted

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

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

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

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

while q:
    v = q.pop()
    flag[v] = True
    for e in g[v]:
        if flag[e]:
            continue
        cnt[e] += cnt[v]
        q.append(e)
        
print(*cnt)

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

def dfs(now, prev = -1):
    for next in G[now]:
        if next == prev:
            continue
        point[next] += point[now]
        dfs(next, now)

dfs(0)
print(*point)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N, Q = MAP()
	tree = defaultdict(list)
	dic = defaultdict(int)
	for _ in range(N-1):
		a, b = MAP()
		tree[a-1].append(b-1)
		tree[b-1].append(a-1)

	for _ in range(Q):
		p, x = MAP()
		dic[p-1] += x

	ans = [0]*N

	checked = [0]*N
	checked[0] = 1

	q = deque([])
	q.append(0)

	while q:
		n = q.popleft()
		ans[n] += dic[n]
		for node in tree[n]:
			if checked[node]:
				continue
			ans[node] += ans[n]
			checked[node] = 1
			q.append(node)

	print(*ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

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

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


def dfs(s):
    used = [False]*N
    stack = []
    stack.append(s)
    while len(stack):
        now = stack[-1]
        used[now] = True
        stack.pop()
        for nxt in G[now]:
            if used[nxt]:
                continue
            val[nxt] += val[now]
            stack.append(nxt)

dfs(0)

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

Submission status: Accepted

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

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

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

used = [False]*N


def dfs(s):
    stack = []
    stack.append(s)
    while len(stack) > 0:
        now = stack[-1]
        used[now] = True
        stack.pop()
        for nxt in G[now]:
            if used[nxt]:
                continue
            val[nxt] += val[now]
            stack.append(nxt)


dfs(0)

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

Submission status: Accepted

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

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

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

used = [False]*N


def dfs(s):
    stack = []
    stack.append(s)
    while len(stack) > 0:
        now = stack[-1]
        used[now] = True
        stack.pop()
        for nxt in G[now]:
            if used[nxt]:
                continue
            val[nxt] += val[now]
            stack.append(nxt)


dfs(0)

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(10000000)
    
    n,q=map(int,input().split())
    tree=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    
    cnt=[0]*n
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        cnt[p]+=x
    
    def dfs(i,before=-1):
        for e in tree[i]:
            if e!=before:
                cnt[e]+=cnt[i]
                dfs(e,i)
                
    dfs(0)   
    print(*cnt)

if __name__=='__main__':
    main()

Submission status: Accepted

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

from collections import deque

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

edge = {}
for i in range(1,n+1):
    edge[i] = []

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

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

d = deque()
remains = set(range(1,n+1))
d.append(1)
remains.remove(1)

while(len(d) > 0):
    tmp = d.pop()
    for i in edge[tmp]:
        if(i in remains):
            ans[i] += ans[tmp]
            d.append(i)
            remains.remove(i)

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

Submission status: Accepted

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

visited[0] = 1
stack = [0]
while stack:
  v = stack.pop()
  for c in tree[v]:
    if visited[c]:
      continue
    visited[c] = 1
    ans[c] += ans[v]
    stack.append(c)
    
print(" ".join(str(i) for i in ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q = map(int,input().split())
tree = {i : [] for i in range(n)}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  tree[b].append(a)
score = [0 for _ in range(n)]
for i in range(q):
  p,x = map(int,input().split())
  score[p-1] += x
  
def dfs(parent,node,s):
  for n in tree[node]:
    if n == parent:
      continue
    score[n] += score[node]
    dfs(node,n,s)

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

Submission status: Accepted

Solution code:
from collections import deque

def graph(N):# Nの無向グラフの作成
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = [int(x) for x in input().split()]
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    return graph

def cnt(Q,graph):
    V = [False] * N#いったことがあるかどうか
    cnt = [0] * N
    for _ in range(Q):
        p, x = [int(x) for x in input().split()]
        cnt[p-1] += x#まず、それぞれのｘだけカウント増やしておく
    que = deque([0])#スタートは0から。
    while que:#木の末端にきてqueなくなるまで
        s = que.popleft()#取り出し（深さ探索）
        V[s] = True
        for i in graph[s]:#根についてる枝の数だけ
            if V[i] == False:#いったことがある方向には戻らないようにする
                cnt[i] += cnt[s]#枝に根の分カウント増やす
                que.append(i) #枝情報をqueに追加
    return(cnt)

N, Q = map(int, input().split())
A = graph(N)
print(*cnt(Q, A))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

from collections import defaultdict
from collections import deque

def main():
	n,q=map(int,input().split())
	d=defaultdict(list)
	
	for i in range(n-1):
		a,b=map(int,input().split())
		d[a].append(b)
		d[b].append(a)
	
	cnt=[0]*(n+1)
	
	for i in range(q):
		p,x=map(int,input().split())
		cnt[p]+=x
	
	data=[]
	
	
	q=deque([1])
	sumi=set()
	
	while q:
		now=q.popleft()
		sumi.add(now)
		kouho=d[now]
		for i in kouho:
			if i not in sumi:
				q.append(i)
				cnt[i]+=cnt[now]
	
	print(*cnt[1:])
	
	
	
	
	
	
	
	
	
	
	
	
	

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# 先にクエリを蓄積してから親のカウンターを子に分配

from collections import deque

N,Q=map(int,input().split())
vtx=[[] for _ in range(N)]
pnt=[-1 for _ in range(N)]
cnt=[0 for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  vtx[a-1].append(b-1)
  vtx[b-1].append(a-1)
pnt[0]=0
que=deque([0])
while que:
  v=que.popleft()
  for w in vtx[v]:
    if pnt[w]==-1:
      pnt[w]=v
      que.append(w)
for i in range(Q):
  p,x=map(int,input().split())
  cnt[p-1]+=x
que=deque([0])
while que:
  # print(cnt)
  v=que.popleft()
  for w in vtx[v]:
    if w!=pnt[v]:
      cnt[w]+=cnt[v]
      que.append(w)
for c in cnt:
  print(c)

Submission status: Accepted

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


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

    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        ai, bi = map(int, input().split())
        g[ai - 1].append(bi - 1)
        g[bi - 1].append(ai - 1)

    ans = [0] * n
    for _ in range(q):
        pi, xi = map(int, input().split())
        ans[pi - 1] += xi

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

    dfs(0)
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    ai, bi = map(int, input().split())
    g[ai - 1].append(bi - 1)
    g[bi - 1].append(ai - 1)

ans = [0] * n
for _ in range(q):
    pi, xi = map(int, input().split())
    ans[pi - 1] += xi


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


dfs(0)
print(*ans)

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
# 親の番号 < 子の番号
edge = [[] for _ 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)
vertices = [0] * N
for _ in range(Q):
    p,x = map(int,input().split())
    vertices[p-1] += x

from collections import deque

que = deque([(-1,0)])
while que:
    pre,now = que.popleft()
    cost = vertices[now]
    for e in edge[now]:
        if e == pre:
            continue
        vertices[e] += cost
        que.append((now,e))

print(*vertices, sep=" ")

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    Edge = [[] for _ 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
    a = deque()
    a.append((-1, 0)) #"pre, now"
    while a:
        pre, now = a.popleft()
        for e in Edge[now]:
            if e != pre:
                counter[e] += counter[now]
                a.append((now, e))
    print(" ".join(map(str, counter)))

    return 0

if __name__ == "__main__":
    solve()

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())
    a, b = a-1,b-1
    g[a].append(b)
    g[b].append(a)

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

#print(xs)
from collections import deque
s = deque()
s.append(0)
visit = [-1]*n
visit[0] = 0
while s:
    x = s.pop()
    for new_x in g[x]:
        if visit[new_x] == -1:
            visit[new_x] = 0
            xs[new_x] += xs[x]
            s.append(new_x)
print(*xs)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = (int(i) for i in input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    vertex = [0 for i in range(N)]
    for q in range(Q):
        p, x = (int(i) for i in input().split())
        vertex[p-1] += x
    from collections import deque
    G_color = ['WHITE' for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(G, s):
        G_color[s] = 'GRAY'
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_parent[v] = u
                    vertex[v] += vertex[u]
                    Q.append(v)
            G_color[u] = 'BLACK'

    bfs(edge, 0)
    print(*vertex)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
G = [set() for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].add(b)
    G[b].add(a)

g2 = [set() for _ in range(N+1)]
p = [0]*(N+1)
vs = set()
stack = [1]
dfs_vs = []
vs.add(1)
while stack:
    v = stack.pop()
    dfs_vs.append(v)
    for u in G[v]:
        if u in vs:
            continue
        g2[v].add(u)
        p[u] = v
        stack.append(u)
        vs.add(u)

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

#print(d)
#print(p)

for v in dfs_vs:
    d[v] += d[p[v]]

print(*d[1:])