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
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

def main():
    n, q = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        g[a].append(b); g[b].append(a)
    node = [0]*n
    for i in range(q):
        p, x = map(int, input().split())
        p -= 1
        node[p] += x

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * n

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

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

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

dfs(0)
print(*node)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque

readline = stdin.readline

def main():
    N, Q = map(int, input().split())

    # 木構造を記録（親も子も関係なく繋がっている節を結ぶ）
    tree = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, readline().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    # 素の状態の節のカウントを求める
    cou = [0] * N
    for _ in range(Q):
        p, x = map(int, readline().split())
        cou[p - 1] += x


    # 頂点から順に節を見ていく
    # que(node, parent) node = 現在の節,    parent = 親の節
    # 初期値に頂点（親はなし）を追加
    que = deque([[0, -1]])

    while len(que) > 0:
        node, parent = que.pop()

        # 現在の節から繋がっている節を全て確認
        for child in tree[node]:
            # 繋がっている節が親なら無視
            if child == parent:
                continue
            # 繋がっている節が子なら、現在の節のカウントを増やす
            else:
                cou[child] += cou[node]
                # 子の節を起点に再帰的に処理
                que.appendleft([child, node])
    
    # くぅ～疲れました！これにて完です！
    print(*cou)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

def dfs(chi_idx, parent):
	for child in node_idxes[chi_idx]:
		if child == parent:
			continue
		vals[child] += vals[chi_idx]
		dfs(child, chi_idx)

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
tre = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    tre[a-1].append(b-1)
    tre[b-1].append(a-1)

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

q = deque([0])
judge = [False]*N
while q:
    root = q.pop()
    judge[root] = True
    for i in tre[root]:
        if judge[i]:
            continue
        cnt[i] += cnt[root]
        q.append(i)

print(*cnt)

Submission status: Accepted

Solution code:
N,Q = map(int, input().split())
ki = [[] for i in range(N+1)]
val = [0 for _ in range(N+1)]

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

q = [(1,0)]
while q:
  c,p = q.pop()
  val[c] += val[p]
  for x in ki[c]:
    if x==p:
      continue
    q.append((x,c))
print(' '.join(map(str, val[1:])))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))

Submission status: Accepted

Solution code:
import sys
def solve():
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    tree = [[] for i in range(N)]
    counter = [0] * N
    arrived = [False] * 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)
    
    for i in range(Q):
        p, x = map(int, input().split())
        counter[p-1] += x
    
    arrived[0] = True
    adder(0, counter, tree, arrived)

    print(*counter)

def adder(ind, counter, tree, arrived):
    for i in tree[ind]:
        if arrived[i]:
            continue
        counter[i] += counter[ind]
        arrived[i] = True
        adder(i, counter, tree, arrived)
    if not tree[ind]:
        return

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def solve():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    N, Q = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(N-1):
        A, B = map(int, input().split())
        A, B = A-1, B-1
        adjL[A].append(B)
        adjL[B].append(A)

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

    def dfs(vNow, vPar, x):
        anss[vNow] += x
        ans = anss[vNow]
        for v2 in adjL[vNow]:
            if v2 != vPar:
                dfs(v2, vNow, ans)

    dfs(0, -1, 0)

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

solve()

Submission status: Accepted

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

N, Q = map(int, input().split())
ki = [[[],0] for i in range(N)]
result = [0]*N

def dfs(i, num, parent):
    num_tmp = num+ki[i][1]
    result[i] = num_tmp
    if not ki[i][0]:
        return
    for j in ki[i][0]:
        if j == parent:
            continue
        dfs(j, num_tmp, i)
    return

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

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

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

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]"):
    matrix = [[] for _ in range(N+1)]
    counter = [0]*(N+1)
    for i in range(N-1):
        matrix[a[i]].append(b[i])
        matrix[b[i]].append(a[i])

    for q in range(Q):
        counter[p[q]]+=x[q]

    queue = deque()
    queue.append(1)

    checkflag = [False]*(N+1)
    while queue:
        root = queue.pop()
        checkflag[root]=True
        for node in matrix[root]:
            if checkflag[node] == False:
                queue.append(node)
                counter[node]+=counter[root]

    print(*counter[1:])




        
    return


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:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7




n,q=map(int,input().split())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)
data=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    data[p-1]+=x
visited=[0]*n
visited[0]=1
stack=[0]

while stack:
    node=stack.pop()
    for v in G[node]:
        if not visited[v]:
            visited[v]=1
            data[v]+=data[node]
            stack.append(v)


print(*data)

Submission status: Accepted

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

n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * n

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

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

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

dfs(0)
print(*node)

Submission status: Accepted

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

import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)

# N: ノードの数
# Q: 数値をノードに付与する回数
N, Q = map(int, input().split())

links =  [[] for _ in range(N)]
values = [0] * N

for i in range(N - 1):
    edge1, edge2 = [x - 1 for x in map(int, input().split())]
    links[edge1].append(edge2)
    links[edge2].append(edge1)

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

# 値の計算
stack = deque()
stack.append((0, -1))
while stack:
    node = stack.pop()

    for linked_node in links[node[0]]:
        if linked_node == node[1]:  # link が親ノード向けでなければ
            continue

        values[linked_node] += values[node[0]]
        stack.append((linked_node, node[0]))

print(*values)

Submission status: Accepted

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

from collections import deque

# N: ノードの数
# Q: 数値をノードに付与する回数
N, Q = map(int, input().split())

links =  [[] for _ in range(N)]
values = [0] * N

for i in range(N - 1):
    edge1, edge2 = [x - 1 for x in map(int, input().split())]
    links[edge1].append(edge2)
    links[edge2].append(edge1)

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

# 値の計算
stack = deque()
stack.append((0, -1))
while stack:
    node = stack.pop()

    for linked_node in links[node[0]]:
        if linked_node == node[1]:  # link が親ノード向けでなければ
            continue

        values[linked_node] += values[node[0]]
        stack.append((linked_node, node[0]))

print(*values)

Submission status: Accepted

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

from collections import deque

# N: ノードの数
# Q: 数値をノードに付与する回数
N, Q = list(map(int, input().split()))

links =  [[] for _ in range(N)]
values = [0 for _ in range(N)]

for i in range(N - 1):
    edge1, edge2 = [x - 1 for x in list(map(int, input().split()))]
    links[edge1].append(edge2)
    links[edge2].append(edge1)

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

# 値の計算
stack = deque()
stack.append((0, -1))
while stack:
    node = stack.pop()

    for linked_node in links[node[0]]:
        if linked_node == node[1]:  # link が親ノード向けでなければ
            continue

        values[linked_node] += values[node[0]]
        stack.append((linked_node, node[0]))

print(*values)

Submission status: Accepted

Solution code:
def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

# N: ノードの数
# Q: 数値をノードに付与する回数
N, Q = list(map(int, input().split()))

links =  [[] for _ in range(N)]
values = [0 for _ in range(N)]

for i in range(N - 1):
    edge1, edge2 = [x - 1 for x in list(map(int, input().split()))]
    links[edge1].append(edge2)
    links[edge2].append(edge1)

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

# 値の計算
stack = [(0, -1)]  # [(ノードID, 親ノードID)] のリスト (-1 は番兵)
while stack:
    node = stack.pop()

    for linked_node in links[node[0]]:
        if linked_node == node[1]:  # link が親ノード向けでなければ
            continue

        values[linked_node] += values[node[0]]
        stack.append((linked_node, node[0]))

print(*values)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, q = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(list)
    for i in range(n-1):
        a, b = list(map(int, input().rstrip('\n').split()))
        d[a-1] += [b-1]
        d[b-1] += [a-1]
    ls = [0] * n
    for i in range(q):
        p, x = list(map(int, input().rstrip('\n').split()))
        ls[p-1] += x
    ql = collections.deque([0])
    fq = collections.defaultdict(int)
    fq[0]
    while True:
        if len(ql) != 0:
            p = ql.popleft()
            for v in d[p]:
                if v not in fq:
                    ls[v] += ls[p]
                    ql.appendleft(v)
                    fq[p]
        else:
            print(*ls)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
cnt = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x

flag = [1]*N
q = [0]
while q:
    temp = q.pop()
    flag[temp] = 0
    for i in L[temp]:
        if flag[i]:
            q.append(i)
            cnt[i] += cnt[temp]
            
print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque

N,Q=map(int,input().split())
to=[[] for _ in range(N)]
count=[0]*N
for _ in range(N-1):
    a,b=map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)
for _ in range(Q):
    p,x=map(int, input().split())
    count[p-1]+=x
q = deque()
q.append(0)
p=[True]*N
while q:
    i = q.pop()
    if p[i]:
        p[i]=False
        for j in to[i]:
            if p[j]:
                count[j]+=count[i]
                q.append(j)
print(*count)

Submission status: Accepted

Solution code:
from collections import deque

if __name__ == '__main__':
    N, Q = map(int, input().split())
    count = [0] * (N + 1)
    tree = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)

    for _ in range(Q):
        idx, val = map(int, input().split())
        count[idx] += val

    q = deque()
    q.append(1)

    is_valid = [1] * (N + 1)
    while q:
        idx = q.pop()
        is_valid[idx] = 0
        for t in tree[idx]:
            if is_valid[t] == 0: continue
            count[t] += count[idx]
            q.append(t)
    print(*count[1:])

Submission status: Accepted

Solution code:
from collections import deque
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
    d = deque()
    d.append((0,-1))
    
    while len(d) != 0:
        i,p = d.popleft()
        for j in links[i]:
            if j==p:
                continue
            values[j] += values[i]
            d.append((j,i))
    print(*values)
    
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10 ** 7)

# input & solve
input = sys.stdin.readline
N, Q = map(int, input().split())

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

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

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

dfs(0)

# output
print(*ans)

Submission status: Accepted

Solution code:
import collections

N,Q=map(int,input().split())
M=[[] for i in range(N+1)]
P=[0 for i in range(N+1)]
for i in range(N-1):
  a,b=map(int,input().split())
  M[a].append(b)
  M[b].append(a)
#print("M:",M)

S=[0 for i in range(N+1)]
for i in range(Q):
  p,x=map(int,input().split())
  S[p]+=x
#print(S)
  
d=collections.deque([1])

while len(d):
  dd=d.popleft()
  if P[dd]==0:
    P[dd]=1
    for i in M[dd]:
      if P[i]==0:
        S[i]+=S[dd]
      d.append(i)
  #print(d,S)
print(*S[1:])

Submission status: Accepted

Solution code:
from collections import deque
N,Q = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
C = [0 for _ in range(N+1)]
for _ in range(Q):
    p,x = map(int,input().split())
    C[p] += x
heap = deque([1])
hist = [0 for _ in range(N+1)]
while heap:
    cur = heap.popleft()
    hist[cur] = 1
    for x in G[cur]:
        if hist[x]==0:
            C[x] += C[cur]
            heap.append(x)
C.pop(0)
print(*C)

Submission status: Accepted

Solution code:
N, Q = [int(x) for x in input().split()]
to = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = [int(x)-1 for x in input().split()]
    to[b].append(a)
    to[a].append(b)
ans = [0] * N
for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    p -= 1
    ans[p] += x

from collections import deque
q = deque()
q.append(0)
visited = [0] * N

while(q):
    v = q.pop()
    visited[v] = 1    
    for u in to[v]:
        if visited[u] == 1: continue
        ans[u] += ans[v]
        q.append(u)
print(' '.join([str(i) for i in ans]))

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
V = {v: 0 for v in range(1, N+1)}
E = {v: [] for v in V.keys()}
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
added = {v: 0 for v in V.keys()}
for _ in range(Q):
    p, x = map(int, input().split())
    added[p] += x
stack = [(1, added[1])]
visited = {v: False for v in V.keys()}
while stack:
    v, value = stack.pop()
    visited[v] = True
    V[v] += value
    for u in E[v]:
        if not visited[u]:
            stack.append((u, value + added[u]))
print(*[val for val in V.values()])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
import sys
def input():
    return sys.stdin.readline()[:-1]
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
#print(graph)
for _ in range(Q):
    a , b = map(int,input().split())
    a = a - 1
    point[a] += b

# dfsを用いて累積和を計算する
# 初期状態だと前の値がないためデフォルト引数に-1を代入
def dfs(now , prev = -1):
    for next in graph[now]:
        # 次のノードが前に参照した値の時はcontinue
        if next == prev:
            continue

        # 現在の値を次のポイントに加算することで累積和をとる
        point[next] += point[now]

        # 次のノードと現在のノードを引数にdfsを継続する
        dfs(next , now)

dfs(0)
print(*point)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
k=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  k[a-1].append(b-1)
  k[b-1].append(a-1)
s=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  s[p-1]+=x
from collections import deque
d=deque()
d.append(0)
v=[False]*n
v[0]=True
while d:
  g=d.popleft()
  for i in k[g]:
    if v[i]:
      continue
    d.append(i)
    v[i]=True
    s[i]+=s[g]
print(*s)

Submission status: Accepted

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

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

score = [0 for _ in range(N)]
for p, x in px:
    p -= 1
    score[p] += x

res = [0 for _ in range(N)]
res[0] = score[0]
visit = [0 for _ in range(N)]
stack = [0]
while stack:
    v = stack.pop()
    visit[v] = 1
    for to in tree[v]:
        if visit[to]:
            continue
        stack.append(to)
        res[to] = res[v] + score[to]

print(*res)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
input = sys.stdin.readline

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

tree = [[0] * 1 for i in range(N)]


tree_list = [0] * N
end = [0] * N

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

for index in range(Q):
    a, b = map(int, input().split())
    a -= 1
    tree_list[a] += b


def iter(node):
    end[node] = -1
    child = tree[node]
    for c in child:
        if end[c] == 0:
            tree_list[c] += tree_list[node]
            iter(c)


iter(0)

print(*tree_list)

Submission status: Accepted

Solution code:
N, Q = [int(x) for x in 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)]

neighbor = [[] for x in range(N)]
ans = [0] * N
summed = [False] * N
for i in range(N - 1):
    neighbor[AB[i][0] - 1].append(AB[i][1])
    neighbor[AB[i][1] - 1].append(AB[i][0])
for i in range(Q):
    ans[PX[i][0] - 1] += PX[i][1]

from collections import deque
deque=deque([0])
summed[0] = True

while len(deque) != 0:
    tmp = deque.popleft()
    for i in neighbor[tmp]:
        if summed[i - 1]:
            continue
        deque.append(i - 1)
        summed[i - 1] = True
        ans[i - 1] += ans[tmp]
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
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)
    # print(a, b)

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

# print(nodes)
result = [0 for _ in range(n + 1)]

# que = [(1, nodes[1])]
que = deque([(1, nodes[1])])

visited = [False] * (n + 1)
while que:
    i, cost = que.popleft()
    if visited[i]:
        continue
    result[i] = cost
    visited[i] = True
    for sub in graph[i]:
        que.append((sub, cost + nodes[sub]))
print(*result[1:])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
graph=[[]for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  graph[a].append(b)
  graph[b].append(a)
cost=[0]*n
visited=[False]*n
for i in range (m):
  p,x=map(int,input().split())
  p=p-1
  cost[p]=cost[p]+x
from collections import deque
quest=deque([0])
visited[0]=True
while len(quest)!=0:
  a=quest.popleft()
  for i in graph[a]:
    if visited[i]==True:
      continue
    quest.append(i)
    visited[i]=True
    cost[i]=cost[i]+cost[a]
print(*cost)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
graph=[[] for i in range(n)]
visited=[False]*n
visited[0]=True
from collections import deque
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)

s=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    s[p-1]+=x
quest=deque([0])#はじめどうせ見るし入れとく
while len(quest)!=0:
    see=quest.popleft()
    for i in graph[see]:
        if visited[i]==True:
            continue
        quest.append(i)
        visited[i]=True
        s[i]+=s[see]
#for i in range(n):
    #print(s[i],end=" ")
print(*s)

Submission status: Accepted

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

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

wait = [1]
parent = [0] * (N + 1)
while wait:
    temp = wait.pop()

    # 頂点tempについて
    for i in graph[temp]:
        if i != parent[temp]:
            parent[i] = temp
            wait.append(i)
            cnt[i] += cnt[temp]


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

Submission status: Accepted

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

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)

ans = [0 for i in range(N)]

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

def dfs(n, r):
    for i in T[n]:
        if i != r:
            ans[i] += ans[n]
            dfs(i, n)

dfs(0, -1)

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
edge=[[]for i in range(n+1)]
li=[0]*(n+1)
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    li[p]+=x

q=deque()
q=[1]
se=set()
while q:
    idx=q.pop()
    se.add(idx)
    for x in edge[idx]:
        if x not in se:
            se.add(x)
            li[x]+=li[idx]
            q.append(x)
            
print(*li[1:])

Submission status: Accepted

Solution code:
from collections import deque

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

# ノードaがノードbの親とは限らない点に注意
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[b-1].append(a-1)
    tree[a-1].append(b-1)

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

# BFSで親ノードの値を子ノードに足していく
# ノードのインデックスが0以外不規則であるかもしれないので、隣接ノードのうち親ノードでないノードを子ノードと考える
point = deque()
for child in tree[0]:
    point.append([0,child])

while point:
    parent, current = point.popleft()
    counter[current] += counter[parent]
    for child in [x for x in tree[current] if x != parent]:
        point.append([current, child])

print(*counter)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(N, d, ans):
    Q = deque([0])
    visited = [False] * N
    visited[0] = True
    while Q:
        q = Q.popleft()

        for p in d[q]:
            if visited[p]:
                continue
            visited[p] = True
            Q.append(p)
            ans[p] += ans[q]

    return ans


def main():
    N, Q = map(int, input().split())
    d = [[] for _ in range(N)]

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

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

    print(*bfs(N, d, ans))
    

main()

Submission status: Accepted

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

n,q = map(int,input().split())
t = [[] for _ in range(n+1)]
for _ in range(n-1):
  a,b = map(int,input().split())
  t[a].append(b)
  t[b].append(a)
cnt = [0]*(n+1)
for _ in range(q):
  p,x = map(int,input().split())
  cnt[p] += x
def csum(now,bef):
  for i in t[now]:
    if i != bef:
      cnt[i] += cnt[now]
      csum(i,now)
csum(1,0)
print(*cnt[1:])

Submission status: Accepted

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


def main():
    N, Q = [int(x) for x in input().strip().split()]
    data = []
    for _ in range(N-1):
        data.append([int(x) for x in input().strip().split()])

    operate = [0] * (N+1)
    for _ in range(Q):
        node, point = [int(x) for x in input().strip().split()]
        operate[node] += point

    tree = [[] for _ in range(N+1)]
    for d in data:
        tree[d[0]].append(d[1])
        tree[d[1]].append(d[0])

    stack = deque()
    stack.append((0,1))  # スタートノード
    while len(stack) > 0:
        parent_node, proc_node = stack.popleft()
        operate[proc_node] += operate[parent_node]
        for child_node in tree[proc_node]:
            if child_node == parent_node:
                continue
            stack.append((proc_node, child_node))

    print(*operate[1:])


if __name__ == "__main__":
    main()