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:
from collections import deque
n,q = map(int,input().split())
ki = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)
score = [0 for i in range(n)]

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

#print(ki,score)
ans = [0 for i in range(n)]

ans[0] = score[0]
visited = [False]*n
visited[0] = True
Q = deque([0])

while Q:
    d = Q.pop()
    #print(d)
    for to in ki[d]:
        if visited[to]:
            continue
        
        ans[to] = ans[d] + score[to]
        #print(ans[to],ans[d],score[to],d)
        visited[to] = True
        Q.append(to)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque


def main():

    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)

    q = deque()
    score = [0] * N
    seen = [0] * N
    for _ in range(Q):
        a, s = map(int, input().split())
        score[a-1] += s

    q.append(0)
    while q:
        tmp = q.pop()
        seen[tmp] += 1
        for v in G[tmp]:
            if seen[v]:
                continue
            q.append(v)
            score[v] += score[tmp]

    print(*score)


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(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
  
visitted=[False]*N
def dfs(v):
  visitted[v] = True
  for go in root[v]:
    if visitted[go]:
      continue
    ans[go] += ans[v]
    dfs(go)

dfs(0)
print(*ans)

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
  
visit = [False]*N
def dfs(n):
  visit[n] = True
  for go in root[n]:
    if visit[go]:
      continue
    ans[go] += ans[n]
    dfs(go)

dfs(0)
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
 
N, Q = map(int, input().split())
root = [[] for i in range(N)]
ans = [0]*N
 
for i 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 i in range(Q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
visit = [False]*N
def dfs(n):
  visit[n] = True
  for go in root[n]:
    if visit[go]:
      continue
    ans[go] += ans[n]
    dfs(go)

dfs(0)
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2*10**9)
N, Q = map(int, input().split())
A = [[] for _ in range(N)]
for _ in range(N-1):
    i, k = map(int, input().split())
    A[i-1].append(k-1)
    A[k-1].append(i-1)
n_P = [0] * N
for _ in range(Q):
    k, n = map(int, input().split())
    n_P[k-1] += n
ans = [0] * N
visited = [0] * N
def make(num, p):
    ans[num] += n_P[num] 
    ans[num] += p
    visited[num] = 1
    for i in A[num]:
        if visited[i] == 0:
            make(i,ans[num])
    return
make(0, ans[0])
print(*ans)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

n,q = LI()
root = [[] for _ in range(n+1)]
quest = [0 for _ in range(n+1)]

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

for _ in range(q):
    p,x = LI()
    quest[p] += x

stock = collections.deque([1])
explored = set()

while len(stock) != 0:
    next = stock.pop()
    explored.add(next)
    for i in root[next]:
        if i not in explored:
            stock.append(i)
            quest[i] += quest[next]
print(*quest[1:])

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,q = LI()
    root = [[] for _ in range(n+1)]
    quest = [0 for _ in range(n+1)]

    for _ in range(n-1):
        a,b = LI()
        root[a].append(b)
        root[b].append(a)
    
    for _ in range(q):
        p,x = LI()
        quest[p] += x

    stock = collections.deque([1])
    explored = set()

    while len(stock) != 0:
        next = stock.pop()
        explored.add(next)
        for i in root[next]:
            if i not in explored:
                stock.append(i)
                quest[i] += quest[next]
    print(*quest[1:])
main()

Submission status: Accepted

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

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

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

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

def df(current, score):
    next_nodes = adj_list[current]
    reached[current]=1
    for node in next_nodes:
        if reached[node]==0:
            counter[node]+=score
            df(node, counter[node])

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

Submission status: Accepted

Solution code:

# copy from https://atcoder.jp/contests/abc138/submissions/15674047

import sys
import heapq
import math


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


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

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

    counter = [0] * N

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

    visited = set()
    stack = [0]
    while stack:  # 深さ優先
        i = stack.pop()
        visited.add(i)
        for j in tree[i]:
            if not j in visited:  # 逆方向回るの防止
                counter[j] += counter[i]
                stack.append(j)
    print(*counter)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
N,Q=map(int,input().split())
arr=[[] for i in range(N)]

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

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


#print(lis)
vist=[0]*N
d=collections.deque()
d.append(0)
while d:
    a=d.pop()
    vist[a]=1
    
    for j in arr[a]:
        
        if vist[j]==1:
            continue
        lis[j]+=lis[a]
        d.append(j)
 #   print(a,d,lis,vist)



print(*lis)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
tree = [[] for i in range(n)]
l = [0]*n

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

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

q = [0]
s = [-1]*n
s[0] = l[0]
while len(q) > 0:
    r = q.pop()
    for i in tree[r]:
        if s[i] == -1:
            s[i] = s[r] + l[i]
            q.append(i)
print(*s)

Submission status: Accepted

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

N,Q=map(int,input().split())
edge=[[] for _ in range(N+1)]
score=[0]*(N+1)
for _ in range(N-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)

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

visited=set()

def dfs(v):
    global score
    visited.add(v)
    for i in edge[v]:
        if i in visited:
            continue
        score[i]+=score[v]
        dfs(i)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(400000)
n,q=map(int,input().split())
ans=[0]*(n+1) #答え
score=[0]*(n+1) #xの総和
g=[[] for _ in range(n+1)] #グラフ
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
for j in range(q):
    p,x=map(int,input().split())
    score[p]+=x

visited=[0]*(n+1)
def dfs(v):
    visited[v]+=1
    global ans
    ans[v]+=score[v]
    for i in range(len(g[v])):
        if visited[g[v][i]]==0:
            ans[g[v][i]]+=ans[v]
            dfs(g[v][i])
dfs(1)
print(" ".join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(400000)
n,q=map(int,input().split())
ans=[0]*(n+1) #答え
score=[0]*(n+1) #xの総和
g=[[] for _ in range(n+1)] #グラフ
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
for j in range(q):
    p,x=map(int,input().split())
    score[p]+=x

visited=[0]*(n+1)
def dfs(v):
    visited[v] += 1
    global ans
    ans[v]+=score[v]
    for i in range(len(g[v])):
        if visited[g[v][i]] == 0:
            ans[g[v][i]]+=ans[v]
            dfs(g[v][i])
dfs(1)
print(" ".join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
l=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    l[a].append(b)
    l[b].append(a)
xl=[0 for i in range(n)]
for i in range(q):
    p,x=map(int,input().split())
    p-=1
    xl[p]+=x
#DFS
que=[0]
s=[-1 for i in range(n)]
s[0]=xl[0]
while len(que)>0:
    r=que.pop()
    for i in l[r]:
        if s[i]==-1:
            s[i]=s[r]+xl[i]
            que.append(i)
print(*s)

Submission status: Accepted

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

def dfs(x):
    seen[x]=1
    for nx in lis[x]:
        if seen[nx]==0:
            psum[nx]=psum[x]+plis[nx]
            dfs(nx)

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

lis=[[] for i in range(n)]

for _ in range(n-1):
    ai,bi=map(lambda x:int(x)-1,input().split())
    lis[ai].append(bi)
    lis[bi].append(ai)

plis=[0 for i in range(n)]

for _ in range(q):
    pi,xi=map(int,input().split())
    plis[pi-1]+=xi

seen=[0 for _ in range(n)]
psum=[0 for _ in range(n)]
psum[0]=plis[0]

dfs(0)

print(*psum)

Submission status: Accepted

Solution code:
# 木上の累積和

import sys
from collections import defaultdict
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))


def ints():
    return list(map(int, read().split()))


N, Q = ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = mina(*ints())
    tree[a].append(b)
    tree[b].append(a)
cnt = [0] * N
for _ in ra(Q):
    q, x = ints()
    cnt[q - 1] += x
cnt.append(0)  # -1アクセス用

# dfsでcntに木に沿った累積和をsetしていく

def dfs(u, p):  # 戻り値なしver
    S_args = [(u, p)]  # 引数管理のstack
    S_cmd = [0]  # 0:into, 1:outofの処理をすべきと記録するstack

    def into(args):
        '''入るときの処理'''
        u, p = args
        cnt[u] += cnt[p]

    def nxt(args):
        S_args.append(args)  # 抜けるときに戻ってくることを予約
        S_cmd.append(1)
        '''今の引数からみて次の引数を列挙'''
        u, p = args
        for nx in tree[u]:
            if nx == p:
                continue
            _stack(nx, u)

    def outof(args):
        '''抜けるときの処理'''
        pass

    def _stack(*args):  # お好きな引数で
        S_args.append(args)
        S_cmd.append(0)

    while S_cmd:
        now_args = S_args.pop()
        cmd = S_cmd.pop()
        if cmd == 0:
            into(now_args)
            nxt(now_args)  # 次の再帰する(次のintoを予約)
        else:
            outof(now_args)


dfs(0, -1)

print(*cnt[:-1])

Submission status: Accepted

Solution code:
# 木上の累積和

import sys
from collections import defaultdict
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))


def ints():
    return list(map(int, read().split()))


N, Q = ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = mina(*ints())
    tree[a].append(b)
    tree[b].append(a)
cnt = [0] * N
for _ in ra(Q):
    q, x = ints()
    cnt[q - 1] += x
cnt.append(0)  # -1アクセス用

# dfsでcntに木に沿った累積和をsetしていく


# def dfs(u, p):  # uは現在のノード、pは親のノード
#     cnt[u] += cnt[p]
#     for nv in tree[u]:
#         if nv == p:
#             continue
#         dfs(nv, u)


def dfs(u, p):  # 戻り値なしver
    S_args = [(u, p)]  # 引数管理のstack
    S_cmd = [0]  # 0:into, 1:outofの処理をすべきと記録するstack

    def into(args):
        '''入るときの処理'''
        u, p = args
        cnt[u] += cnt[p]

    def nxt(args):
        S_args.append(args)  # 抜けるときに戻ってくることを予約
        S_cmd.append(1)
        '''今の引数からみて次の引数を列挙'''
        u, p = args
        for nx in tree[u]:
            if nx == p:
                continue
            _stack(nx, u)

    def outof(args):
        '''抜けるときの処理'''
        pass

    def _stack(*args):  # お好きな引数で
        S_args.append(args)
        S_cmd.append(0)

    while S_cmd:
        now_args = S_args.pop()
        cmd = S_cmd.pop()
        if cmd == 0:
            into(now_args)
            nxt(now_args)  # 次の再帰する(次のintoを予約)
        else:
            outof(now_args)


dfs(0, -1)

print(*cnt[:-1])

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(1000000)

def DFS(node):
    if not checked[node]:
        global point
        checked[node] = True
        point += pointlist[node]
        
        for child in neighborlist[node]:
            if not checked[child]:
                DFS(child)
        
        anslist[node] += point
        point -= pointlist[node]

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

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

checked = [False]*(N+1)
anslist = [0]*(N+1)
point = 0

DFS(1)

print(*anslist[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(400000)
N, Q = map(int, input().split())
paths = [list() for _ in range(N+1)] # paths[i] : 頂点iと繋がってる点を全て表す
for _ in range(N-1):
    a, b = map(int, input().split())
    paths[a].append(b)
    paths[b].append(a)
# ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]

ans = [0]*(N+1) # ans[i] : 頂点iについて答える値を格納

counters = [0]*(N+1) # そのノードの部分木に与える点数の総和を格納
for x in px:
    counters[x[0]] += x[1]

visit = [0]*(N+1) #dfsをする時に一度訪れた点に再訪しないための確認
def dfs(node, score, ans):
    visit[node] = 1 # 訪問したことを記録
    score += counters[node] # 自分の部分木に加点する分を加えて後世に残す
    ans[node] = score # 点数の記録
    for loof in paths[node]: # 自分と繋がってる各ノードについて
        if visit[loof] == 0: # まだ探索していなければ
            dfs(loof, score, ans) # 探索

dfs(1, 0, ans)
    

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

Submission status: Accepted

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

N,Q = map(int,input().split())
path = [[] for i in range(N)]
ans = [0] * N
def dfs(v,p=-1):
    for to in path[v]:
        if to == p :
            continue
        ans[to] += ans[v]
        dfs(to,v)

for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)
for i in range(Q):
    P,X = map(int,input().split())
    ans[P-1] += X
dfs(0)
print(*ans)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
g = [[] for _ in range(n+1)]
d = [0]*(n+1)
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)
for _ in range(q):
    p,x = map(int,input().split())
    d[p] += x
ans = [0]*(n+1)
seen = [False]*(n+1)
from collections import deque
q = deque([(1,d[1])])
while q:
    s,cost = q.popleft()
    seen[s] = True
    ans[s] += cost
    for e in g[s]:
        if not seen[e]:
            q.append((e,cost+d[e]))
# def helper(s,cost):
#     seen[s] = True
#     ans[s] += cost
#     for e in g[s]:
#         if not seen[e]:
#             helper(e,cost+d[e])
# for i in range(1,n+1):
#     if not seen[i]:
#         helper(i,d[i])
res = []
for a in ans[1:]:
    res.append(str(a))

print(' '.join(res))

Submission status: Accepted

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

from collections import deque

dist=[-1]*(N+1) # 出力に合わせて適宜変更
dist[0]=0
dist[1]=0

D=deque()
D.append(1)

while D:
    V=D.popleft()
    for i in A[V]:
        if dist[i]!=-1:
            continue
        dist[i]=0
        B[i]+=B[V] # 出力に合わせて適宜変更（答えに直結するので最重要）
        D.append(i)

print(*B[1:])

Submission status: Accepted

Solution code:
import copy
import math
import time
import statistics
import math
import itertools
import bisect
import sys
from decimal import *

# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():

    start = time.time()

    n, q = get_int_multi()

    a = [[] for _ in range(n+1)]
    for _ in range(n-1):
        s, e = get_int_multi()
        a[s].append(e)
        a[e].append(s)

    point = [0] * (n+1)
    for _ in range(q):
        p, x = get_int_multi()
        point[p] += x

    def tasu(now, prev):
        for next in a[now]:
            if next == prev:
                continue
            point[next] += point[now]
            tasu(next, now)

    sys.setrecursionlimit(10 ** 6)
    tasu(1, -1)
    point = point[1:] #１つ目は0なので除去（inputは1始まりなので、0は使わない）
    print(*point) # * は引数展開　listの中身を引数にする。例えばprint(*[1,2,3])はprint(1,2,3)になり 1 2 3 が出力される


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
lst=[[] for i in range(n)]
ans=[0]*n

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

for i in range(q):
    s,t=map(int,input().split())
    ans[s-1]+=t

Q=[0]

flag=[True]+[False]*(n-1)


while Q:
  v=Q.pop()
  flag[v]=True
  for i in lst[v]:
    if flag[i]:
      continue
    flag[i]=True
    ans[i]+=ans[v]
    Q.append(i)


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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
dic = defaultdict(list)
N, Q = map(int, input().split())
point = [0 for _ in range(N)]

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

for _ in range(Q):
    p, x = map(int, input().split())
    point[p-1]+=x
    
queue = deque()
for i in dic[1]:
    queue.append(1)
    queue.append(i) #親、子
    
while queue:
    p = queue.popleft()
    c = queue.popleft()
    point[c-1]+=point[p-1] 
    
    for j in dic[c]:
        if j != p:
            queue.append(c)
            queue.append(j)
            
        
print(*point)

Submission status: Accepted

Solution code:
import math
import sys

sys.setrecursionlimit(200005)

n, q = map(int, input().split(" "))
abL = [list(map(int, input().split(" "))) for _ in range(n - 1)]
pxL = [list(map(int, input().split(" "))) for _ in range(q)]

to = [[] for _ in range(200005)]
ans = [0 for _ in range(n + 1)]


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


for a, b in abL:
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

for p, x in pxL:
    p -= 1
    ans[p] += x

dfs(0)

for a in ans[:n]:
    print(a)

Submission status: Accepted

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

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

cnt = [0]*(N+1)
for _ in range(Q):
    P, X = map(int, input().split())
    cnt[P] += X

flag = [False]*(N+1)

q = [1]
while q:
    n = q.pop()
    flag[n] = True
    for i in w[n]:
        if flag[i]:
            continue
        flag[i] = True
        cnt[i] += cnt[n]
        q.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque
n, q = map(int, input().split())

road = [[] for _ in range(n)]
cnt = [0 for _ in range(n)]

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

for i in range(q):
    idx, v = map(int, input().split())
    cnt[idx - 1] += v

dist = [-1] * n
que = deque()
dist[0] = 0
que.append(0)

while(len(que) != 0):
    # BFS/DFS
    v = que.pop()
    for r in road[v]:
        if dist[r] != -1:
            continue
        # print(r, v)
        dist[r] = dist[v] + 1
        cnt[r] += cnt[v]
        que.append(r)
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 j in range(Q):
    p, x = map(int, input().split())
    count[p-1] += x

visited = [False] * N
que = deque([0])

while que:
    now = que.pop()
    visited[now] = True
    for nxt in G[now]:
        if visited[nxt]:
            continue
        count[nxt] += count[now]
        que.appendleft(nxt)

print(*count)

Submission status: Accepted

Solution code:
from collections import deque
# from collections import Counter
# from itertools import accumulate
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt

# input = sys.stdin.readline
# def main():

#---------------------------------------------------------

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

road = [[] for _ in range(n)]
cnt  = [0 for _ in range(n)]

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

for i in range(q):
    idx,v = map(int,input().split())
    cnt[idx-1] += v

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
    # BFS/DFS
    v = que.pop()
    for r in road[v]:
        if dist[r]!=-1:
            continue
        dist[r] = dist[v] + 1
        cnt[r] += cnt[v]
        que.append(r)

print(*cnt)

Submission status: Accepted

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

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

que = deque([0])
flag = [False] * N

while que:
    v = que.pop()
    flag[v] = True
    for e in G[v]:
        if flag[e]:
            continue
        count[e] += count[v]
        que.appendleft(e)

print(*count)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, q = MAP()
graph = [[] for i in range(n)]
point = [0]*n
for i in range(n-1):
    a, b = MAP()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
for i in range(q):
    p, x = MAP()
    point[p-1] += x

# 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:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 50

def dfs(current, node_vals, seen, to):
    for next in to[current]:
        if not seen[next]:
            node_vals[next] += node_vals[current]
            seen[next] = 1
            dfs(next, node_vals, seen, to)


def run():
    N, Q = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    for i in range(N-1):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)

    node_vals = [0] * (N+1)

    for i in range(Q):
        p, x = map(int, sysread().split())
        node_vals[p] += x

    seen = [0] * (N+1)
    seen[1] = 1
    dfs(1, node_vals, seen, to)

    node_vals = [str(v) for v in node_vals]
    print(' '.join(node_vals[1:]))

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
from collections import deque
import copy

# グラフの作成(無向グラフでは#を消す)
n, q = map(int, input().split())
graph = [deque([]) for _ in range(n+1)]
for _ in range(n-1):
    a, b  = [int(x) for x in input().split()]
    graph[a].append(b)
    graph[b].append(a) # 無向グラフ
#print(graph)
q_sum_list = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    q_sum_list[p-1] += x
#print(q_sum_list)
arrive_rireki = [-1] * (n + 1)

score = [0]*n
score_temp = 0

# 深さ優先探索
def dfs(v):
    global score_temp
    stack = [v]
    arrive_rireki[v] = 1
    score_temp += q_sum_list[v-1]
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_rireki[w] < 0:
                arrive_rireki[w] = 1
                stack.append(w)
                score_temp += q_sum_list[w-1]
        else:
            stack.pop()
            score[v-1] = score_temp
            score_temp -= q_sum_list[v-1]
    return score

dfs(1)
#print(eda_list)
print(* score)

Submission status: Accepted

Solution code:
from collections import deque
import copy

# グラフの作成(無向グラフでは#を消す)
n, q = map(int, input().split())
graph = [deque([]) for _ in range(n+1)]
for _ in range(n-1):
    a, b  = [int(x) for x in input().split()]
    graph[a].append(b)
    graph[b].append(a) # 無向グラフ
#print(graph)
q_sum_list = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    q_sum_list[p-1] += x
#print(q_sum_list)
arrive_rireki = [-1] * (n + 1)

score = [0]*n
score_temp = 0

# 深さ優先探索
def dfs(v):
    global score_temp
    #arrive_rireki = [-1] * (n + 1)
    #print("check", graph_temp, arrive_rireki) #deepcopy の確認
    stack = [v]
    arrive_rireki[v] = 1
    score_temp += q_sum_list[v-1]
    while stack:
        #print("stack", stack)
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_rireki[w] < 0:
                arrive_rireki[w] = 1
                stack.append(w)
                score_temp += q_sum_list[w-1]
        else:
            stack.pop()
            #score[v-1] += q_sum_list[v-1]
            score[v-1] = score_temp
            score_temp -= q_sum_list[v-1]
            #print("stack pop", v, stack)
            #for i in range(len(stack)):
            #    score[v-1] += q_sum_list[stack[i]-1]
                #print(score, q_sum_list[stack[i]-1])
    return score

dfs(1)
#print(eda_list)
print(* score)

Submission status: Accepted

Solution code:
from collections import deque
 
N, Q = map(int, input().split())
Ki = [[] for _ in range(N)]
for _ in range(N-1):
    p, c = map(int, input().split())
    Ki[p-1].append(c-1)
    Ki[c-1].append(p-1)
S = [0]*N
for _ in range(Q):
    node, score = map(int, input().split())
    S[node-1] += score
 
stack = deque([0])
done = [0]*N
done[0] = 1
 
while len(stack) > 0:
    now = stack.pop()
    
    for new in Ki[now]:
        if done[new] == 0:
            done[new] = 1
            stack.append(new)
            S[new] += S[now]
    
print(*S)