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:
def dfs(u, cnt):
    cnt += point[u]
    counter[u] = cnt
    color[u] = GRAY
    for v in M[u]:
        if color[v] == WHITE:
            dfs(v, cnt)
    color[u] = BLACK

import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
M = [[] for _ in range(n)]
point = [0] * n
for i in range(n-1):
    a, b = map(int, input().split())
    M[a-1].append(b-1)
    M[b-1].append(a-1)
for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x
#print(M, point)
    
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n

counter = [0] * n
dfs(0, 0)

print(*counter)

Submission status: Accepted

Solution code:
# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)
#隣接リスト表現
n,q=list(map(int,input().split()))
es=[[] for i in range(n)]
for i in range(n-1):
  a,b=list(map(int,input().split()))
  es[a-1].append(b)
  es[b-1].append(a)
#頂点に値をたす
cnt=[0 for i in range(n)]
for i in range(q):
  p,x=list(map(int,input().split()))
  cnt[p-1]=cnt[p-1]+x
  
#頂点vから始めるdfsで累積和をを求める
#check=訪れたことがあるかどうかを探索
check=[0 for i in range(n)]
def dfs(v):
  check[v-1]=1
  for l in es[v-1]:
    if check[l-1]==0:
      cnt[l-1]=cnt[l-1]+cnt[v-1]
      dfs(l)
  return cnt
#出力
dfs(1)
for i in cnt:
  print(i,end=" ")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, q = MI()
    connected_graph = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = MI()
        connected_graph[b - 1].append(a - 1)
        connected_graph[a - 1].append(b - 1)

    points = [0] * n

    for j in range(q):
        p, x = MI()
        points[p - 1] += x

    ans = [-1] * n
    ans[0] = points[0]
    queue = cl.deque([])
    queue.append(0)
    while len(queue) > 0:
        target = queue.popleft()
        connecteds = connected_graph[target]
        for connected in connecteds:
            if ans[connected] != -1:
                continue
            else:
                ans[connected] = ans[target] + points[connected]
                queue.append(connected)

    print(*ans, sep=" ")


main()

Submission status: Accepted

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

c = [0] * n

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

used = [0] * n
used[0] = 1

def dfs(x):
    cost=c[x]
    for nx in g[x]:
        if used[nx]:
            continue
        used[nx]=1
        c[nx]+=cost
        dfs(nx)
dfs(0)
print(*c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

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

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

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

d = deque([1])

while len(d):
    p = d.popleft()
    for i in graph[p]:
        if b[i]:
            a[i] += a[p]
            d.append(i)
            graph[i].remove(p)
print(*a[1:])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

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

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

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

d = deque([1])
b[1] = False

while len(d):
    p = d.popleft()
    for i in graph[p]:
        if b[i]:
            a[i] += a[p]
            b[i] = False
            d.append(i)
print(*a[1:])

Submission status: Accepted

Solution code:
from collections import deque
n,q = map(int,input().split())
l =  [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    l[b].append(a)

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

bit = [0 for _ in range(n)]
"""
def dfs(k):
    bit[k] = 1
    for i in l[k]:
        if bit[i]==0:
            value[i] += value[k]
            dfs(i)
"""
d = deque([0])
while d:
    a = d.popleft()
    bit[a] = 1
    for i in l[a]:
        if bit[i]==0:
            d.append(i)
            value[i] += value[a]
        

print(*value)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    dist = [-1]*(n+1)
    que = deque([1])
    dist[1] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in g[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            ans[w] += ans[v]
            que.append(w)

n, q  = MAP()
g = [[] for i in range(n+1)]
ans = [0]*(n+1)
for i in range(n-1):
    a, b = MAP()
    g[a].append(b)
    g[b].append(a)
for i in range(q):
    p, x = MAP()
    ans[p] += x
#for i in range(1,n+1):
#    ans[i] += ans[g[i]]
bfs()
for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

N, Q = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
PX = [tuple(map(int, input().split())) for _ in range(Q)]
counter = [0] * (N + 1)
for px in PX:
    p, x = px
    counter[p] += x

q = deque()
visited = [-1] * (N+1)
visited[1] = 1
q.append(1)

while q:
    parent = q.pop()
    nodes = graph[parent]
    for node in nodes:
        if visited[node] == -1:
            visited[node] = 1
            q.append(node)
            counter[node] += counter[parent]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
 
n, q = map(int, input().split())
connect = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)
 
counter = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    counter[p-1] += x
 
ans = [0] * n
 
def dfs(count, v, parent):
    count += counter[v]
    ans[v] = count
    for child in connect[v]:
        if child != parent:
            dfs(count, child, v)
 
dfs(0, 0, -1)
 
print(*ans)

Submission status: Accepted

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

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

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

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

ans = [0] * n
def dfs(me, parent, cum):
    cum += counter[me]
    ans[me] = cum
    for child in connect[me]:
        if child != parent:
            dfs(child, me, cum)

dfs(0, -1, 0)

print(*ans)

Submission status: Accepted

Solution code:
N,Q = list(map(int,input().split()))
ad={}
point={}
P = {}
color={}
child={}

for n in range(N):
    ad[n+1]=set()
    child[n+1]=set()
    color[n+1] = -1
    point[n+1] = 0
    P[n+1] = 0

for n in range(N-1):
    a,b = list(map(int,input().split()))
    ad[a].add(b)
    ad[b].add(a)
    
for q in range(Q):
    p,x = list(map(int,input().split()))
    point[p] += x

#BFS
from collections import deque
start=1
visit = []
que = deque([start])

i=0
while len(que) > 0:
    start = que.popleft()
    color[start] = 1
    
    for v in ad[start]:
        if color[v] == -1:
            que.append(v) 
            color[v] = 0
            point[v] += point[start]
    
#     print(que,point)
ans=' '.join(map(str,point.values()))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
n,q = map(int,input().split())
dic = defaultdict(list)
for i in range(n-1):
    a,b = map(int,input().split())
    dic[b].append(a)
    dic[a].append(b)
# print(d)

dp = [-1]+[0]*n

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

visited = [False]*(n+1)
que = deque([1])

while que:
    parent = que.popleft()
    visited[parent] = True
    for child in dic[parent]:
        if not visited[child]:
            dp[child] += dp[parent]
            que.append(child)

print(*dp[1:])

Submission status: Accepted

Solution code:
from collections import deque

N,Q = map(int, input().split())
g,q,s,c,d = [[] for i in range(N)],[0]*N,[False]*N,[0]*N,deque()

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

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

d.append(0)
while d:
	v = d.popleft()
	s[v] = True
	for x in g[v]:
		if not s[x]:
			d.append(x)
			q[x] += q[v]

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

Submission status: Accepted

Solution code:
from collections import deque

N,Q = map(int, input().split())
g = [[] for i in range(N)]
q,s,c = [0]*N,[False]*N,[0]*N
d = deque()

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

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

d.append(0)
while d:
	v = d.popleft()
	s[v] = True
	for x in g[v]:
		if not s[x]:
			d.append(x)
			q[x] += q[v]

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[32]:


from collections import deque


# In[37]:


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


# In[38]:


if __name__ == "__main__":
    func()


# In[ ]:

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

c = [0] * (n+1)

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

#BFS 
q = deque([1])
visited = [False] * (n+1)
visited[1] = True


while len(q) > 0:
    v = q.popleft()
    for w in adj[v]:
        if not visited[w]:
            q.append(w)
            c[w] += c[v]
            visited[w] = True

c_str = [str(c[i+1]) for i in range(n)]
print(" ".join(c_str))

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N, Q = MI()
    #木
    tree = [[] for i in range(N)]
    for i in range(N-1):
        a,b = MI()
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    #カウンター保存用、初期化
    counter = [0]* N
    score = [0]* N
    dq = deque()
    dq.append([0,-1])
    for i in range(Q):
        p, x = MI()
        counter[p-1] += x
    score[0] = counter[0]
    #score[tree[0][0]] = counter[tree[0][0]]
    while dq:
        temp, past = dq.pop()
        for num in tree[temp]:
            if num != past:
                score[num] = score[temp]+counter[num]
                dq.append([num,temp])
    score = [str(i) for i in score]
    print(" ".join(score))
    return None

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
 
def main():
    n,q = map(int,ipt().split())
    way = [[] for i in range(n+1)]
    for i in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)
    pl = [0]*(n+1)
    for i in range(q):
        p,x = map(int,ipt().split())
        pl[p] += x
    ans = [-1]*(n+1)
    ans[0] = 0
    ans[1] = pl[1]
    q = [(1,0)]
 
    while q:
        qi,qp = q.pop()
        qa = ans[qi]
        for j in way[qi]:
            if j == qp:
                continue
            ans[j] = qa+pl[j]
            q.append((j,qi))
 
    print(" ".join(map(str,ans[1::])))
 
    return None
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
 
N,Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #頂点を0indexに
  G[a].append(b);G[b].append(a)
query = {}
for i in range(Q):
  p,x = map(int,input().split())
  p-=1
  if p not in query:
    query[p] = x
  else:
    query[p] += x
ans = [0 for _ in range(N)]
def dfs(v,par): #vが今いる頂点、parが親。
  if v in query:
    ans[v] += query[v]
  for u in G[v]:
    if u != par:
      ans[u] += ans[v]
      dfs(u,v)
dfs(0,-1)
print(*ans)

Submission status: Accepted

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

N,Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #頂点を0indexに
  G[a].append(b);G[b].append(a)
#query = {}
ans = [0 for _ in range(N)]
for i in range(Q):
  p,x = map(int,input().split())
  p-=1
  ans[p] += x

def dfs(v,par): #vが今いる頂点、parが親。
  if par != -1:
    ans[v] += ans[par]
  for u in G[v]:
    if u != par:
      dfs(u,v)
dfs(0,-1)
print(*ans)

Submission status: Accepted

Solution code:
import re
import sys
from collections import *
from functools import lru_cache
from heapq import *
from itertools import *
from statistics import *
from string import (
    ascii_letters as letters,
    ascii_lowercase as lcletters,
    ascii_uppercase as ucletters,
    digits
)

hexdigits='01234567890ABCDEFabcdef'
inf=float('inf')

sys.setrecursionlimit(2**31-1)

rfs=lambda:rl().split()
ri=lambda:int(rl())
ris=lambda:list(map(int,rfs()))
rls=lambda:list(sys.stdin)
rl=lambda:next(sys.stdin)
rrs=lambda:list(map(str.strip,rls()))
rs=lambda:rl().strip()
rt=lambda:sys.stdin.read()
rg=lambda:list(map(list,rrs()))
rig=lambda:[[*map(int,x.split())] for x in rls()]

def n4(i,j):
    return [
                (i-1,j),
        (i,j-1),        (i,j+1),
                (i+1,j),
    ]

def n8(i,j):
    return [
        (i-1,j-1),(i-1,j),(i-1,j+1),
        (  i,j-1),        (  i,j+1),
        (i+1,j-1),(i+1,j),(i+1,j+1),
    ]

inb=lambda i,j,m,n:0<=i<m and 0<=j<n

###########################################

N,Q=ris()

adj=defaultdict(list)
for _ in range(N-1):
    a,b=ris()
    adj[a].append(b)
    adj[b].append(a)

ct=[0]*N
for _ in range(Q):
    p,x=ris()
    ct[p-1]+=x
    
def dfs(u,p):
    if p!=-1:
        ct[u-1]+=ct[p-1]
    for v in adj[u]:
        if v!=p:
            dfs(v,u)

dfs(1,-1)

print(*ct)

Submission status: Accepted

Solution code:
import re
import sys
from collections import *
from functools import lru_cache
from heapq import *
from itertools import *
from statistics import *
from string import (
    ascii_letters as letters,
    ascii_lowercase as lcletters,
    ascii_uppercase as ucletters,
    digits
)

hexdigits='01234567890ABCDEFabcdef'
inf=float('inf')

sys.setrecursionlimit(2**31-1)

rfs=lambda:rl().split()
ri=lambda:int(rl())
ris=lambda:list(map(int,rfs()))
rls=lambda:list(sys.stdin)
rl=lambda:next(sys.stdin)
rrs=lambda:list(map(str.strip,rls()))
rs=lambda:rl().strip()
rt=lambda:sys.stdin.read()
rg=lambda:list(map(list,rrs()))
rig=lambda:[[*map(int,x.split())] for x in rls()]

def n4(i,j):
    return [
                (i-1,j),
        (i,j-1),        (i,j+1),
                (i+1,j),
    ]

def n8(i,j):
    return [
        (i-1,j-1),(i-1,j),(i-1,j+1),
        (  i,j-1),        (  i,j+1),
        (i+1,j-1),(i+1,j),(i+1,j+1),
    ]

inb=lambda i,j,m,n:0<=i<m and 0<=j<n

###########################################

N,Q=ris()

adj=defaultdict(list)
for _ in range(N-1):
    a,b=ris()
    adj[a].append(b)
    adj[b].append(a)

ct=[0]*(N+1)
for _ in range(Q):
    p,x=ris()
    ct[p]+=x
    
ans=[0]*N
def dfs(u,x,p):
    x=x+ct[u]
    ans[u-1]=x
    for v in adj[u]:
        if v!=p:
            dfs(v,x,u)

dfs(1,0,-1)

print(*ans)

Submission status: Accepted

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

P=[[0,0] for i in range(N+1)]
for i in range(Q):
    p,x=map(int,input().split())
    P[p][1]+=x
#print(P)
P[1][0]=1
A=[]
for i in L[1]:
    A.append([1,i])
    P[i][0]=1
    P[i][1]+=P[1][1]
#print(A)
#print(P)
for i in range(10**7):
    if i==len(A):
        break
    s,g=A[i]
    for j in L[g]:
        if P[j][0]==0:
            P[j][0]=g
            P[j][1]+=P[g][1]
            A.append([g,j])
    #print(A)
ans=[]
for i in range(1,N+1):
    ans.append(P[i][1])
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

N, Q = map(int, input().split())
score = [0]*N

#　木を作成
Ki = [[] for _ in range(N)]
for _ in range(N-1):
    p, c = map(int, input().split())
    Ki[p-1].append(c-1)
    Ki[c-1].append(p-1)
    
# スコア表を作る
S = [0]*N
for _ in range(Q):
    node, score = map(int, input().split())
    S[node-1] += score

# DFS
stack = deque([0])
done = [0]*N
done[0] = 1

while len(stack) > 0:
    now = stack.pop()
    
    for new in Ki[now]:
        if done[new] == 0:
            done[new] = 1
            stack.append(new)
            S[new] += S[now]
    
print(*S)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = lambda:sys.stdin.readline().strip()
    
    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)]

    # queryを一個づつ処理すると間に合わない。
    # pxをまとめ上げ、かつ隣接nodeに逐次加算していけばよい
    from collections import deque

    tree = [[] for i in range(N)]
    for a,b in AB:
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    score = [0]*N
    for p,x in PX:
        score[p-1]+=x

    queue = deque([0])
    visited = [False]*N
    visited[0] = True

    while queue:
        x = queue.pop()

        for i in tree[x]:
            if not visited[i]:
                queue.append(i)
                score[i]+=score[x]
                visited[i]=True

    print(*score)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = lambda:sys.stdin.readline().strip()
    
    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)]

    from collections import deque

    tree = [[] for i in range(N)]
    for a,b in AB:
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    score = [0]*N
    for p,x in PX:
        score[p-1]+=x

    queue = deque([0])
    visited = [False]*N
    visited[0] = True

    while queue:
        x = queue.pop()

        for i in tree[x]:
            if not visited[i]:
                queue.append(i)
                score[i]+=score[x]
                visited[i]=True

    print(*score)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d
import sys
sys.setrecursionlimit(2*2*10**5)

def dfs(i,p,edges,num):
    
    for j in edges[i]:
        if(j!=p):
            
            num[j] += num[i]
            
            dfs(j,i,edges,num)
    


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


#隣接リスト
edges = [ [] for i in range(N)]
num = [0]*N


for i in range(N-1):
    a0,b0 = map(int,input().split())

    edges[a0-1].append(b0-1)
    edges[b0-1].append(a0-1)
    
for i in range(Q):
    p0,x0 = map(int,input().split())

    num[p0-1] += x0
    
dfs(0,-1, edges, num)
    
for i in range(N):
    print(num[i], end=" ")

Submission status: Accepted

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


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def dfs2(self, info, start=1, goal=-1, time=0, save=False):
        """
        :param info: 各頂点の付加情報 = [v1,v2,v3,...,vN]
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: 伝搬後のinfo
        """

        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        if self.destroy:
            edge2 = self.edges
        else:
            edge2 = marshal.loads(marshal.dumps(self.edges))

        p, t = start, time
        self.parent[p] = -2
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.directed:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                if q == goal:
                    """ ゴール時の処理"""
                    # return t + 1
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                info[q] += info[p]
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ p から進める点がもう無い時の点 p における処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 点 p から親ノードに戻ってきた時の親ノードにおける処理 """

                """"""""""""""""""""
        return info

##################################################################################################

N, Q = map(int, input().split())
M = N-1
graph = Graph(N, directed=False, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)
info = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    info[p-1] += x
res = graph.dfs2(info, start=1)
print(*res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

n,q=map(int,input().split())
lis=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    lis[a-1].append(b-1)
    lis[b-1].append(a-1)
p_list=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    p_list[p-1]+=x
close=set()
def dfs(n):
    close.add(n)
    for e in lis[n]:
        if e not in close:
            p_list[e]+=p_list[n]
            dfs(e)
dfs(0)
for p in p_list: print(p,end=" ")

Submission status: Accepted

Solution code:
import sys
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, sys.stdin.readline().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
X = [0] * N
for _ in range(Q):
    p, x = map(int, sys.stdin.readline().split())
    X[p-1] += x

ans = [0] * N
done = set()
todo = [(0, X[0])]
while todo:
    i, sumx = todo.pop()
    ans[i] = sumx
    done.add(i)
    for ni in G[i]:
        if ni in done:
            continue
        todo.append((ni, sumx + X[ni]))
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
count=[0]*(n+1)
ab=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
for _ in range(q):
    p,x=map(int,input().split())
    count[p]+=x
stack=[]
visited=[0]*(n+1)
stack.append(1)
visited[1]=1
while stack:
    y=stack.pop()
    for i in ab[y]:
        if visited[i]==0:
            visited[i]+=1
            count[i]+=count[y]
            stack.append(i)
for j in range(n+1):
    count[j]=str(count[j])
print(" ".join(count[1:]))

Submission status: Accepted

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

c=[0]*n

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)

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

ans = [0]*n

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

print(*ans)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
tree = [[] for _ in range(n)]

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

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

visited = set()
stack = [0]
while stack:
    i = stack.pop()
    visited.add(i)
    for j in tree[i]:
        if not j in visited:
            counter[j] += counter[i]
            stack.append(j)
print(' '.join(map(str, counter)))

Submission status: Accepted

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

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

G = [[] for i in range(N)]
for i in range(N - 1):
  a,b = map(int,readline().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,readline().split())
  P[p - 1] += x
  
ans = [0] * N

stack = []
# 頂点, 親, そこまでの点数
stack.append([0, -1, 0])
while stack:
  v,parent,point = stack.pop()
  point += P[v]
  ans[v] = point
  for child in G[v]:
    if child == parent:
      continue
    stack.append([child, v, point])
  
print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
n, q = map(int, input().split())
Connections = dd(list)
for i in range(n-1):
    a, b = map(int, input().split())
    Connections[a].append(b)
    Connections[b].append(a)

#Tree[node] -> children(list)
Tree = dd(list)
visited = set()
stack = [1]
while stack != []:
    temp = []
    for taregt_node in stack:
        for next_node in Connections[taregt_node]:
            if next_node not in visited:
                Tree[taregt_node].append(next_node)
                visited.add(taregt_node)
                temp.append(next_node)
    stack = temp
#print(Tree)

#Point[node] -> point
Point = dd(int)
for i in range(q):
    p, x = map(int, input().split())
    Point[p] += x
#print(Point)

Counter = dd(int)
#visited = set()
stack = [1]
Counter[1] = Point[1]
while stack != []:
    temp = []
    for target_node in stack:
        for next_node in Tree[target_node]:
            Counter[next_node] = Counter[target_node] + Point[next_node]
            temp.append(next_node)
    stack = temp
#print(Counter)

for i in range(1, n):
    print(Counter[i], end=" ")
print(Counter[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

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

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

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


def function(now, count):
    ans[now] += count
    for i in tree[now]:
        if checked[i] == False:
            checked[i] = True
            function(i, ans[now])

function(0, 0)

for a in ans:
    print(a)