Problem:


Score : 400 points

Problem Statement

Given is a rooted tree with N vertices numbered 1 to N.
The root is Vertex 1, and the i-th edge (1 \leq i \leq N - 1) connects Vertex a_i and b_i.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0.

Now, the following Q operations will be performed:

Operation j (1 \leq j \leq Q): Increment by x_j the counter on every vertex contained in the subtree rooted at Vertex p_j.

Find the value of the counter on each vertex after all operations.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq Q \leq 2 \times 10^5

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

Sample Input 1

4 3
1 2
2 3
2 4
2 10
1 100
3 1

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:

Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.

Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.

Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Sample Input 2

6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10

Sample Output 2

20 20 20 20 20 20



Sample input:
4 3
1 2
2 3
2 4
2 10
1 100
3 1


Sample output:
100 110 111 110

Submission status: Accepted

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

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

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

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

next = [0]
s_next = {0}
for i in next:
    for v in edge[i]:
        if v in s_next:
            continue
        s_next.add(v)
        next.append(v)
        cost[v] += cost[i]

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

Submission status: Accepted

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

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

done = [0] * n
key = [1]

while key:
  pos = key.pop()
  done[pos-1] = 1
  for j in parents[pos-1]:
    if done[j-1] != 1:
      points[j-1] += points[pos-1]
      key.append(j)
  
print(*points)

Submission status: Accepted

Solution code:
import sys

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])

def main():
    N,Q = LI()
    node=[[] for _ in range(N)]
    flag = [True for _ in range(N)]
    for _ in range(N-1):
        a,b = LI()
        node[a-1].append(b-1)
        node[b-1].append(a-1)

    counter = [0] * N
    for _ in range(Q):
        p,x = LI()
        counter[p-1] += x

    que = [[0,0]]
    while que:
        a,c = que.pop()
        flag[a]=False
        counter[a]+=c
        for b in node[a]:
            if flag[b]:
                que.append([b,counter[a]])

    r = [counter[i] for i in range(N)]

    return(" ".join(map(str,r)))

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def main():
    N,Q = LI()
    node=[[] for _ in range(N)]
    flag = [True for _ in range(N)]
    for _ in range(N-1):
        a,b = LI()
        node[a-1].append(b-1)
        node[b-1].append(a-1)

    counter = [0] * N
    for _ in range(Q):
        p,x = LI()
        counter[p-1] += x

    cur = [[0,0]]
    while cur:
        nxt = []
        for a,c in cur:
            flag[a]=False
            counter[a]+=c
            for b in node[a]:
                if flag[b]:
                    nxt.append([b,counter[a]])
        cur = [x for x in nxt]

    r = [counter[i] for i in range(N)]

    return(" ".join(map(str,r)))

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
# ABC138 D - Ki
from collections import deque
N,Q = map(int, input().split())
G = [[] for _ in range(N)]

c = [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())
    c[p-1] += x

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

while q:
    v = q.pop()
    flg[v] = True
    for e in G[v]:
        if flg[e]:
            continue
        c[e] += c[v]
        q.append(e)
print(*c)

Submission status: Accepted

Solution code:
n,q = (int(i) for i in input().split())
v,k,ans = [1]*(n+1),[[] for i in range(n+1)],[0]*(n+1)
v[1],y = 0,[1]
for i in range(n-1):
    a,b = (int(i) for i in input().split())
    k[a].append(b)
    k[b].append(a)
for i in range(q):
    p,x = (int(i) for i in input().split())
    ans[p]+=x
v[1] = 0
while y:
    p = y.pop()
    v[p] = 0
    for i in k[p]:
        if v[i]:
            ans[i]+=ans[p]
            y.append(i)
print(" ".join(map(str,ans[1:])))

Submission status: Accepted

Solution code:
from collections import deque

n, q = [int(i) for i in input().split()]

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

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

queue = deque([[0,1]])
while queue:
    parent, node = queue.popleft()
    for leaf in tree[node]:
        if leaf == parent:
            continue
        counter[leaf] += counter[node]
        queue.append([node, leaf])

print(*counter[1:])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 7)
    
    
    N, Q = map(int, input().split())
    
    T = [[]for i in range(N)]
    
    for i in range(N-1):
        a, b = map(int, input().split())
        T[a-1].append(b-1)
        T[b-1].append(a-1)
    
    X = [0 for i in range(N)]
    for i in range(Q):
        p, x = map(int, input().split())
        X[p-1] += x
    
    def dfs(x, p):
        for j in T[x]:
            if j == p:
                continue
            X[j] += X[x]
            dfs(j, x)
    
    dfs(0, -1)
    
    for i in range(N):
        print(X[i], end =" ")
main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

que = deque()

for a in tree[0]:
  que.append([0,a])
  #[親ノード,子ノード].ここでは頂点1に隣接している頂点の組をキューに加えている

while que:
    parent, node = que.popleft()
    #親ノードのカウンターは子ノードに遺伝する
    counter[node] += counter[parent]
    for leaf in tree[node]:
      if leaf != parent:
        que.append([node, leaf]) #子ノードの葉をキューに加える　      

print(*counter)

Submission status: Accepted

Solution code:
from collections import deque
import sys

n, q, *args = map(int, open(0).read().split())
ab = args[:(n-1)*2]
px = args[(n-1)*2:]

tree = [[] for _ in range(n+1)]
for a, b in zip(*[iter(ab)]*2):
    tree[a].append(b)
    tree[b].append(a)

counter = [0] * (n+1)
for p, x in zip(*[iter(px)]*2):
    counter[p] += x

# pop, appendまたはQueueライブラリだと間に合わない
queue = deque([[0,1]])
while queue:
    parent, node = queue.popleft()
    for leaf in tree[node]:
        if leaf == parent:
            continue
        counter[leaf] += counter[node]
        queue.append([node, leaf])

print(*counter[1:])

Submission status: Accepted

Solution code:
from collections import deque
import sys
s = sys.stdin.readlines()

n, q = map(int, s[0].split())

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

counter = [0] * (n+1)
for px in s[n:]:
    p, x = map(int, px.split())
    counter[p] += x

# pop, appendまたはQueueライブラリだと間に合わない
queue = deque([[0,1]])
while queue:
    parent, node = queue.popleft()
    for leaf in tree[node]:
        if leaf == parent:
            continue
        counter[leaf] += counter[node]
        queue.append([node, leaf])

print(*counter[1:])

Submission status: Accepted

Solution code:
from collections import deque

n, q = [int(i) for i in input().split()]
ab = [[int(i) for i in input().split()] for _ in range(n-1)]
px = [[int(i) for i in input().split()] for _ in range(q)]

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

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

# pop, appendまたはQueueライブラリだと間に合わない
queue = deque([[0,1]])
while queue:
    parent, node = queue.popleft()
    for leaf in tree[node]:
        if leaf == parent:
            continue
        counter[leaf] += counter[node]
        queue.append([node, leaf])

print(*counter[1:])

Submission status: Accepted

Solution code:
# ABC138D - Ki
from collections import deque
 
 
def dfs() -> None:
    # pop, appendまたはQueueライブラリだと間に合わない
    queue = deque([[0,1]])
    while queue:
        parent, node = queue.popleft()
        for leaf in T[node]:
            if leaf == parent:
                continue
            counter[leaf] += counter[node]
            queue.append([node, leaf])
 
 
def main():
    # Ai (A[i][0]) may be not a parent of Bi (A[i][1])
    global T, counter
    N, Q, *A = map(int, open(0).read().split())
    E, P = A[: (N - 1) * 2], A[(N - 1) * 2 :]
    T = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(E)] * 2):
        T[v].append(u), T[u].append(v)
    counter = [0] * (N + 1)
    for p, x in zip(*[iter(P)] * 2):
        counter[p] += x  # increase vertex p by x
    dfs()
    print(*counter[1:])
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# https://atcoder.jp/contests/abc138/tasks/abc138_d

# n: 頂点の数 ((n-1)回エッジを作る)
# q: 頂点に整数を足し込む操作の回数
n, q = map(int, input().split())

values = [0 for _ in range(n)]  # n 個の頂点の値はすべて 0 で初期化する
links = [[] for _ in range(n)]  # n 番目の頂点が、エッジを伸ばしている先の頂点のリスト

# 木の構築
for _ in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    links[a].append(b)
    links[b].append(a)

# 初期値の挿入
for _ in range(q):
    node, value = map(int, input().split())
    node -= 1  # 0 オリジン対応
    values[node] += value

# 値の伝播
stack = [(0, -1)]  # (頂点の番号, 親頂点の番号) を stack につめて、空になるまでイテレートする
while 0 < len(stack):
    node, parent = stack.pop()
    for link in links[node]:
        if link == parent:
            continue
        values[link] += values[node]
        stack.append((link, node))

print(*values)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# https://atcoder.jp/contests/abc138/tasks/abc138_d


def main():
    n, q = map(int, input().split())
    values = [0] * n
    links = [[] for _ in range(n)]

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

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

    s = [(0, -1)]
    while s:
        i, p = s.pop()
        for j in links[i]:
            if j == p:
                continue
            values[j] += values[i]
            s.append((j, i))

    print(*values)


main()

Submission status: Accepted

Solution code:
import sys
import collections
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N, Q = map(int, input().split())
graph = collections.defaultdict(list)
for _ in xrange(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

values = [0] * (1+N)
for _ in xrange(Q):
    a, b = map(int, input().split())
    values[a] += b
q = [(0, 1)]
while q:
    parent, child = q.pop()
    values[child] += values[parent]
    for i in graph[child]:
        if i == parent: continue
        q.append((child, i))
ans = ' '.join(map(str, values[1:]))
print(ans)

Submission status: Accepted

Solution code:
n, q = (int(x) for x in input().split())

E = [[] for i in range(n + 1)]

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

P = []
X = []


for i in range(q):
    p, x = (int(x) for x in input().split())
    P.append(p)
    X.append(x)

c = [0] * (n + 1)

for i in range(len(P)):
    c[P[i]] += X[i]


checked = [False] * (n + 1) #探索済みか否か
stac = [1] #探索対象

# dig(1,-1,0)

while stac:
    th = stac.pop() #新しい探索対象
    checked[th] = True #訪問済み

    for i in  E[th]: #そこに隣接するエッジ
        if checked[i] == False: #探索済みで無かったら
            c[i] += c[th]
            stac.append(i)
result = map(str, c[1:])
print(" ".join(result))

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
es = [[] for i in range(N)]
value = [0]*N

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

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

stuck = [0]
log = [1]*N
log[0] = 0

while stuck:
  e = stuck.pop()
  for f in es[e]:
    if log[f]:
      log[f] = 0
      value[f] += value[e]
      stuck += [f]

ans = [str(v) for v in value]
print(' '.join(ans))

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
es = [[] for i in range(N)]
value = [0]*N

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

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

stuck = [0]
log = [1]*N
log[0] = 0

while stuck:
  e = stuck.pop()
  for f in es[e]:
    if log[f]:
      log[f] = 0
      value[f] += value[e]
      stuck += [f]

print(*value)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
es = [[] for i in range(N)]
value = [0]*N

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

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

stuck = [0]
log = [1]*N
log[0] = 0

while stuck:
  e = stuck.pop()
  for f in es[e]:
    if log[f]:
      log[f] = 0
      value[f] += value[e]
      stuck += [f]

ans = [str(v) for v in value]
print(*ans)

Submission status: Accepted

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


#import scipy.optimize
#import numpy as np

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

if __name__ == "__main__":
    Input1 = [input() for i in range(1)]
    N,Q = list(map(int,Input1[0].split()))
    Input2 = [input() for i in range(1,N+Q)]
    a = [0]*(N-1)
    b = [0]*(N-1)
    p = [0]*(Q)
    x = [0]*Q
    for i in range(N-1):
        a[i],b[i] = list(map(int,Input2[i].split()))
    for i in range(N-1,N-1+Q):
        p[i+1-N],x[i+1-N] = list(map(int,Input2[i].split()))

##    Node = [1]*(N+1)
##    for i in range(N-1):
##        Node[b[i]] = a[i]
##    Root = [False]*(N+1)
##    Root[1] = True
##    Parent = [[],[1]]
##    for i in range(2,N+1):
##        Parent.append([i])
##        j = i
##        temp = Node[j]
##        Parent[i] = Parent[i]+Parent[temp]
##        while Root[i]==False:
##            if any([Root[k] for k in Parent[i]]):
##                Root[i]=True
##            else:
##                j = Node[j]
##                Parent[i] = Parent[i]+Parent[j]

    graph = [[] for i in range(N+1)]
    for i in range(N-1):
        graph[a[i]].append(b[i])
        graph[b[i]].append(a[i])

    
    Cntr = [0]*(N+1)
    for i in range(Q):
        Cntr[p[i]] += x[i]
        
    q=[(0,1)]
    while q:
        parent,child = q.pop()
        Cntr[child]+=Cntr[parent]
        for i in graph[child]:
            if i==parent:
                continue
            q.append((child,i))
    print(' '.join(map(str,Cntr[1:])))

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

deq = deque([0])
visited = [False] * N
while deq:
    parent = deq.popleft()
    edge = graph_lis[parent]
    for v in edge:
        if not visited[v]:
            ans[v] += ans[parent]
            deq.append(v)
    visited[parent] = True
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
 
if __name__ == "__main__":
    N, q = map(int, input().split())
    links = [[] for _ in range(N)]
    
    for i in range(N - 1):
        a, b = map(int, input().split())
        links[a - 1].append(b - 1)
        links[b - 1].append(a - 1)
    
    ans = [0] * N
    for i in range(q):
        p, x = map(int, input().split())
        ans[p - 1] += x

    deq = deque([0])
    visited = [False] * N
    while deq:
        parent = deq.popleft()
        link = links[parent]
        for v in link:
            if not visited[v]:
                ans[v] += ans[parent]
                deq.append(v)
        visited[parent] = True
    
    print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
Q=deque()
Q.append((0,1))
n,q=map(int,input().split())
edges=[[] for i in range(n+1)]
cnt=[0 for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  edges[a].append(b)
  edges[b].append(a)
for i in range(q):
  p,x=map(int,input().split())
  cnt[p]+=x
while(Q):
  k=Q.popleft()
  cnt[k[1]]+=cnt[k[0]]
  for i in edges[k[1]]:
    if i!=k[0]:
      Q.append((k[1],i))
for i in range(1,n+1):
  print(cnt[i], end=" ")

Submission status: Accepted

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

n,q=map(int,input().split())
ab=[[int(i) for i in input().split()] for j in range(n-1)]
px=[[int(i) for i in input().split()] for j in range(q)]

graph=[[] for i in range(n+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
    
value=[0]*(n+1)

for p,x in px:
    value[p]+=x
    
q=[(0,1)]
while q:
    parent,child = q.pop()
    value[child]+=value[parent]
    for i in graph[child]:
        if i==parent:
            continue
        q.append((child,i))
ans=' '.join(map(str,value[1:]))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
n,q=map(int,input().split())
ab=[[int(i) for i in input().split()] for j in range(n-1)]
px=[[int(i) for i in input().split()] for j in range(q)]

graph=[[] for i in range(n+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
    
value=[0]*(n+1)

for p,x in px:
    value[p]+=x
    
q=[(0,1)]
while q:
    parent,child = q.pop()
    value[child]+=value[parent]
    for i in graph[child]:
        if i==parent:
            continue
        q.append((child,i))
ans=' '.join(map(str,value[1:]))
print(ans)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
ab=[[int(i) for i in input().split()] for j in range(n-1)]
px=[[int(i) for i in input().split()] for j in range(q)]

graph=[[] for i in range(n+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
    
value=[0]*(n+1)

for p,x in px:
    value[p]+=x
    
q=[(0,1)]
while q:
    parent,child = q.pop()
    value[child]+=value[parent]
    for i in graph[child]:
        if i==parent:
            continue
        q.append((child,i))
ans=' '.join(map(str,value[1:]))
print(ans)

Submission status: Accepted

Solution code:
import collections
import sys

input = sys.stdin.readline

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

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

remaining = collections.deque([[0, 1]])
while len(remaining) > 0:
    a, b = remaining.popleft()
    ps[b] += ps[a]
    for c in es[b]:
        if c != a:
            remaining.append([b, c])
print(*ps[1:])

Submission status: Accepted

Solution code:
# dfs(深さ優先探索)

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

num_list = [0] * (N+1)

tree_list = [[] for _ in range(N+1)]

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

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

q = [1]
checked = [0] * (N+1)

while q:
    v=q.pop()
    checked[v] = 1
    for u in tree_list[v]:
        if checked[u] == 1:
            continue
        num_list[u] += num_list[v]
        q.append(u)

print(*num_list[1:])

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

queue = deque()
queue.append((0, -1))
while queue:
  q = queue.popleft()
  if q[0] != 0:
    cnt[q[0]] += cnt[q[1]]
  for i in to[q[0]]:
    if i != q[1]:
      queue.append((i, q[0]))

for c in cnt:
  print(c)

Submission status: Accepted

Solution code:
from collections import deque
n, Q = map(int, input().split())
edges = [[] for _ in range(n+1)]
count = [0]*(n+1)
q = deque()
q.append((1, 0))

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

while(q):
    k = q.popleft()
    count[k[0]] += count[k[1]]
    for i in edges[k[0]]:
        if not i == k[1]:
            q.append((i, k[0]))

print(*count[1:])

Submission status: Accepted

Solution code:
# ABC138D - Ki
from collections import deque


def main():
    # Ai (A[i][0]) may be not a parent of Bi (A[i][1])
    global T, cnt
    N, Q, *A = map(int, open(0).read().split())
    E, P = A[: (N - 1) * 2], A[(N - 1) * 2 :]
    T = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(E)] * 2):
        T[v].append(u), T[u].append(v)
    cnt = [0] * (N + 1)
    for p, x in zip(*[iter(P)] * 2):
        cnt[p] += x  # increase vertex p by x
    stack = deque([(1, -1)])
    while stack:
        v, p = stack.popleft()
        x = cnt[v]
        for u in T[v]:
            if u != p:
                cnt[u] += x
                stack.append((u, v))
    print(*cnt[1:])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC138D - Ki
from collections import deque


def dfs(r: int) -> None:
    stack = deque([(r, -1)])
    while stack:
        v, p = stack.popleft()
        x = cnt[v]
        for u in T[v]:
            if u != p:
                cnt[u] += x
                stack.append((u, v))


def main():
    # Ai (A[i][0]) may be not a parent of Bi (A[i][1])
    global T, cnt
    N, Q, *A = map(int, open(0).read().split())
    E, P = A[: (N - 1) * 2], A[(N - 1) * 2 :]
    T = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(E)] * 2):
        T[v].append(u), T[u].append(v)
    cnt = [0] * (N + 1)
    for p, x in zip(*[iter(P)] * 2):
        cnt[p] += x  # increase vertex p by x
    dfs(1)
    print(*cnt[1:])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC138D - Ki
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def dfs(v: int, p: int) -> None:
    x = cnt[v]
    for u in T[v]:
        if u != p:
            cnt[u] += x  # cumulative sum
            dfs(u, v)


def main():
    # Ai (A[i][0]) may be not a parent of Bi (A[i][1])
    global T, cnt
    N, Q, *A = map(int, open(0).read().split())
    E, P = A[: (N - 1) * 2], A[(N - 1) * 2 :]
    T = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(E)] * 2):
        T[v].append(u), T[u].append(v)
    cnt = [0] * (N + 1)
    for p, x in zip(*[iter(P)] * 2):
        cnt[p] += x  # increase vertex p by x
    dfs(1, -1)
    print(*cnt[1:])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit as SRL, stdin, stdout

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

n, q = rrd()

v = [[] for _i in range(n + 10)]

for i in range(n - 1):
    x, y = rrd()
    v[x].append(y)
    v[y].append(x)

add = [0] * (n + 10)

for i in range(q):
    p, x = rrd()
    add[p] += x

p = [(1, 0)]
vis = [0] * (n + 2)
while len(p):
    now, fa = p.pop()
    add[now] += add[fa]
    vis[now] = 1
    for i in v[now]:
        if not vis[i]:
            p.append((i,now))

stdout.write(" ".join(map(str, add[1:n + 1])))

Submission status: Accepted

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

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

ab_list = [list(map(int,list(input().split()))) for _ in range(N-1)]  
px_list = [list(map(int,list(input().split()))) for _ in range(Q)]  

graph = [[] for _ in range(N+1)]
point_list = [0] * (N+1)

for a, b in ab_list:
    graph[a].append(b)
    graph[b].append(a)
    
for p, x in px_list:
    point_list[p] += x
    
def add_point(num, root, point):    
    point_list[num] += point   
    for g in graph[num]:
        if g == root:
            continue
        add_point(g, num, point_list[num])

add_point(1, 0, 0)
 
print(*(point_list[1:]))

Submission status: Accepted

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

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

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

counter = [0 for _ in range(N)]

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

while len(search_list) > 0:
    now = search_list.pop()
    is_visit[now] = True
    now_count = counter[now]
    for p in connections[now]:
        if is_visit[p]:
            continue
        search_list.append(p)
        counter[p] += now_count

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

Submission status: Accepted

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

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


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

    px[p-1] += x

visited = [False] * N

stack = [0]
while stack:
    i = stack.pop()
    ans[i] += px[i]
    visited[i] = True
    for j in es[i]:
        #print(i,j,es)
        if visited[j] == False:
            ans[j] += ans[i]
            stack.append(j)
    

print(*ans)

Submission status: Accepted

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

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


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

    px[p-1] += x

visited = [False] * N
from collections import deque
stack = deque([0])
while stack:
    i = stack.popleft()
    ans[i] += px[i]
    visited[i] = True
    for j in es[i]:
        #print(i,j,es)
        if visited[j] == False:
            ans[j] += ans[i]
            stack.append(j)
    

print(*ans)

Submission status: Accepted

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

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

if __name__ == "__main__":
    N, Q = [int(_) for _ in stdin.readline().rstrip().split()]
    graph = [[] for i in range(N+1)]
    count = [0]*(N+1)
    for i in range(N-1):
        a, b = [int(_) for _ in stdin.readline().rstrip().split()]
        graph[a].append(b)
        graph[b].append(a)
    for i in range(Q):
        p, x = [int(_) for _ in stdin.readline().rstrip().split()]
        count[p] += x
    dfs(1, 0)
    print(*count[1:])

Submission status: Accepted

Solution code:
from collections import deque
 
# BFSで通す
N, Q = map(int, input().split())  # N頂点, Q個の命令
 
G = [[] for _ in range(N)]
count = [0]*N
for i in range(N-1):  # 辺はN-1本
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
 
for i in range(Q):  # Q個の操作について
    p, x = map(int, input().split())
    count[p-1] += x
 
q = deque([0])
flag = [False]*N
 
while len(q):
    v = q.pop()
    flag[v] = True
    for e in G[v]:  # vを親にもつノードについてループを回す
        if flag[e]:  # 頂点eに到達済みであれば
            continue
        count[e] += count[v]  # それぞれの子たちに親の値を伝播させる
        q.append(e)
 
print(*count)

Submission status: Accepted

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

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

point = [0]*n
for p,x in px:
	point[p-1] += x

ans = [0]*n
ans[0] = point[0]
visited = [False]*n
visited[0] = True
stock = [0]

while stock:
	# print('while')
	# print(stock)
	# print(ans)
	s = stock.pop()
	for p in pea[s]:
		# print('for')
		if visited[p]:
			continue
		# print(s,p)
		# print()
		visited[p] = True
		stock.append(p)
		ans[p] = ans[s]+point[p]
print(*ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
 
 
n,q = na()
g = [[] for i in range(n)]
c = [0]*n
 
for i in range(n-1):
    a,b = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
for i in range(q):
    p,x = na()
    c[p-1] += x
 
def f(b,a,r):
    r += c[a]
    c[a] = r
    for i in g[a]:
        if i != b:
            f(a,i,r)
 
f(-1,0,0)
print(' '.join([str(s) for s in c]))

Submission status: Accepted

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

N,Q = map(int,input().split())
AB = [[x for x in map(int,input().split())] for _ in range(N-1)]
PX = [[x for x in 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)
 
cnt = [0]*N
for p,x in PX:
    cnt[p-1] += x
 
def dfs(v):
    for w in graph[v]:
        cnt[w-1] += cnt[v-1]
        graph[w].remove(v)
        if len(graph[w]) > 0:
            dfs(w)
 
dfs(1)
 
print(*cnt)