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
inputs = lambda:map(int, input().split())
n, q = inputs()
e = [[] for _ in range(n)]
counter = [0] * n
m = n-1
for _ in range(m):
    v1, v2 = inputs()
    v1 -= 1
    v2 -= 1
    e[v1] += v2,
    e[v2] += v1,
for _ in range(q):
    p, x = inputs()
    p -= 1
    counter[p] += x
used = [False] * n
s = 0
used[s] = True
stack = [s]
while stack:
    s = stack.pop()
    for c in e[s]:
        if used[c]:
            None
        else:
            used[c] = True
            counter[c] += counter[s]
            stack += c,
print(*counter)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g
 
def main():
    n,q=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    tuple(g)
    px=[]
    for _ in range(q):
        px.append(tuple(inpl()))
    ans=[0 for _ in range(n)]
    went=[False for _ in range(n)]
    went[0]=True
    for i in range(q):
        ans[px[i][0]-1]+=px[i][1]
    que=deque()
    que.append(0)
    while que:
        par = que.pop()
        for chi in g[par]:
            if went[chi]:
                continue
            else:
                went[chi]=True
                ans[chi]+=ans[par]
                que.append(chi)
    
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    n,q=map(int,input().split())
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    p=[0]*q
    x=[0]*q
    for i in range(q):
        p[i],x[i] = map(int,input().split())
        
    px=[[] for i in range(n)]
    for pp,xx in zip(p,x):
        px[pp-1].append(xx)
    px=[sum(i) for i in px]
    c=[0]*n
    flag=[True]*n
     
    from collections import deque
    q = deque([(-1,0,0)])
    while q:
        parent,child,point = q.popleft()
        if parent!=-1:
            flag[parent]=False
        point+=px[child]
        c[child]=point
        for y in tree[child]:
            if y == parent:
                continue
            if flag[y]:
                q.append((child,y,point))
    print(*c)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def dfs(i, V, E, x):
    S = [i]
    while(len(S) > 0):
        vi = S.pop()
        p = x[vi]
        for j in E[vi]:
            if V[j] == 0:
                V[j] = 1
                x[j] += p
                S.append(j)
    return V, x

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

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

V[1] = 1
dfs(1, V, E, x)
print(*x[1:])

Submission status: Accepted

Solution code:
from collections import defaultdict

def dfs(i, V, E, x):
    S = [i]
    while(len(S) > 0):
        vi = S.pop()
        p = x[vi]
        for j in E[vi]:
            if V[j] == 0:
                V[j] = 1
                x[j] += p
                S.append(j)
    return V, x

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

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

V[1] = 1
V, x = dfs(1, V, E, x)
print(*x[1:])

Submission status: Accepted

Solution code:
from collections import defaultdict

def dfs(i, V, E, x):
    S = [i]
    while(len(S) > 0):
        vi = S.pop()
        p = x[vi]
        for j in E[vi]:
            if V[j] == 0:
                V[j] = 1
                x[j] += p
                S.append(j)
    return V, x

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

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

V[1] = 1
V, x = dfs(1, V, E, x)
print(*x[1:])

Submission status: Accepted

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


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


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


used = [False for _ in range(N)]
used[0] = True
buf = [0]
while len(buf) > 0:
    i = buf.pop()
    for child in graph[i]:
        if not used[child]:
            counts[child] += counts[i]
            buf.append(child)
            used[child] = True


print(' '.join(list(map(str, counts))))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    inputs = lambda:map(int, input().split())
    n, q = inputs()
    e = [[] for _ in range(n)]
    counter = [0] * n
    m = n-1
    for _ in range(m):
        v1, v2 = inputs()
        v1 -= 1
        v2 -= 1
        e[v1] += v2,
        e[v2] += v1,
    for _ in range(q):
        p, x = inputs()
        p -= 1
        counter[p] += x
    used = [False] * n
    s = 0
    used[s] = True
    stack = [s]
    while stack:
        s = stack.pop()
        for c in e[s]:
            if used[c]:
                None
            else:
                used[c] = True
                counter[c] += counter[s]
                stack += c,
    print(*counter)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    入力 = sys.stdin.readline
    範囲, 出力 = range, print
    真, 偽 = True, False
    何もしない = None
    一行に複数個の入力 = lambda:map(int, 入力().split())
    頂点の数, 操作回数 = 一行に複数個の入力()
    辺 = [[] for _ in 範囲(頂点の数)]
    カウンター = [0] * 頂点の数
    辺の数 = 頂点の数-1
    for _ in 範囲(辺の数):
        頂点1, 頂点2 = 一行に複数個の入力()
        頂点1 -= 1
        頂点2 -= 1
        辺[頂点1] += 頂点2,
        辺[頂点2] += 頂点1,
    for _ in 範囲(操作回数):
        頂点, 足す値 = 一行に複数個の入力()
        頂点 -= 1
        カウンター[頂点] += 足す値
    到達済み = [偽] * 頂点の数
    親 = 0
    到達済み[親] = 真
    スタック = [親]
    while スタック:
        親 = スタック.pop()
        for 子 in 辺[親]:
            if 到達済み[子]:
                何もしない
            else:
                到達済み[子] = 真
                カウンター[子] += カウンター[親]
                スタック += 子,
    出力(*カウンター)
main()

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
L = [0]*(n+1)
graph = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
for i in range(q):
    a,b = map(int,input().split())
    L[a] += b
q = [(1,0)]
while len(q) > 0:
    c = q.pop()
    x, par = c[0], c[1]
    L[x] += L[par]
    for child in graph[x]:
        if par == child:
            continue
        q.append((child,x))
print(' '.join(map(str,L[1:])))

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect

MOD = 10**9+7

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

node = [0]*N
edge = [[] for _ in range(N)]
color = [0]*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)

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

stack = [0]
while stack:
    s = stack.pop()
    color[s] = 1
    for t in edge[s]:
        if color[t]==0:
            stack.append(t)
            node[t] += node[s]
    color[s]=2

for n in node:
    print(n)

Submission status: Accepted

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

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

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

#print(Graph)
Value = [0]*(n+1)
for p,x in PX:
    Value[p] += x
#print(Value)

q = [(1,0)]
while q:
    x,parent = q.pop()
    Value[x] += Value[parent]  #親の値を子に入れる
    for y in Graph[x]:
        if y == parent:
            continue
        q.append((y,x))
print(*Value[1:])

Submission status: Accepted

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

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

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

#print(Graph)
Value = [0]*(n+1)
for p,x in PX:
    Value[p] += x
#print(Value)

q = [(1,0)]
while q:
    x,parent = q.pop()
    Value[x] += Value[parent]  #親の値を子に入れる
    for y in Graph[x]:
        if y == parent:
            continue
        q.append((y,x))
print(*Value[1:])

Submission status: Accepted

Solution code:
from collections import deque
N, Q = map(int, input().split())  # N頂点の木, Q回の操作
tree = [[] for _ in range(N)]  # N頂点の木を構築する
visited = [False]*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())
    p -= 1
    counter[p] += x
# print(counter)
# exit()
q = deque([0])
visited[0] = True
while len(q):
    v = q.pop()
    for e in tree[v]:  # 親の値を伝播させていく
        if visited[e]:
            continue
        visited[e] = True
        counter[e] += counter[v]
        q.append(e)

print(*counter)

Submission status: Accepted

Solution code:
N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]

query_list = [input().split() for k in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]

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

linked_node_list = [[] for _ in range(N)]

for a, b in tree_list:
    a, b = int(a)-1, int(b) -1
    linked_node_list[a].append(b)
    linked_node_list[b].append(a)


for index, val in query_list_int:
    val_list[index-1] += val

stack = [0]
parent = [0] * (N+1)

while True:
    v=stack.pop()
    for child in linked_node_list[v]:
        if child != parent[v]:
            parent[child] = v
            stack.append(child)
            val_list[child] += val_list[v]
    if not stack:
        break

print(*val_list)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, q = map(int, input().split())
d = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append(b)
    d[b].append(a)
d2 = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    d2[p-1] += x

ans = [0] * n

from collections import deque

def dfs(cur, pre, point):
    stack = deque([[cur, pre, point]])
    while stack:
        cur, pre, point = stack.pop()
        point += d2[cur]
        ans[cur] = point
        for e in d[cur]:
            if e != pre:
                stack.append([e, cur, point])

dfs(0, -1, 0)
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7

    n, q = list(map(int, readline().split()))
    tmd = collections.defaultdict(list)
    for i in range(n-1):
        tma, tmb = list(map(int, readline().split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]
    score = [0] * n
    for i in range(q):
        p, x = list(map(int, readline().split()))
        score[p-1] += x

    ql = [[0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0]
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    score[tmv] += score[tmp]
                    ql.append([cost + 1, tmv])
                    fq[tmv]
        else:
            break
    print(*score)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

es=[[] for _ in range(n)]
for a,b in AB:
  a,b=a-1,b-1
  es[a].append(b)
  es[b].append(a)
  
cnt=[0]*n
for p,x in PX:
  cnt[p-1]+=x

ans=[0]*n
ans[0]=cnt[0]
visited=[0]*n
stack=[0]
while stack:
  v=stack.pop()
  visited[v]=1
  for to in es[v]:
    if visited[to]: continue
    stack.append(to)
    ans[to]=ans[v]+cnt[to]
print(*ans)

Submission status: Accepted

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

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

adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
tree_value = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    tree_value[p] += x
searched = set()
"""
def dfs(node, count):
    searched.add(node)
    tree_value[node] += count
    for i in adjacent_list[node]:
        if i not in searched:
            dfs(i, tree_value[node])
"""
used = [0 for i in range(n+1)]
que = Queue()
que.put(1)
while que.qsize() != 0:
    m = que.get()
    used[m] = 1
    for i in adjacent_list[m]:
        if not used[i]:
            tree_value[i] += tree_value[m]
            que.put(i)
for i in range(1,n+1):
    print("{} ".format(tree_value[i]), end = "")

Submission status: Accepted

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

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

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

# 頂点1から順番に処理
stack = [1]

parent = [0] * (N+1)

# 頂点xと繋がっている頂点yをそれぞれ調べ、yがxの親である場合は何もしない。
# yがxの親でない場合は、yがxの子であるため、yの親としてxを登録し、次の処理対象としてstackし、yのカウンターにxの値を足す
while stack:
    # stackから頂点を1つ取り出す
    x = stack.pop()
    # stackから取り出した頂点とつながっている頂点それぞれについて処理
    for y in graph[x]:
        # yがxの親（xがyの子）
        if y == parent[x]:
            # 何もしない
            pass
        #xがyの親（yがxの子）
        else:
            # 頂点x, y繋がっているためどちらかが必ず親なので、xをyの親として登録
            parent[y] = x
            # yをxの子としてstack
            stack.append(y)
            # yのカウンターにxの値を足す
            val[y] += val[x]

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

Submission status: Accepted

Solution code:

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
from collections import deque
N,Q=map(int,input().split())
G=[[] for _ in range(N)]
count=[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())
    count[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
        count[e]+=count[v]
        q.append(e)
print(*count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

count = [0 for i in range(N + 1)]
visited = [False for i in range(N+1)]

stack = [(1, 0)]
while stack:
    root, curCount = stack.pop()
    
    visited[root] = True
    curCount += tally[root]
    count[root] = curCount
    for neighbour in edges[root]:
        if visited[neighbour]: continue
        stack.append((neighbour, curCount))

print(*count[1:])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
G = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
C = [0]*(N)
for i in range(Q):
    p,x = map(int,input().split())
    C[p-1] += x
from collections import deque
d=deque()
d.append(0)
t = [False]*(N)
t[0] = True
while d:
    a = d.popleft()
    for b in G[a]:
        if not t[b]:
            t[b] = True
            d.append(b)
            C[b] += C[a]
print(*C)

Submission status: Accepted

Solution code:
from collections import deque

n, q = map(int,input().split())
g = [[] for _ in range(n)] # グラフを格納
count = [0 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) # どちらが根かわからない

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

que = deque()
que.append(0)

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

while que:
    i = que.popleft()
    watch[i] = True
    for e in g[i]:
        if watch[e] == True: continue
        count[e] += count[i]
        que.append(e)

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
tree = {}
ans = []
ans.extend([0 for _ in range(N)])

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

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

sta = [(0, 0)]
while sta:
    k, p = sta.pop()
    for c in tree.get(k, []):
        if c == p:
            continue
        ans[c] += ans[k]
        sta.append((c, k))

print(' '.join([str(x) for x in ans]))

Submission status: Accepted

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

N, Q = map(int ,input().split())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
	at,bt = map(int ,input().split())
	E[at].append(bt)
	E[bt].append(at)
cnt = [0 for _ in range(N+1)]
for _ in range(Q):
	pt,xt = map(int, input().split())
	cnt[pt] += xt

flg = [0 for _ in range(N+1)]
q = [[1,-1]]
while q:
	cp, root = q.pop()
	for np in E[cp]:
		if np == root:
			continue
		cnt[np] += cnt[cp]
		q.append([np,cp])

cnt.pop(0)
for c in cnt:
	print(c, end = " ")
print()

Submission status: Accepted

Solution code:
from collections import deque

N,Q=map(int,input().split())
out=[set() for i in range(N+1)];out[0]=None # 頂点は1-initial
for j in range(N-1):
    a,b=map(int,input().split())
    out[a].add(b)
    out[b].add(a)
# print(out) #DB

a=[0 for i in range(N+1)];a[0]=None

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

# print(a) #DB

q=deque()
q.append(1)
while q:
    u=q.popleft()
    for v in out[u]:
        a[v]+=a[u]
        q.append(v)
        out[v].remove(u)
        # print(q) #DB
    out[u].clear()

print(*a[1:])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import deque
    N, Q = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    cost = [0]*N
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    for _ in range(Q):
        p, x = (int(i) for i in input().split())
        cost[p-1] += x

    def bfs(s):
        G_color = ['WHITE' for _ in range(len(G))]
        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'
                    cost[v] += cost[u]
                    Q.append(v)
            G_color[u] = 'BLACK'

    bfs(0)
    print(*cost)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
sys.setrecursionlimit(10 ** 9)



INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, q = LI()
G = [[] for _ in range(n)]
for a, b in LIR(n - 1):
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

D = [0] * n
for p, x in LIR(q):
    D[p - 1] += x


que = deque([0])
visited = [0] * n
visited[0] = 1
while que:
    u = que.popleft()
    for v in G[u]:
        if visited[v] == 0:
            visited[v] = 1
            D[v] += D[u]
            que += [v]


print(*D)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
sys.setrecursionlimit(10 ** 9)



INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, q = LI()
G = [[] for _ in range(n)]
for a, b in LIR(n - 1):
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

D = [0] * n
for p, x in LIR(q):
    D[p - 1] += x


que = [0]
visited = [0] * n
visited[0] = 1
while que:
    u = que.pop()
    for v in G[u]:
        if visited[v] == 0:
            visited[v] = 1
            D[v] += D[u]
            que += [v]


print(*D)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
sys.setrecursionlimit(10 ** 9)



INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, q = LI()
G = [[] for _ in range(n)]
for a, b in LIR(n - 1):
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

D = [0] * n
for p, x in LIR(q):
    D[p - 1] += x


que = [0]
par = [-1] * n
par[0] = 0
while que:
    u = que.pop()
    for v in G[u]:
        if par[v] == -1:
            par[v] = u
            D[v] += D[u]
            que += [v]


print(*D)

Submission status: Accepted

Solution code:
# 2019-11-17 10:52:21(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n, q = [int(x) for x in sys.stdin.readline().split()]
    AB = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        AB[a].append(b)
        AB[b].append(a)
    # 無向グラフとして考える

    ans = [0 for _ in range(n+1)]
    for _ in range(q):
        p, x = [int(x) for x in sys.stdin.readline().split()]
        ans[p] += x
    
    stack = [1]
    parent = [0 for _ in range(n+1)]
    while stack:
        x = stack.pop()
        for y in AB[x]:
            if y != parent[x]: # yがxの親でなければ
                parent[y] = x # xがyの親
                stack.append(y)
                ans[y] += ans[x]
 
    
    print(' '.join(map(str, ans[1:])))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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)

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

def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        else:
            ans[u] += ans[v]
            dfs(u, v)

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

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
G = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
C = [0]*(N)
for i in range(Q):
    p,x = map(int,input().split())
    C[p-1] += x
from collections import deque
d=deque()
d.append(0)
t = [False]*(N)
t[0] = True
while d:
    a = d.popleft()
    for b in G[a]:
        if not t[b]:
            t[b] = True
            d.append(b)
            C[b] += C[a]
print(*C)

Submission status: Accepted

Solution code:
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)
counter = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    counter[p] += x
used = [False] * N
stack = [0]
used[0] = True
while stack:
    a = stack.pop()
    for b in g[a]:
        if not used[b]:
            used[b] = True
            counter[b] += counter[a]
            stack.append(b)
print(" ".join(map(str, counter)))

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)]
res=[0 for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)

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


def my_add(v,par):
    for vn in g[v]:
        if vn==par:
            continue
        res[vn]+=res[v]
        my_add(vn,v)

my_add(0,-1)
print(*res)