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.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

branch = [[] for _ in range(N)] # [[]]*N だと参照渡しになってしまう
X = [0,]*N
root = [False]*N
t = 0

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

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


def search(p):
    global t
    root[p-1] = True
    for q in branch[p-1]:
        if root[q-1]:
            continue
        X[q - 1] += X[p - 1]        # 各頂点に到達した際にどのような計算をすればいいかを意識
        search(q)



search(1)
print(*X)

Submission status: Accepted

Solution code:
# ＤＦＳ, グラフ, 全探索, 親の情報を自身に加算
 # ※ 要削除

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

pic = [[] for _ in range(n+1)] # ダミーのノード '0' を含む
for _ in range(n-1): # 絵の取り込み
    x, y = map(int, input().split())
    pic[x].append(y)
    pic[y].append(x)
    
cnts = [0] * (n+1) # カウンター初期化
for _ in range(q): # 初期情報取り込み
    x, y = map(int, input().split())
    cnts[x] += y

visited = [0] * (n+1) # 訪問の記録、初期化
visited[0], visited[1] = 1, 1 # 開始時情報記録

stack = []
stack.append(1)

#print(n, q) # ※
#print(pic) # ※
#print(cnts)
#print(visited) # ※

while stack:
    tmp = stack.pop() # 探索候補を pop して...
    for i in pic[tmp]: # 次の探索候補を探索
        if visited[i] != 0: # 未訪問かどうかを確認...
            continue
        else: # 未訪問の場合...
            visited[i] = 1 # 現在地の訪問を記録
            cnts[i] += cnts[tmp] # 親の 'cnt' を自身の 'cnt' に加える
            stack.append(i) # 現在地を探索候補に積む

print(*cnts[1:])

Submission status: Accepted

Solution code:
# ＢＦＳ, グラフ, 全探索, 親の情報を自身に加算
 # ※ 要削除

from collections import deque

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

pic = [[] for _ in range(n+1)] # ダミーのノード '0' を含む
for _ in range(n-1): # 絵の取り込み
    x, y = map(int, input().split())
    pic[x].append(y)
    pic[y].append(x)
    
cnts = [0] * (n+1) # カウンター初期化
for _ in range(q): # 初期情報取り込み
    x, y = map(int, input().split())
    cnts[x] += y

visited = [0] * (n+1) # 訪問の記録、初期化
visited[0], visited[1] = 1, 1 # 開始時情報取り込み

queue = deque([])
queue.append(1)

#print(n, q) # ※
#print(pic) # ※
#print(cnts)
#print(visited) # ※

while queue:
    tmp = queue.popleft() # 探索候補を popleft して...
    for i in pic[tmp]: # 次の探索候補を探索
        if visited[i] != 0: # 未訪問かどうかを確認...
            continue
        else: # 未訪問の場合...
            visited[i] = 1 # 現在地の訪問を記録
            cnts[i] += cnts[tmp] # 親の 'cnt' を自身の 'cnt' に加える
            queue.append(i) # 現在地を探索候補に積む

print(*cnts[1:])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

branch = [[] for _ in range(N)] # [[]]*N だと参照渡しになってしまう
X = [0,]*N
root = [None]*N
t = 0

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

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


def search(p):
    global t
    root[p-1] = t
    t += 1
    for q in branch[p-1]:
        if root[q-1] != None:
            continue
        X[q - 1] += X[p - 1]
        search(q)
    t -= 1



search(1)
print(*X)

Submission status: Accepted

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

n, q = [int(i) for i in readline().split()]
to = [[] for _ in range(n)]
ans = [0]*n

def dfs(v, p=-1): # v:これから見るnode、p:親node
    global ans
    for i in range(len(to[v])):
        u = to[v][i]
        if u == p: continue # 親nodeは確認済みなので見ない
        ans[u] += ans[v]
        dfs(u, v)

for i in range(n-1):
    a, b = [int(i) for i in readline().split()]
    a -= 1; b -= 1
    to[a].append(b)
    to[b].append(a)

for i in range(q):
    v, x = [int(i) for i in readline().split()]
    v -= 1
    ans[v] += x

dfs(0)

print(*ans)

Submission status: Accepted

Solution code:
# ＤＦＳ, グラフ, 全探索, 親の情報を自身に加算
 # ※ 要削除

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

pic = [[] for _ in range(n+1)] # ダミーのノード '0' を含む
for _ in range(n-1): # 絵の取り込み
    x, y = map(int, input().split())
    pic[x].append(y)
    pic[y].append(x)
    
cnts = [0] * (n+1)
for _ in range(q):
    x, y = map(int, input().split())
    cnts[x] += y

visited = [0] * (n+1) # 訪問の記録、初期化
visited[0], visited[1] = 1, 1

stack = []
stack.append(1)

#print(n, q) # ※
#print(pic) # ※
#print(cnts)
#print(visited) # ※

while stack:
    tmp = stack.pop() # 探索候補を pop して...
    for i in pic[tmp]: # 次の探索候補を探索
        if visited[i] != 0: # 未訪問かどうかを確認...
            continue
        else: # 未訪問の場合...
            visited[i] = 1 # 現在地の訪問を記録
            cnts[i] += cnts[tmp] # 親の 'cnt' を自身の 'cnt' に加える
            stack.append(i) # 現在地を探索候補に積む

print(*cnts[1:])

Submission status: Accepted

Solution code:
# ＤＦＳ, グリッド で スタート から ゴール までの経路をを探索
 # ※ 要削除

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

pic = [[] for _ in range(n+1)]
for _ in range(n-1): # 絵の取り込み
    x, y = map(int, input().split())
    pic[x].append(y)
    pic[y].append(x)
    
cnts = [0] * (n+1)
for _ in range(q):
    x, y = map(int, input().split())
    cnts[x] += y

visited = [0] * (n+1) # 訪問の記録、初期化
visited[0], visited[1] = 1, 1

stack = []
stack.append(1)

#print(n, q) # ※
#print(pic) # ※
#print(cnts)
#print(visited) # ※

while stack:
    tmp = stack.pop() # 探索候補を pop して...
    for i in pic[tmp]: # 次の探索候補を探索
        if visited[i] != 0: # 未訪問かどうかを確認...
            continue
        else: # 未訪問の場合...
            visited[i] = 1 # 現在地の訪問を記録
            cnts[i] += cnts[tmp] # 親の 'cnt' を自身の 'cnt' に加える
            stack.append(i) # 現在地を探索候補に積む

print(*cnts[1:])

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    from collections import deque
    input = stdin.readline
    n, q = map(int, input().split())
    a = [[] for _ in range(n)]
    for i in range(n - 1):
        x, y = map(int, input().split())
        a[x - 1].append(y - 1)
        a[y - 1].append(x - 1)
    p = [0] * n
    for i in range(q):
        x, y = map(int, input().split())
        p[x - 1] += y
    c = [0] * n
    c[0] = 1
    que = deque([])
    que.append(0)
    while len(que) > 0:
        e = que.popleft()
        for i in a[e]:
            if c[i] > 0:
                continue
            c[i] = 1
            p[i] += p[e]
            que.append(i)
    for i in range(n):
        print(p[i])
main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n, q = map(int, input().split())
    a = [[] for _ in range(n)]
    for i in range(n - 1):
        x, y = map(int, input().split())
        a[x - 1].append(y - 1)
        a[y - 1].append(x - 1)
    p = [0] * n
    for i in range(q):
        x, y = map(int, input().split())
        p[x - 1] += y
    c = [0] * n
    c[0] = 1
    que = deque([])
    que.append(0)
    while len(que) > 0:
        e = que.popleft()
        for i in a[e]:
            if c[i] > 0:
                continue
            c[i] = 1
            p[i] += p[e]
            que.append(i)
    for i in range(n):
        print(p[i])
main()

Submission status: Accepted

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


def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):

    edges = [[] for _ in range(N)]
    for ai, bi in zip(a,b):
        edges[ai-1].append(bi)
        edges[bi-1].append(ai)
    pls = [0]*N
    for pi, xi in zip(p, x):
        pls[pi-1]+=xi
    
    ans = [0]*N
    ans[0] = pls[0]
    q = deque([1])
    while q:
        temp = q.pop()
        for t in edges[temp-1]:
            edges[t-1].remove(temp)
            ans[t-1] = pls[t-1] + ans[temp-1]
        q.extend(edges[temp-1])

    print(*ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    x = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, Q = map(int, input().split())
Tree = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    Tree[a-1].append(b-1)
    Tree[b-1].append(a-1)
    
count = [0 for i in range(N)]
for i in range(Q):
    p, x = map(int, input().split())
    count[p-1] += x

d = deque()
d.append(0)
visited = set()
while d:
    now = d.pop()
    visited.add(now)
    for v in Tree[now]:
        if v not in visited:
            d.append(v)
            count[v] += count[now]
            
print(*count)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
v = [[0,0] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
for i in range(q):
    p,x = map(int,input().split())
    v[p][1] += x
q = [1]
while q:
    now = q.pop()
    v[now][0] = 1
    for i in v[now][2:]:
        if v[i][0] == 0:
            v[i][1] += v[now][1]
            q.append(i)
s = []
for i in v:
    s.append(i[1])
print(*s[1:])

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 138 D - Ki　
import sys
sys.setrecursionlimit(10 ** 9)

N, Q = map(int, sys.stdin.readline().strip().split())

M = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, sys.stdin.readline().strip().split())
    M[a - 1].append(b - 1)
    M[b - 1].append(a - 1)

X = [0] * N
for _ in range(Q):
    p, x = map(int, sys.stdin.readline().strip().split())
    X[p - 1] += x


ans = [0] * N


def dfs(u, parent=None):

    ans[u] = ans[parent] + X[u]

    for v in M[u]:
        if v != parent:
            dfs(v, u)


dfs(0, 0)
print(' '.join([str(i) for i in ans]))

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 138 D - Ki　
import sys
sys.setrecursionlimit(10 ** 9)

N, Q = map(int, sys.stdin.readline().strip().split())

M = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, sys.stdin.readline().strip().split())
    M[a - 1].append(b - 1)
    M[b - 1].append(a - 1)

X = [0] * N
for _ in range(Q):
    p, x = map(int, sys.stdin.readline().strip().split())
    X[p - 1] += x


fp = [True] * N  # 探索可能な点か記録する。
ans = [0] * N


def dfs(u, x):
    ans[u] += x
    fp[u] = False
    for v in M[u]:
        if fp[v]:
            dfs(v, x + X[v])


dfs(0, X[0])
print(' '.join([str(i) for i in ans]))

Submission status: Accepted

Solution code:
import sys


def count(i, r=-1):
    for e in es[i]:
        if e != r:
            counter[e] += counter[i] + rc[e]
            count(e, i)


if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    es = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        es[a-1].append(b-1)
        es[b-1].append(a-1)
    counter = [0]*N
    rc = [0]*N
    for _ in range(Q):
        p, x = map(int, input().split())
        rc[p-1] += x
    counter[0] = rc[0]
    count(0)
    print(*counter)

Submission status: Accepted

Solution code:
from collections import deque
num_ver, times_plus = map(int,input().split())
done_ls = [0] * num_ver
graph_ls = [[] for _ in range(num_ver)]
for i in range(num_ver-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    graph_ls[a].append(b)
    graph_ls[b].append(a)

point_ls = [0] * num_ver
for i in range(times_plus):
    ver, point = map(int,input().split())
    ver -= 1
    point_ls[ver] += point

queue = deque()
queue.append([0,0])
ans_ls = [0] * num_ver
visited_ls = [0] * num_ver
while queue:
    ver, point_before = queue.pop()
    point_after = point_before + point_ls[ver]
    ans_ls[ver] = point_after
    visited_ls[ver] = 1
    for nex in graph_ls[ver]:
        if visited_ls[nex] != 1:
            queue.append([nex, point_after])
for ans in ans_ls:
    print(ans)

Submission status: Accepted

Solution code:
import sys


def count(i, r, value):
    value += rc[i]
    counter[i] = value
    for e in es[i]:
        if e != r:
            count(e, i, value)


if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    es = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        es[a-1].append(b-1)
        es[b-1].append(a-1)
    counter = [0]*N
    rc = [0]*N
    for _ in range(Q):
        p, x = map(int, input().split())
        rc[p-1] += x
    count(0, -1, 0)
    print(*counter)

Submission status: Accepted

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

#print(graph, counter)
# 深さ優先探索
def dfs(v):
    #global time
    #time += 1
    visited[v] = 1
    stack = [v]
    #print(stack, v)
    #arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if visited[w] == 0:
              visited[w] = 1
              counter[w] += counter[v]
              stack.append(w) 
        else:
            stack.pop()          
    return 0

visited = [0] * N
# 孤立している頂点対策
#for i in range(N):
 #   if visited[i] == 0:
  #     dfs(i)
dfs(0)

#print(counter)

print(*counter)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    N, Q, *ABPX = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(ABPX[0 : 2 * N - 2 : 2], ABPX[1 : 2 * N - 2 : 2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)
    X = [0] * N
    for p, x in zip(ABPX[2 * N - 2 :: 2], ABPX[2 * N - 1 :: 2]):
        X[p - 1] += x

    C = [0] * N
    C[0] = X[0]
    seen = [False] * N
    stack = deque([0])

    while stack:
        v = stack.pop()
        seen[v] = True
        for nv in G[v]:
            if not seen[nv]:
                stack.append(nv)
                C[nv] = C[v] + X[nv]

    print(*C)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    N, Q, *ABPX = map(int, read().split())

    A = ABPX[0 : 2 * N - 2 : 2]
    B = ABPX[1 : 2 * N - 2 : 2]
    P = ABPX[2 * N - 2 :: 2]
    X = ABPX[2 * N - 1 :: 2]

    G = [[] for _ in range(N)]
    for a, b in zip(A, B):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    Y = [0] * N
    for p, x in zip(P, X):
        Y[p - 1] += x

    C = [0] * N
    C[0] = Y[0]
    seen = [False] * N
    stack = deque([0])

    while stack:
        v = stack.pop()
        seen[v] = True
        for nv in G[v]:
            if not seen[nv]:
                stack.append(nv)
                C[nv] = C[v] + Y[nv]

    print(*C)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def main():
    N, Q = map(int, readline().split())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, readline().split())
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)
    X = [0] * N
    for i in range(Q):
        p, x = map(int, readline().split())
        X[p - 1] += x

    C = [0] * N
    C[0] = X[0]
    seen = [False] * N
    stack = deque([0])
    
    while stack:
        v = stack.pop()
        seen[v] = True
        for nv in G[v]:
            if not seen[nv]:
                stack.append(nv)
                C[nv] = C[v] + X[nv]

    print(*C)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def main():
    N, Q = map(int, readline().split())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, readline().split())
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)
    X = [0] * N
    for i in range(Q):
        p, x = map(int, readline().split())
        X[p - 1] += x

    C = [0] * N

    def dfs(v, p):
        C[v] = C[p] + X[v]
        for nv in G[v]:
            if nv != p:
                dfs(nv, v)

    dfs(0, -1)

    print(*C)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def main():
    N, Q = map(int, readline().split())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, readline().split())
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)
    X = [0] * N
    for i in range(Q):
        p, x = map(int, readline().split())
        X[p - 1] += x

    C = [0] * N

    def dfs(v, p, count):
        C[v] = count + X[v]
        for nv in G[v]:
            if nv != p:
                dfs(nv, v, C[v])

    dfs(0, -1, 0)

    print(*C)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,Q = IL()
graph = [[] for i in range(N)]

for _ in range(N-1):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
  
count = [0 for i in range(N)]
flag =  [0 for i in range(N)]
newQ = [0 for i in range(N)]

Q = ILL(Q)

for x,n in Q:
  newQ[x-1] += n
  
q = deque([0])
count[0] = newQ[0]
flag[0] = 1
while q:
  x = q.pop()
  for y in graph[x]:
    if flag[y] == 0:
      count[y] = count[x] + newQ[y]
      flag[y] = 1
      q.append(y)

print(*count)

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:
# 20/5/28
import sys
sys.setrecursionlimit(3 * 10 ** 5)
input = sys.stdin.readline

def bfs(root):
    global AL, cnt, visited
    visited[root] = True
    for v in AL[root]:
        if not visited[v]:
            cnt[v] += cnt[root]
            bfs(v)

N, Q = [int(x) for x in input().split()]
AL = [[] for _ in range(N + 1)]
for i in range(1, N):
    a, b = [int(x) for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

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

visited = [False] * (N + 1)
bfs(1)
s = " ".join(map(str, cnt[1:]))
print(s)

Submission status: Accepted

Solution code:
# 20/5/28
import sys
sys.setrecursionlimit(3 * 10 ** 5)
input = sys.stdin.readline

def bfs(root, parent):
    global AL, cnt
    for v in AL[root]:
        if v != parent:
            cnt[v] += cnt[root]
            bfs(v, root)

N, Q = [int(x) for x in input().split()]
AL = [[] for _ in range(N + 1)]
for i in range(1, N):
    a, b = [int(x) for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

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

bfs(1, -1)
print(*cnt[1:])

Submission status: Accepted

Solution code:
# 20/5/28
from collections import deque

N, Q = [int(x) for x in input().split()]
AL = [[] for _ in range(N + 1)]
for i in range(1, N):
    a, b = [int(x) for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

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

visited = [False] * (N + 1)
stk = deque([1])
while stk:
    root = stk.pop()
    visited[root] = True
    for v in AL[root]:
        if not visited[v]:
            cnt[v] += cnt[root]
            stk.append(v)

print(*cnt[1:])

Submission status: Accepted

Solution code:
# 20/5/28
from collections import deque

N, Q = [int(x) for x in input().split()]
AL = [[] for _ in range(N + 1)]
for i in range(1, N):
    a, b = [int(x) for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

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

visited = [False] * (N + 1)
stk = deque([1])
while stk:
    root = stk.pop()
    visited[root] = True
    for v in AL[root]:
        if not visited[v]:
            cnt[v] += cnt[root]
            stk.append(v)

s = " ".join(map(str, cnt[1:]))
print(s)

Submission status: Accepted

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

n, q = map(int, input().split())
a, b = [0] * (-1 + n), [0] * (n - 1)
path = [[] for _ in range(n)]
for i in range(n - 1):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    path[a[i]].append(b[i])
    path[b[i]].append(a[i])
add = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    add[p] += x
q = deque()
ans = [0] * n
# 根 0 から見ていく
q.append(0)
visit = [0] * n
visit[0] = 1
ans[0] = add[0]
while q:
    pos = q.popleft()
    for v in path[pos]:
        if visit[v] == 0:
            ans[v] = ans[pos] + add[v]
            q.append(v)
            visit[v] = 1
print(*ans)

Submission status: Accepted

Solution code:
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)
cnt=[0]*(n+1)
for i in range(q):
  p,x=map(int,input().split())
  cnt[p]+=x
flag=[1]*(n+1)
stack=[1]
while stack:
  v=stack.pop()
  flag[v]=0
  for k in graph[v]:
    if flag[k]:
      cnt[k]+=cnt[v]
      stack.append(k)
print(*cnt[1:])

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
def BFS(dq):
    while dq:
        e = dq.popleft()
        visited[e] = True
        for i in G[e]:
            if not visited[i]:
                P[i] += P[e]
                dq.append(i)

# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,Q = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N-1)]
PX = [tuple(map(int,input().split())) for _ in range(Q)]

G = [[] for _ in range(N)]
for a,b in AB:
    G[a-1].append(b-1)
    G[b-1].append(a-1)

# 各頂点が "カウンター増加の根" として直接増加する数
P = [0]*N
for p,x in PX:
    P[p-1] += x

# 訪問済みフラグ
visited = [False]*N
visited[0] = True

Ans = [0]*N
from collections import deque
BFS(deque([0]))

print(*P)

Submission status: Accepted

Solution code:
from collections import deque

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

edge = [[] for i in range(N)]
ans = [0] * N
query = [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 q in range(Q):
    p, x = map(int, input().split())
    query[p-1] += x

is_visited = [False] * N
stack = deque([(0,0)])

while len(stack) != 0:
    cur, q = stack.pop()
    is_visited[cur] = True

    q = q + query[cur]
    ans[cur] += q

    for next in edge[cur]:
        if is_visited[next]:
            continue
        stack.append((next, q))

print(*ans)

Submission status: Accepted

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

edge = [[] for i in range(N)]
ans = [0] * N
query = [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 q in range(Q):
    p, x = map(int, input().split())
    query[p-1] += x

is_visited = [False] * N
stack = [(0,0)]

while len(stack) != 0:
    cur, q = stack.pop()
    is_visited[cur] = True

    q = q + query[cur]
    ans[cur] += q

    for next in edge[cur]:
        if is_visited[next]:
            continue
        stack.append((next, q))

print(*ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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

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

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

N,Q,*abpx=map(int,sys.stdin.read().split())

graph=[[] for _ in range(N)]
for a,b in zip(*[iter(abpx[:2*(N-1)])]*2):
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)

f=[0]*N
for p,x in zip(*[iter(abpx[2*(N-1):])]*2):
    p-=1
    f[p]+=x

ans=[0 for _ in range(N)]
visited=[False]*N
def c(i,p):
    if visited[i]:
        return 
    visited[i]=True
    w=f[i]+p
    ans[i]=w
    ch=graph[i]
    for x in ch:
        c(x,w)

c(0,0)
print(*ans)