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

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

st = [0]
visit = [False for i in range(n)]
while not len(st) == 0:
  now = st.pop()
  visit[now] = True
  for e in graph[now]:
    if visit[e]:
      continue
    weight[e] += weight[now]
    st.append(e)
    
print(' '.join(map(str,weight)))

Submission status: Accepted

Solution code:
# D - Ki TLE
import sys
sys.setrecursionlimit(10**7)
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)
    
lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))

cnt = [0]*N
for p,x in lst:
    cnt[p] += x 
    
seen = [False]*N
def dfs(v):
    seen[v] = True# v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        cnt[next_v] += cnt[v] 
        dfs(next_v)
dfs(0)
print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
G=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
count=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  count[p-1]+=x
stack=deque([0])
ans=[0]*n
ans[0]=count[0]
flag=[False]*n
while stack:
  v=stack.pop()
  flag[v]=True
  for nv in G[v]:
    if not flag[nv]:
      stack.append(nv)
      ans[nv]=ans[v]+count[nv]
print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import setrecursionlimit # 再帰エラー対策
setrecursionlimit(10 ** 7)

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

node = [[] for _ in range(n+1)]
counter = [0 for _ in range(n+1)]
visited = [0 for _ in range(n+1)]
point_dic = defaultdict(int)

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

# 各ノードの加算値を記録
for _ in range(q):
    p,x = map(int,input().split())
    point_dic[p] += x

# 現在のノード(now)とそれまでに加算された値(before_point)
def dfs(now,before_point):
    if visited[now]:
        return
    
    # 現在のノードの加算値を足す
    if point_dic[now]:
        point = point_dic[now]+before_point
    else:
        point = before_point
    
    # 訪問済みにする
    visited[now] = 1
    counter[now] += point

    for i in node[now]:
        if visited[i]:
            continue

        dfs(i,point) # 再帰して子ノードに引き継ぐ

dfs(1,0)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

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

node = [[] for _ in range(n+1)]
counter = [0 for _ in range(n+1)]
visited = [0 for _ in range(n+1)]
point_dic = defaultdict(int)

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

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

def dfs(now,before):
    global counter
    global visited

    if visited[now]:
        return
    
    if point_dic[now]:
        point = point_dic[now]+before
    else:
        point = before
    
    visited[now] = 1
    counter[now] += point

    for i in node[now]:
        if visited[i]:
            continue

        dfs(i,point)

dfs(1,0)

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

Submission status: Accepted

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

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

tree = [[] for _ in range(n)]

app = set([0])

import queue
next = queue.Queue()
next.put(0)
# print(tree_candidate)
while not next.empty():
    i = next.get()
    for j in tree_candidate[i]:
        if not j in app:
            tree[i].append(j)
            app.add(j)
            next.put(j)

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

next = queue.Queue()
next.put(0)

while not next.empty():
    i = next.get()
    for j in tree[i]:
        cnts[j] += cnts[i]
        next.put(j)

for i in cnts:
    print(i, end=' ')

Submission status: Accepted

Solution code:
def abc138d_ki():
    import heapq
    n, q = map(int, input().split())
    cnt = [0] * n
    graph = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)
    for _ in range(q):
        p, x = map(int, input().split())
        cnt[p - 1] += x
    qu = [(0, 0)]
    heapq.heapify(qu)
    check = [False] * n
    while len(qu) != 0:
        h, no = heapq.heappop(qu)
        check[no] = True
        for nxt in graph[no]:
            if not check[nxt]:
                cnt[nxt] += cnt[no]
                heapq.heappush(qu, (h + 1, nxt))
    for c in cnt:
        print(c, end=' ')


abc138d_ki()

Submission status: Accepted

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

stack=deque([[0,0,-1]]) # 現在地、その位置で引き継いできたcount、前の位置

while stack:
    num,count,preb = stack.pop()
    cnt[num]+=count
    for i in tree[num]:
        if i == preb:
            continue
        stack.append([i,cnt[num],num])

print(*cnt)

Submission status: Accepted

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

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)]

t = dict()
for i in range(1, n+1):
    t[i] = set()
for a, b in ab:
    t[a].add(b)
    t[b].add(a)

cnt = [0] * n
s = set()
for p, x in px:
    cnt[p-1] += x

def solve(p):
    s.add(p)
    for c in t[p]:
        if c not in s:
            cnt[c-1] += cnt[p-1]
            solve(c)
solve(1)
print(*cnt, sep=' ')

Submission status: Accepted

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

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)]

t = dict()
for i in range(1, n+1):
    t[i] = []
for a, b in ab:
    t[a].append(b)
    t[b].append(a)

cnt = [0] * n
s = set()
for p, x in px:
    cnt[p-1] += x

def solve(p):
    s.add(p)
    for c in t[p]:
        if c not in s:
            cnt[c-1] += cnt[p-1]
            solve(c)
solve(1)
print(*cnt, sep=' ')

Submission status: Accepted

Solution code:
from collections import deque
N, Q = list(map(int, input().split()))
S = [set() for _ in range(N)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    S[a].add(b)
    S[b].add(a)
node = [0]*N
for _ in range(Q):
    t, v = list(map(int, input().split()))
    t -= 1
    node[t] += v

seen = [False]*N
stk = deque([(0, 0)])
while stk:
    t, v = stk.pop()
    seen[t] = True
    node[t] += v
    s = S[t]
    for k in s:
        if not seen[k]:
            stk.appendleft((k, node[t]))
print(*node)

Submission status: Accepted

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

setrecursionlimit(10 ** 8)


def dfs(now):
    seen[now] = True
    score[now] += operation[now]
    for next in branch[now]:
        if seen[next] is False:
            score[next] += score[now]
            dfs(next)


N, Q = map(int, input().split())
branch = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    branch[a - 1].add(b - 1)
    branch[b - 1].add(a - 1)
operation = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    operation[p - 1] += x

seen = [False] * N
score = [0] * N
for i in range(N):
    if seen[i] is False:
        dfs(i)

for ans in score:
    print(ans, end=' ')

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
e=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a].append(b)
  e[b].append(a)
ps=[0 for i in range(n)]
for i in range(q):
  p,x=map(int,input().split())
  ps[p-1]+=x

s=[-1 for i in range(n)]
sc=[0]
s[0]=0
while sc:
  nsc=[]
  for i in sc:
    s[i]+=ps[i]
    for j in e[i]:
      if s[j]==-1:
        nsc.append(j)
        s[j]=s[i]
  sc=nsc


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

Submission status: Accepted

Solution code:
from collections import deque

def dfs(tree, cost, root):
    q = deque([root])
    dist = [-1]*N

    dist[root] = cost[root]

    while q:
        v = q.pop()
        for n_v in tree[v]:
            if dist[n_v] < 0:
                dist[n_v] = dist[v] + cost[n_v]
                q.append(n_v)

    return dist

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)

pts = [0]*N

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

dist = dfs(tree, pts, 0)

for i in range(N):
    print(dist[i])

Submission status: Accepted

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

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

seen = [False]*N

def dfs(v, seen, G, counter):
    seen[v] = True
    for u in G[v]:
        if not seen[u]:
            counter[u] += counter[v]
            dfs(u, seen, G, counter)

dfs(0, seen, G, counter)

for c in counter:
    print(c, end = " ")
print("")

Submission status: Accepted

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

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

stack, seen = [0], [False]*N
while stack:
    v = stack.pop()
    seen[v] = True

    for u in G[v]:
        if not seen[u]:
            stack.append(u)
            counter[u] += counter[v]

for c in counter:
    print(c, end = " ")
print("")

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### 木の読み込み tree

n,q = map(int, input().split())
ns = [[] for _ in range(n)]
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append(v)
    ns[v].append(u)
vals = [0]*n
for _ in range(q):
    p,x = map(int, input().split())
    vals[p-1] += x
ans = [0]*n
done = [False]*n
s = [(0, vals[0])]
done[0] = True
while s:
    u,val = s.pop()
    ans[u] = val
    for v in ns[u]:
        if done[v]:
            continue
        done[v] = True
        s.append((v, val+vals[v]))
write(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import deque
N,Q = map(int, input().split())
a = [0] * (N-1)
b = [0] * (N-1)
g=[[] for i in range(N+1)]
for i in range(N-1):
    a[i], b[i] = map(int, input().split())
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])
p = [0] * Q
x = [0] * Q
ans=[0]*(N+1)
for i in range(Q):
    p[i], x[i] = map(int, input().split())
    ans[p[i]]+=x[i]
    
q = deque([1]) 
ch=[0]*(N+1)
while len(q) > 0:
    pp = q.popleft()     # キュー取りだし（先頭）
    if ch[pp]==0:
        ch[pp]=1
    for u in g[pp]:
        if ch[u]!=1:
           
            ans[u]+=ans[pp]
            q.append(u)
    #print(pp,l,q)

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

Submission status: Accepted

Solution code:
from collections import deque
N,Q = map(int, input().split())
a = [0] * (N-1)
b = [0] * (N-1)
g=[[] for i in range(N+1)]
for i in range(N-1):
    a[i], b[i] = map(int, input().split())
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])
p = [0] * Q
x = [0] * Q
ans=[0]*(N+1)
for i in range(Q):
    p[i], x[i] = map(int, input().split())
    ans[p[i]]+=x[i]
    
q = deque([1]) 
ch=[0]*(N+1)
while len(q) > 0:
    pp = q.popleft()     # キュー取りだし（先頭）
    if ch[pp]==0:
        ch[pp]=1
    for u in g[pp]:
        if ch[u]==1:
            continue
        ans[u]+=ans[pp]
        q.append(u)
    #print(pp,l,q)

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import defaultdict
import sys
sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, q = input_int_list()
    cnt = [0] * (n + 1)  # 1-indexed
    tree = defaultdict(list)

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

    # 遅延評価をする O(q)
    for _ in range(q):
        p, x = input_int_list()
        cnt[p] += x

    # 遅延評価（DFS）O(n)
    stack = [(1, 0)]
    visited = set([1])
    while stack:
        e, add = stack.pop()
        cnt[e] += add
        for node in tree[e]:
            if node not in visited:
                visited.add(node)
                stack.append((node, cnt[e]))

    print(" ".join([str(i) for i in cnt[1:]]))
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n,q=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in range(n-1)]
    tree=[list() for _ in range(n)]
    score=[0]*n
    for a,b in ab:
        a,b=a-1,b-1
        tree[a].append(b)
        tree[b].append(a)
    e = [0]
    while len(e) > 0:
        i = e.pop()
        for j in tree[i]:
            tree[j].remove(i)
            e.append(j)
    px=[list(map(int,input().split())) for _ in range(q)]
    for p,x in px:
        p-=1
        score[p]+=x
    add(tree,score)
    print(*score)

def add(tree,score):
    s=tree[0][:]
    for i in s:
        score[i] += score[0]
    while len(s)>0:
        t = s.pop()
        for i in tree[t]:
            s.append(i)
            score[i] += score[t]

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue

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

ki = [[0,[]] for _ in range(N)]

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

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

seen = [False for _ in range(N)]
que = queue.Queue()
que.put(0)
while not(que.empty()):
    now = que.get()
    seen[now] = True
    # print(ki[now][1])
    for i in range(len(ki[now][1])):
        nxt = ki[now][1][i]
        if seen[nxt]:
            continue
        else:
            ki[nxt][0] += ki[now][0]
            que.put(nxt)

for i in range(N):
    print("{} ".format(ki[i][0]),end="")
print()

Submission status: Accepted

Solution code:
from collections import deque

N, Q = map(int, input().split()) # Nは頂点の数、Qは操作の回数
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)

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

q = deque()
q.append(1)
visited[1] = 1
while q:
    node = q.pop()

    next_nodes = graph[node]
    for next in next_nodes:
        if visited[next] != -1:
            continue
        q.append(next)
        visited[next] = 1
        counts[next] += counts[node]

print(*counts[1:])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)
N, Q = map(int,input().split())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

d = defaultdict(int)
for _ in range(Q):
    p,x = map(int,input().split())
    d[p-1] += x
visited = [False]*N
cnt = [0]*N
def dfs(n, acc):
    cnt[n] = acc
    for m in edges[n]:
        if not visited[m]:
            visited[m] = True
            dfs(m, acc+d[m])
visited[0] = True
dfs(0, d[0])
print(*cnt)

Submission status: Accepted

Solution code:
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 6)


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

# 1 2 3
# a, b, c = LI()


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

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


n, q = LI()
point = [0]*n
graph = [[] for i in range(n)]
visited = [False]*n


def dfs(n):
    visited[n-1] = True
    for node in graph[n-1]:
        if visited[node-1]:
            continue
        point[node-1] += point[n-1]
        dfs(node)


def main():

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

    for i in range(q):
        p, x = LI()
        point[p - 1] += x

    dfs(1)

    print(*point)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
 
N, Q = map(int, input().split())
root = [[] for _ in range(N)]
ans = [0]*N
 
for _ in range(N-1):
  a,b=map(int, input().split())
  a,b=a-1,b-1
  root[a].append(b)
  root[b].append(a)

for _ in range(Q):
  p,x=map(int, input().split())
  ans[p-1]+=x
  
visited=[False]*N
def dfs(v):
  visited[v] = True
  for go in root[v]:
    if visited[go]:
      continue
    ans[go] += ans[v]
    dfs(go)

dfs(0)
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1<<30)
N,Q = map(int,input().split())
def dfs(x, score):
    for y in Tree[x]:
        if Parent[x] != y:
            Parent[y] = x
            score[y] += score[x]
            dfs(y, score)
Tree = [[] for i in range(N+1)]
Parent = [0]*(N+1)
for i in range(N-1):
    a,b = map(int,input().split())
    Tree[a].append(b)
    Tree[b].append(a)
score = [0]*(N+1)
for j in range(Q):
    p,x = map(int,input().split())
    score[p] += x
dfs(1,score)
print(*score[1:],end="\t")

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
tree=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)
count=[0]*n
for _ in range(q):
    p,cnt=map(int,input().split())
    count[p-1]+=cnt
stack=deque([[0,0,-1]])
while stack:
    num,cnt,pr=stack.pop()
    count[num]+=cnt
    for k in tree[num]:
        if k==pr:
            continue
        stack.append([k,count[num],num])
print(*count)

Submission status: Accepted

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

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)]

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

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

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)
print(*value[1:],end="\t")

Submission status: Accepted

Solution code:
N,Q=list(map(int,input().split()))
l=[[] for i in range(N)]
for i in range(N-1):
   a,b=list(map(int,input().split()))
   l[a-1].append(b-1)
   l[b-1].append(a-1)
l_c=[0]*N
for i in range(Q):
   a,b=list(map(int,input().split()))
   l_c[a-1]+=b
visited=[0]*N
from collections import deque
def ans(start):
   que=deque([start])
   visited[start]=1
   while que:
      node=que.popleft()
      for i in l[node]:
         if visited[i]==0:
            l_c[i]+=l_c[node]
            que.append(i)
            visited[i]=1
ans(0)
print(*l_c)

Submission status: Accepted

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

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

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

    adj[b-1].append(a-1)
    adj[a-1].append(b-1)

cnt = [0] * n
for i in range(q):
    p, x = list(map(int, input().split()))

    cnt[p-1] += x

counter = [0] * n
visited = [True] + [False] * (n-1)
visit = [0]

while len(visit) > 0:
    node = visit.pop()
    counter[node] += cnt[node]

    for adjNode in adj[node]:
        if visited[adjNode] == False:
            visited[adjNode] = True
            visit.append(adjNode)

            counter[adjNode] += counter[node]

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

Submission status: Accepted

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


N, Q = map(int, input().split())
to = [[] for _ in range(N)]
ans = [0] * N

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


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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys #追加
sys.setrecursionlimit(500*500)

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

cost=[0]*n
edge = [[] for _ in range(n)]

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

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


visited=[-1]*n


def dfs(n,c):

    cost[n]+=c
    tmp=cost[n]
    visited[n]=0

    for v in edge[n]:
        if visited[v]==-1:
            dfs(v,tmp)
    

dfs(0,0)

print(*cost)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
num=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    num[a-1].append(b)
    num[b-1].append(a)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
queue=deque()
queue.append(0)
seen=[False]*n
for i in range(n):
    if len(queue)==0:
        break
    num1=queue.popleft()
    seen[num1]=True
    num2=num[num1]
    for j in range(len(num2)):
        if seen[num2[j]-1]==False:
            ans[num2[j]-1]+=ans[num1]
            queue.append(num2[j]-1)
for i in ans:
    print(i)

Submission status: Accepted

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

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

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

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

visited = [False]*n
def dfs(n):
    visited[n] = True
    for i in trees[n]:
        if visited[i]:
            continue
        ans[i] += ans[n]
        dfs(i)
dfs(0)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n, q = list(map(int, input().split(" ")))
    v_list = [[] for i in range(n)]
    for _ in range(n-1):
        a, b = list(map(int, input().split(" ")))
        v_list[a-1].append(b-1)
        v_list[b-1].append(a-1)

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

    point_list = [0]*n
    checked_list = [0]*n
    stack = deque([0]) 
    while stack:
        cur = stack.pop()
        checked_list[cur] = 1
        point_list[cur]+=p_x_list[cur]
        for next_i in v_list[cur]:
            if checked_list[next_i]:
                continue
            stack.append(next_i)
            point_list[next_i]+=point_list[cur]
   
    print(*point_list)

if __name__=="__main__":
    main()

Submission status: Accepted

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

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

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

def dfs(now,prev=-1):
  for next in G[now]:
    if next==prev:
      continue
    S[next]+=S[now]
    dfs(next,now)

dfs(1)
print(*S[1:])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
L=[[] for i in range(n+1)]
S=[0 for i in range(n+1)]
V=[0 for i in range(n+1)]

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

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


que=[1]
head=0
V[1]=1
while len(que)>head:
    now=que[head]
    head+=1
    for nex in L[now]:
        if V[nex]==0:
            V[nex]=1
            que.append(nex)
            S[nex]+=S[now]

print(" ".join([str(i) for i in S[1:]]))

Submission status: Accepted

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

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

gone = [False for _ in range(N)]

def dfs(counter, count, cur_node):
    count += P[cur_node]
    gone[cur_node] = True
    counter[cur_node] += count
    for next_node in Edges[cur_node]:
        if gone[next_node]:
            continue
        dfs(counter, count, next_node)

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

for c in counter:
    print(c)

Submission status: Accepted

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

def dfs(v, cnt):
    seen = [0] * (N+1)
    seen[v] = 1
    stack = [v]
    while stack:
        v = stack[-1]
        if G[v]:
            w = G[v].popleft()
            if not seen[w]: # if 訪れていなければ
                cnt[w] += cnt[v]
                seen[w] = 1
                stack.append(w)
        else:
            stack.pop()
    return cnt

cnt = dfs(1, cnt)
print(*cnt[1:])

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    import queue
    N,Q=MI()
    adj=[[]for _ in range(N)]
    for _ in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
        
    ans=[0]*N
    for _ in range(Q):
        p,x=MI()
        p-=1
        ans[p]+=x
        
    q=queue.Queue()
    q.put((0,-1))
    
    while not q.empty():
        v,p=q.get()
        for nv in adj[v]:
            if nv!=p:
                ans[nv]+=ans[v]
                q.put((nv,v))
                
    print(' '.join(map(str, ans)))
        
    

main()

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n-1)]
e = [list() for _ in range(n)]
for a,b in ab:
    e[a-1] += [b-1]
    e[b-1] += [a-1]
px = [list(map(int,input().split())) for _ in range(q)]
omomi = [0]*n
for p,x in px:
    omomi[p-1] += x

visited = [0]*n
visited[0] = 1
stack = [0]

while stack:
    v = stack.pop()
    for k in e[v]:
        if visited[k]==0:
            omomi[k] += omomi[v]
            visited[k] = 1
            stack.append(k)

print(*omomi)

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(10**9)

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N, Q = mi()
    a, b = i2(N-1)
    p, x = i2(Q)

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

    child = [[] for i in range(N)]
    parent = [None]*N

    q = deque([0])
    while q:
        now = q.pop()
        for v in d[now]:
            if parent[now] == v:
                continue
            parent[v] = now
            q.appendleft(v)

    c = [0]*N
    for i in range(Q):
        c[p[i]-1] += x[i]

    @lru_cache(maxsize=None)
    def dfs(i):
        if parent[i] == None:
            return c[i]
        
        return c[i]+dfs(parent[i])

    print(*[dfs(i) for i in range(N)])

if __name__ == '__main__':
    main()