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
from collections import defaultdict, deque
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n, q = map(int, readline().split())
G = defaultdict(list)
for _ in range(n-1):
    a, b = map(int, readline().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
count = [0] * n
for _ in range(q):
    p, x = map(int, readline().split())
    count[p-1] += x


def dfs(root, x):
    ans[root] = count[root] + x
    for i in G[root]:
        if ans[i] == -1:
            dfs(i, ans[root])


ans = [-1] * n
ans[0] = count[0]
q = deque([0])
while q:
    root = q.pop()
    for i in G[root]:
        if ans[i] == -1:
            q.append(i)
            ans[i] = ans[root] + count[i]

# dfs(0, 0)
print(*ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d
n, q = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

def dfs(graph, counter, visited, p, x, n):
    stack = [p]
    visited[p] = True
    while stack:
        node = stack.pop()
        # counter[node] += x
        for n in graph[node]:
            if not visited[n]:
                stack.append(n)
                visited[n] = True
                counter[n] += counter[node]

counter = [0] * n
visited = [False] * n
for _ in range(q):
    # まとめて一括で更新することで、dfsの回数を減らす。
    p, x = map(int, input().split())
    p -= 1
    counter[p] += x

for p in range(len(counter)):
    dfs(graph, counter, visited, p, x, n)
print(*counter)

Submission status: Accepted

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

d = [0]*(N+1)
visit = [0]*(N+1)
for i in range(Q):
    p,x = map(int,input().split())
    d[p]+=x
def bfs(s):
    q = deque([s])
    while q:
        v = q.pop()
        visit[v] = 1
        for j in E[v]:
            if(visit[j] == 1):
                continue
            q.append(j)
            d[j] += d[v]
            
bfs(1)
for i in range(1,N+1):
    print(d[i])

Submission status: Accepted

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

N, Q = map(int, input().split())
graph = [[] for i in range(N)]

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

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


seen_points = [True] * N
seen_points[0] = False
stack = [0]

while stack:
    now = stack.pop()
    for i in graph[now]:
        if seen_points[i]:
            seen_points[i] = False
            stack.append(i)
            v[i] += v[now]

print(*v)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]
 
sys.setrecursionlimit(1000000)
mod = 1000000007
 
#A
def A():
    a = I()
    s = input()
    if a >= 3200:
        print(s)
    else:
        print("red")
    return
 
#B
def B():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
    return
 
#C
def C():
    n = I()
    v = LI()
    q = []
    for i in v:
        heappush(q,i)
    while q:
        x = heappop(q)
        if not q:
            print(x)
            return
        y = heappop(q)
        heappush(q,(x+y)/2)
    return
 
#D
def D():
    def dfs(x,d,s):
        for y in v[x]:
            if d[y]:
                s += f[y]
                ans[y] = s
                d[y] = 0
                dfs(y,d,s)
                s -= f[y]
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    ans = [0]*n
    d = [1]*n
    d[0] = 0
    ans[0] = f[0]
    s = f[0]
    dfs(0,d,s)
    print(*ans)
    return
 
#E
def E():
    s = input()
    t = input()
 
    return
 
#F
def F():
 
    return
 
#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())

g = [[] for _ in range(n)]
c = [0] * n
visited = [False] * n

#根に近い順に累積和
def dfs(i):
    visited[i] = True
    for j in g[i]:
        if visited[j] == True:
            continue
        c[j]+=c[i]
        dfs(j)

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())
    c[p - 1]+=x

dfs(0)
print(*c)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
score = [0]*N
visited = [False]*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 j in range(Q):
  p, x = map(int, input().split())
  p -= 1
  score[p] += x

def dfs(pos):
  visited[pos] = True
  for next_pos in G[pos]:
    if visited[next_pos] == True:
      continue
    score[next_pos] += score[pos]
    dfs(next_pos)
dfs(0)
score = [str(s)  for s in score]
ans = ' '.join(score)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    N,Q=map(int,readline().split())
    g=[[] for _ in range(N)]
    for _ in range(N-1):
        a,b=map(lambda x:int(x)-1,readline().split())
        g[a].append(b)
        g[b].append(a)
    count=[0]*N
    for _ in range(Q):
        p,x=map(int,readline().split())
        p-=1
        count[p]+=x
    
    #累積和を根から
    d=deque([[0,0]])
    is_searched=[False]*N
    is_searched[0]=True
    while len(d)>=1:
        now=d.popleft()
        x=now[0]
        s=now[1]
        s+=count[x]
        count[x]=s
        for nex in g[x]:
            if is_searched[nex]==False:
                is_searched[nex]=True
                d.append([nex,s])

    print(*count)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

N, Q = map(int, input().split())
info = [[] for _ in range(N)]
ans = [0 for _ in range(N)]
check = [1 for _ in range(N)]

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


def plus(n, val):
    ans[n] += val
    check[n] = 0
    for i in info[n]:
        if check[i]:
            plus(i, val + Query[i])


Query = [0 for _ in range(N)]
for _ in range(Q):
    p, x = map(int, input().split())
    Query[p - 1] += x
plus(0, Query[0])
ans = list(map(str, ans))
print(" ".join(ans))

Submission status: Accepted

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

def main():
    n,q=map(int,input().split())
    t=[[] for _ in range(n+1)]
    cnt=[0]*(n+1)
    tf=[0]*(n+1)
    for i in range(n-1):
        a,b=map(int,input().split())
        t[a].append(b)
        t[b].append(a)
    for i in range(q):
        p,x=map(int,input().split())
        cnt[p]+=x
    d=deque()
    d.append(1)
    tf[1]=1
    while d:
        chk=d.popleft()
        for i in t[chk]:
            if tf[i]==1:
                continue
            else:
                d.append(i)
                tf[i]=1
                cnt[i]+=cnt[chk]
    print(' '.join(map(str,cnt[1:])))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import queue
import sys
input = sys.stdin.readline
        
N, Q = map(int, input().rstrip().split())
e = [list(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(N-1)]
q = [list(map(int, input().rstrip().split())) for _ in range(Q)]

v2e = [set() for _ in range(N)]
for a, b in e:
    v2e[a].add(b)
    v2e[b].add(a)

v = [0] * N
for i in range(Q):
    v[q[i][0]-1] += q[i][1]
    
que = queue.Queue()
que.put((0, 0))
f = [False] * N
f[0] = True
while que.qsize() > 0:
    a, b = que.get()
    v[a] += b
    for c in v2e[a]:
        if f[c] == False:
            que.put((c, v[a]))
            f[c] = True
            
print(' '.join(list(map(str, v))))

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,Q = list(map(int,input().split()))
    edges = [[] for i in range(N+1)]
    for i in range(N-1):
        a,b = list(map(int,input().split()))
        edges[a].append(b)
        edges[b].append(a)

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

    stack = [(1,0)]
    ans = [0]*(N+1)
    not_checked = [True]*(N+1)
    while stack:
        v,cnt = stack.pop()
        ans[v] = cnt+add[v]
        not_checked[v] = False
        for edge in edges[v]:
            if not_checked[edge]:
                stack.append((edge,ans[v]))

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)

N, Q = map(int, stdin.readline().split())
graph = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, stdin.readline().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
counter = [0] * N
for i in range(Q):
    p, x = map(int, stdin.readline().split())
    counter[p - 1] += x


def dfs(now, prev=-1):
    for next in graph[now]:
        if next == prev:
            pass
        else:
            counter[next] += counter[now]
            dfs(next, now)


dfs(0)
print(*counter)

Submission status: Accepted

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

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(parent,i,add):
    for k in graph[i]:
        if k != parent:
            value[k] += add
            dfs(i,k,value[k])
    

dfs(0,1,value[1])

ans = value[1:]

print(*ans)

Submission status: Accepted

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

N,Q = map(int,input().split())
graph = [[] for i in range(N)]

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

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

notv = [True]*N
notv[0] = False
stack = deque([0])

while stack:
    now = stack.pop()
    for i in graph[now]:
        if notv[i]:
            notv[i] = False
            stack.append(i)
            v[i] += v[now]

print(*v)

Submission status: Accepted

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

N,Q = map(int,input().split())
graph = [[] for i in range(N)]

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

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

notv = [True]*N
notv[0] = False
stack = deque([0])

while stack:
    now = stack.popleft()
    for i in graph[now]:
        if notv[i]:
            notv[i] = False
            stack.append(i)
            v[i] += v[now]

print(*v)

Submission status: Accepted

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

N,Q = map(int,input().split())
graph = [[] for i in range(N)]

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

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

notv = [True]*N
notv[0] = False
stack = [0]

while stack:
    now = stack.pop()
    for i in graph[now]:
        if notv[i]:
            notv[i] = False
            stack.append(i)
            v[i] += v[now]

print(*v)

Submission status: Accepted

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

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

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

from collections import deque
flag=[0]*(N+1)
q=deque([1])
while q:
    k=q.popleft()
    flag[k]=1
    for v in d[k]:
        if flag[v]==1:
            continue
        ans[v]+=ans[k]
        q.appendleft(v)

print(*ans[1:])

Submission status: Accepted

Solution code:
# 深さ優先探索の問題
import sys

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

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

# 隣接リスト
t = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = [int(i) for i in readline().split()]
    t[a-1].append(b-1)
    t[b-1].append(a-1)

# スコア
score = [0] * N
for _ in range(Q):
    p, x = [int(i) for i in readline().split()]
    #s[p-1] = s[p-1] + x
    score[p-1] += x

ans = [0] * N

# 深さ優先探索 (スタック)
rootchecker = [0] * N
rootchecker[0] = 1
stack = [0]
while stack:
    #print(stack)
    s = stack.pop()
    ans[s] += score[s]
    for c in t[s]:
        if rootchecker[c] == 0:
            ans[c] += ans[s]
            rootchecker[c] = 1
            stack.append(c)

print(*ans)

Submission status: Accepted

Solution code:
# 深さ優先探索の問題
import sys

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

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

# 隣接リスト
t = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = [int(i) for i in readline().split()]
    t[a-1].append(b-1)
    t[b-1].append(a-1)

# スコア
s = [0] * N
for _ in range(Q):
    p, x = [int(i) for i in readline().split()]
    #s[p-1] = s[p-1] + x
    s[p-1] += x

ans = [0] * N

# 深さ優先探索
def dfs(v, p, value):
    #value = value + s[v]
    value += s[v]
    ans[v] = value
    for c in t[v]:
        if c == p:
            continue
        dfs(c, v, value)

dfs(0, -1, 0)

print(*ans)

Submission status: Accepted

Solution code:
import collections
N, Q = map(int, input().split())
count = [0] * (N + 1)
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)
for _ in range(Q):
    v, val = map(int, input().split())
    count[v] += val
q = collections.deque()
q.append(1)
check = [0] * (N + 1)
while q:
    v = q.pop()
    check[v] = 1
    for u in g[v]:
        if check[u] == 1:
            continue
        count[u] += count[v]
        q.append(u)
print(*count[1:])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        fx = f[x]
        for y in v[x]:
            if d[y]:
                d[y] = 0
                f[y] += fx
                dfs(y)
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    d = [1]*n
    d[0] = 0
    q = deque([0])
    while q:
        x = q.popleft()
        fx = f[x]
        for y in v[x]:
            if d[y]:
                d[y] = 0
                f[y] += fx
                q.append(y)
    print(*f,sep=" ")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  adj[a-1].append(b-1)
  adj[b-1].append(a-1)
c = [0] * n
for _ in range(q):
  p, x = map(int, input().split())
  c[p-1] += x
parent = list(range(n))
stack = [0]
while stack:
  vertex = stack.pop()
  value = c[vertex]
  taboo = parent[vertex]
  for child in adj[vertex]:
    if child != taboo:
      c[child] += value
      parent[child] = vertex
      stack.append(child)
print(' '.join(map(str, c)))

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
C=[[] for _ in range(N+1)]
V=set([])
R=[0]*(N+1)
def main():
  for i in range(N-1):
    a,b=map(int,input().split())
    C[a].append(b)
    C[b].append(a)
  for i in range(Q):
    a,b=map(int,input().split())
    R[a]+=b

  from collections import deque
  q = deque([])
  q.append(1)
  while len(q) > 0:
    p = q.popleft()
    for i in C[p]:
      if not i in V:
        R[i]+=R[p]
        q.append(i)
    V.add(p)
  print(*R[1:])
main()

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
C=[[] for _ in range(N+1)]
V=set([])
R=[0]*(N+1)
for i in range(N-1):
  a,b=map(int,input().split())
  C[a].append(b)
  C[b].append(a)
for i in range(Q):
  a,b=map(int,input().split())
  R[a]+=b

from collections import deque
q = deque([])
q.append(1)
while len(q) > 0:
  p = q.popleft()
  for i in C[p]:
    if not i in V:
      R[i]+=R[p]
      q.append(i)
  V.add(p)
print(*R[1:])

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
def dfs(edge):
  visited=[-1]*n
  stack=deque([0])
  visited[0]=0
  while stack:
    p=stack.pop()
    for c in edge[p]:
      if visited[c]==-1:
        visited[c]=0
        cnt[c]+=cnt[p]
        stack.append(c)
  return cnt
cnt=[0]*n
for _ in range(q):
  k,x=map(int,input().split())
  k-=1
  cnt[k]+=x
ans=dfs(edge)
print(*ans)

Submission status: Accepted

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

#import numpy as np
#import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
#from heapq import heappush, heappop
#from itertools import permutations, combinations, product, accumulate, groupby
#from bisect import bisect_left, bisect_right, insort_left, insort_right
#from operator import itemgetter as ig

sys.setrecursionlimit(10 ** 7)
#nf = 10 ** 20
#INF = float("INF")
#mod = 10 ** 9 + 7

'''
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:


def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]
 深さ優先探索
def dfs(G, v):
    global time, first_order,seen,last_order
    time += 1
    first_order[v-1] = time   #　行きがけ

    seen[v-1] = True # v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        if seen[next_v-1]:
            continue
        dfs(G, next_v)

    time += 1
    last_order[v - 1] = time  # 帰りがけ
'''

N, Q = map(int,input().split())
G = defaultdict(list)
for i in range(1, N):
    a, b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)

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


def dfs(v,p=-1):

    # v からいける各頂点 next_v について
    for next_v in G[v]:
        if next_v == p:
            continue
        P[next_v-1] += P[v-1]
        dfs(next_v, v)

dfs(1)
print(*P)

'''
if __name__ == '__main__':
    main()
'''

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
ans = [0] * N

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

def main():

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

N, Q = map(int, input().split())
ab = [map(int, input().split()) for _ in range(N - 1)]
px = [map(int, input().split()) for _ in range(Q)]

# build tree
tree = defaultdict(list)
for a, b in ab:
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)

# 同じノードがきたらまとめておく
# (複数回DFSしない)
dic = defaultdict(int)
for p, x in px:
    dic[p - 1] += x

ans = [0] * N
checked = [False] * N
q = deque([0])

while q:
    n = q.pop()
    checked[n] = True
    ans[n] += dic[n]
    for u in tree[n]:
        if checked[u]:
            continue
        ans[u] += ans[n]
        q.append(u)
print(*ans)

Submission status: Accepted

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

N, Q = map(int, input().split())
ab = [map(int, input().split()) for _ in range(N - 1)]
px = [map(int, input().split()) for _ in range(Q)]

# build tree
tree = defaultdict(list)
for a, b in ab:
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)

dic = defaultdict(int)
for p, x in px:
    dic[p - 1] += x

ans = [0] * N
checked = [0] * N
checked[0] = 1
q = deque([0])

while q:
    n = q.popleft()
    ans[n] += dic[n]
    for u in tree[n]:
        if checked[u]:
            continue
        ans[u] += ans[n]
        checked[u] = 1
        q.append(u)
print(*ans)

Submission status: Accepted

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

n,q = map(int, input().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:n+n-2])
PX = iter(ABPX[n+n-2:])

tree = dict()
for a,b in zip(AB,AB):
  if a in tree: tree[a].add(b)
  else: tree[a] = {b}
  if b in tree: tree[b].add(a)
  else: tree[b] = {a}

opr = {i+1:0 for i in range(n)}
for p,x in zip(PX,PX):
  opr[p] += x

stack = [1]
parent = [0] * (n+1)
ans = [0]*n
while stack:
  x = stack.pop()
  ans[x-1] += opr[x]
  for y in tree[x]:
    if y == parent[x]: continue
    parent[y] = x
    stack.append(y)
    ans[y-1] += ans[x-1]

print(*ans)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc138/submissions/7003989
import sys

input = sys.stdin.readline

# 遅延評価で加えてあげるだけ

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

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

value = [0] * (N + 1)
for p, x in PX:
    value[p] += x
#print("value:", value)
q = [(1, 0)]
#print("***loop***")
while q:
    x, parent = q.pop()
#    print("x:", x, "parent:", parent)
    value[x] += value[parent]
#    print("value:",value)
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y, x))
#    print("q:",q)

print(*value[1:])

Submission status: Accepted

Solution code:
import math 
import bisect
import heapq
from operator import mul
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)
c = [0] * n

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

seen = [0] * n
seen[0] = 1
next = deque([0])


while next:
    v = next.popleft()
    cost = c[v]

    for nv in g[v]:

        if seen[nv]:
            continue
        seen[nv] = 1
        next.append(nv)
        c[nv] += cost

print(*c)

Submission status: Accepted

Solution code:
from collections import deque

N, Q = map(int, input().split())
AB = {i: set() for i in range(1, N+1)}
for i in range(N - 1):
    tmpA, tmpB = map(int, input().split())
    AB[tmpA].add(tmpB)
    AB[tmpB].add(tmpA)
P = [0] * Q
X = [0] * Q
V = [0] * (N + 1)
for i in range(Q):
    P, X = map(int, input().split())
    V[P] += X

check = [0]*(N + 1)
q = deque()
q.append(1)
check[1] = 1
while q != deque():
    node = q.pop()
    for i in AB[node]:
        if check[i] == 1:
            continue
        V[i] += V[node]
        check[i] = 1
        q.appendleft(i)
print(*V[1:])

Submission status: Accepted

Solution code:
from collections import deque
"""
def dfs(i):
    q = deque()
    q.append(i)
    p = i
    d[i] = 1
    while True:
        if len(q) == 0:
            print(" ".join(map(str, c)))
            return
        s = 0
        p = q[len(q) - 1]
        for j in G[p]:
            if d[j] == 0:
                c[j] += c[p]
                q.append(j)
                s = 1
                p = j
                d[j] = 1
                break
        if s == 0:
            q.pop()
"""
def bfs(i):
    q = deque()
    q.append(i)
    p = i
    d[i] = 1
    while True:
        if len(q) == 0:
            print(" ".join(map(str, c)))
            return
        p = q.popleft()
        for j in G[p]:
            if d[j] == 0:
                q.append(j)
                c[j] += c[p]
                d[j] = 1

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

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

Submission status: Accepted

Solution code:
from collections import deque
n, q = map(int, input().split())
d = [[] for i 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 i in range(q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
# print(d)
d2 = [True] * n
 
def bfs():
    que = deque([0])
    d2[0] = False
    while len(que) != 0:
        val = que.popleft()
 
        for i in range(len(d[val])):
            if d2[d[val][i]] == True:
                que.append(d[val][i])
                ans[d[val][i]] += ans[val]
                d2[d[val][i]] = False
    return ans
print(' '.join(map(str,bfs())))

Submission status: Accepted

Solution code:
from collections import deque
n, q = map(int, input().split())
d = [[] for i 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 i in range(q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
# print(d)
d2 = [True] * n

def bfs():
    que = deque([0])
    d2[0] = False
    while len(que) != 0:
        val = que.popleft()

        for i in range(len(d[val])):
            if d2[d[val][i]] == True:
                que.append(d[val][i])
                ans[d[val][i]] += ans[val]
                d2[d[val][i]] = False
    return ans
print(' '.join(map(str,bfs())))

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)



c=[0]*n

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

used=[0]*n
used[0]=1
next=deque([0])

while next:
    v=next.popleft()
    cost=c[v]
    for nv in g[v]:
        if used[nv]:
            continue
        used[nv]=1
        next.append(nv)
        c[nv]+=cost

print(*c)