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())
tree = [[]*N 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())
    p -= 1
    counter[p] += x
# print(tree)
# print(counter)
# 幅優先探索で値を葉の方へ伝えていく
q = deque([0])
visited = [False]*N
visited[0] = True
while len(q):
    v = q.pop()
    for e in tree[v]:
        if visited[e]:
            continue
        visited[e] = True
        counter[e] += counter[v]
        q.append(e)
print(" ".join(map(str, counter)))

Submission status: Accepted

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

def main():
    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)
        
    ans = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1 
        ans[p] += x
    visited = [False] * N
    Q = deque()
    Q.append(0)
    while Q:
        v = Q.popleft()
        visited[v] = True
        for d in edge[v]:
            if visited[d]:
                continue
            Q.append(d)
            ans[d] += ans[v]

    print(*ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
N,  Q = map(int ,input().split())

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

dp = [0]*N
used = [False]*N

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

q = [1]
used[0] = True

while q:
    x = q.pop()
    
    for i in d[x]:
        if used[i-1]==True:
            continue
        dp[i-1] += dp[x-1]
        used[i-1] = True
        q.append(i)

print(*dp)

Submission status: Accepted

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

n,q=map(int,input().split())
tree=[[] for i in range(n)]

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

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

from collections import deque
q=deque([0])
while q:
  i=deque.popleft(q)
  for leaf in tree[i]:
    q.append(leaf)
    ans[leaf]+=ans[i]
    tree[leaf].remove(i)

print(*ans)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

nmax=2*10**5+10
graph=[[] for _ in range(nmax)]
level=[-1]*nmax

def dfs(n,s,l):
  if len(graph[s])==0:
    return
  for e in graph[s]:
    if level[e]==-1:
      level[e]=level[s]+1
    if level[e]>level[s]:
      l[e]+=l[s]
      dfs(n,e,l)

def main():
  n,q=LI()
  for _ in range(n-1):
    a,b=LI()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
  l=[0]*n
  for _ in range(q):
    a,b=LI()
    l[a-1]+=b

  level[0]=0
  dfs(n,0,l)

  return ' '.join([str(x) for x in l])

# main()
print(main())

Submission status: Accepted

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

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 + 1)]
for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)
  
cost = [0] * (N + 1)
for p, x in PX:
  cost[p] += x
  
check = [0] * (N + 1)
stack = [1]
check[1] = 1

while stack:
  s = stack.pop()
  for g in graph[s]:
    if check[g] == 0:
      check[g] = 1
      cost[g] += cost[s]
      stack.append(g)
      
print(*cost[1:])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
N, Q = map(int, input().split())
to = [[] for _ in range(N)]
ans = [0 for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

ans = [-1] * n

def dfs(v):
    ans[v] = S[v]
    stack = [v]
    while stack:
        x = stack[-1]
        if len(G[x]) > 0:
            w = G[x].popleft()
            if ans[w] == -1:
                ans[w] = ans[x] + S[w]
                stack.append(w)
        else: stack.pop()

dfs(0)
print(*ans)

Submission status: Accepted

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

N,Q = map(int,readline().split())
AB = [list(map(int,readline().split())) for i in range(N-1)]

graph = [[] for _ in range(N+1)] #隣接リスト
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

#親のノードに子を入れてくdfs
stack = [1]
parent = [0]*(N+1)
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in graph[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)

query = [0]*(N+1)

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

#全ての親についての累積和を取る。
#この時、親方向に逆流しないように注意。
for x in order:
    a = query[x]
    for y in graph[x]:
        if y == parent[x]: #逆流防止弁
            continue
        query[y] += a

print(*query[1:])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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)

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

ret = [0] * n
q = deque(maxlen = n)
q.append((0, 0))
while len(q) > 0:
    f, c = q.popleft()
    ret[c] = count[c] + ret[f]
    for n in tree[c]:
        if n != f:
            q.append((c, n))

print(*ret)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

ret = [0 for _ in range(n)]
q = deque(maxlen=n)
q.append((0, 0))
while len(q) > 0:
    f, c = q.popleft()
    ret[c] = count[c] + ret[f]
    for n in tree[c]:
        if n != f:
            q.append((c, n))

print(*ret)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

ret = [0 for _ in range(n)]
q = deque(maxlen=n)
q.append((0, 0))
while len(q) > 0:
    f, c = q.popleft()
    ret[c] = count[c] + ret[f]
    for n in tree[c]:
        if n != f:
            q.append((c, n))

print(*ret)

Submission status: Accepted

Solution code:
# coding: utf-8 
# Your code here!
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000000)

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

l=[[i] for i in range(N)] 

#print(l) 
def dfs(num,point,visited): 
    visited[num]=1 
    point+=plus[num] 
    
    ans[num]=point 
    while l[num][-1]!=num: 
        temp=l[num].pop(-1) 
        if visited[temp]==0: 
            dfs(temp,point,visited) 
            
    return 0 

for _ in range(N-1): 
    a,b=map(int,input().split()) 
    l[a-1].append(b-1) 
    l[b-1].append(a-1) 
    
ans=[0]*N 
plus=[0]*N 

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

dfs(0,0,[0]*N) 

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
n,q = map(int,input().split())
to = [[] for _ in range(n)]
ans = [0]*n

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

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

stack = deque()
stack.append((0,0))
while len(stack) != 0:
    cn,pn = stack.pop()
    for nn in to[cn]:
        if nn == pn:
            continue
        ans[nn] += ans[cn]
        stack.append((nn,cn))

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
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)

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

stack = deque([0])
seen = [False]*n
while len(stack) > 0:
    parent = stack.pop()
    seen[parent] = True
    for child in graph[parent]:
        if seen[child]:
            continue
        ans[child] += ans[parent]
        stack.append(child)

print(*ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
read = sys.stdin.read

N, Q = map(int, readline().split())
graph = [[] for _ in range(N + 1)]
cnt = [0] * (N + 1)

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

px = map(int, read().split())
for p, x in zip(*[px] * 2):
    cnt[p] += x

stack = [1]
checked = [False] * (N + 1)
checked[1] = True
while stack:
    V = stack.pop()
    for i in graph[V]:
        if checked[i]:
            continue
        checked[i] = True
        stack.append(i)
        cnt[i] += cnt[V]

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

Submission status: Accepted

Solution code:

N, Q = map(int, input().split())
edges = [[] for i in range(N+1)]
ans = [None for i in range(N+1)]
points = [[] for i in range(N+1)]

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

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

def dfs(u):
  visited = set()
  stack = [(u, -1, 0)]

  while stack:
    u, parent, point = stack.pop()
    visited.add(u)

    for p in points[u]:
      point += p

    ans[u] = point

    for edge in edges[u]:
      if edge not in visited:
        stack.append((edge, u, point))

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
import time
import sys

input = sys.stdin.readline

# start = time.time()
n, q = map(int, input().strip().split())
edges = [list(map(int, input().strip().split())) for _ in range(n - 1)]
values = [list(map(int, input().strip().split())) for _ in range(q)]

# elapsed = time.time() - start
# print("elapsed_time:{0}".format(elapsed) + "[sec]")

edge_dict = defaultdict(list)
value_dict = defaultdict(int)
total_value_dict = defaultdict(int)
visited = [False] * n

for a, b in edges:
    edge_dict[a].append(b)
    edge_dict[b].append(a)

for p, x in values:
    value_dict[p] += x


qu = deque([1])
total_value_dict[1] = value_dict[1]
visited[0] = True

while len(qu) > 0:
    node = qu.popleft()
    next_nodes = [m for m in edge_dict[node] if not visited[m - 1]]
    for m in next_nodes:
        total_value_dict[m] = total_value_dict[node] + value_dict[m]
        visited[m - 1] = True
        qu.append(m)

print(' '.join([str(total_value_dict[i]) for i in range(1, n + 1)]))

Submission status: Accepted

Solution code:
from collections import deque

n,q = map(int,input().split())
cnt = [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())
  cnt[v]+=val    
  
q = deque()
q.append(1)
checked = [0]*(n+1) 
while q:
  v = q.pop()
  checked[v] = 1
  for vc in g[v]:
    if checked[vc] == 1:
      continue
    else:
      cnt[vc] += cnt[v]
      q.append(vc)
    
print(*cnt[1:])

Submission status: Accepted

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

n, q = map(int, input().split())
edges = list(tuple(map(int, input().split())) for _ in range(n-1))
adj = [[] for _ in range(n+1)]
cnt = [0] * n
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

def dfs(p, u):
    vis = [0] * n
    stk = [(p, u)]
    while stk:
        p, u = stk[-1]
        stk.pop()
        if vis[u-1]:
            continue
        for v in adj[u]:
            if v != p:
                cnt[v-1] += cnt[u-1]
                stk.append((u, v))

quries = list(tuple(map(int, input().split())) for _ in range(q))
for u, p in quries:
    cnt[u-1] += p
dfs(-1, 1)
print(*cnt)

Submission status: Accepted

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

n, q = map(int, input().split())
edges = list(tuple(map(int, input().split())) for _ in range(n-1))
adj = [[] for _ in range(n+1)]
cnt = [0] * n
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

def dfs(p, u):
    vis = [0] * n
    stk = [(p, u)]
    while stk:
        p, u = stk[-1]
        stk.pop()
        if vis[u-1]:
            continue
        for v in adj[u]:
            if v != p:
                cnt[v-1] += cnt[u-1]
                stk.append((u, v))

quries = list(tuple(map(int, input().split())) for _ in range(q))
for u, p in quries:
    cnt[u-1] += p
dfs(-1, 1)
print(*cnt)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
g=[[] for _ in range(n)]
ans = [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 = list(map(int,input().split()))
  ans[p-1] += x
f=[1]*n
t=[0]
while t:
  v=t.pop()
  f[v]=0
  for k in g[v]:
    if f[k]:
      ans[k]+=ans[v]
      t.append(k)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
N,Q = map(int,input().split(" "))
cnt = [0 for _ in range(N)]
edge = [set() for i in range(N)]
for i in range(N-1):
    a,b = map(lambda x: int(x)-1, input().split(" "))
    edge[a].add(b)
    edge[b].add(a)
    
for i in range(Q):
    p,x = map(int,input().split(" "))
    p -= 1
    cnt[p] += x
plug = [0 for _ in range(N)]
stack = deque([0])
while stack:
    v = stack.pop()
    plug[v] = 1

    for e in edge[v]:
        if plug[e] != 1 and e != v:
            cnt[e] += cnt[v]
            stack.append(e)

print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque
N, Q = map(int, input().split())
edges = [[] for i in range(N+1)]
counts = [0 for i in range(N+1)]

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

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

def dfs():
  colors = ["white"] * (N+1)
  stack = deque()
  stack.append(1)

  while stack:
    v = stack.pop()
    colors[v] = "black"

    for e in edges[v]:
      if colors[e] != "black" and e != v:
        counts[e] += counts[v]
        stack.append(e)

dfs()

print(*counts[1:])

Submission status: Accepted

Solution code:
from collections import deque
import sys

input = sys.stdin.readline
N, q = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N-1)]

graph = [[] for i in range(N+1)]
for i,j in AB:
    graph[i].append(j)
    graph[j].append(i)

c = [0] * (N+1)
for i in range(q):
    p1 , x1 = map(int, input().split())
    c[p1] += x1
    
r = [-1 for i in range(N+1)] 
Q = deque()
Q.append(1)
r[1] = 0

while Q:
    x = Q.pop()
    for to in graph[x]:
        if r[to] == -1:
            c[to] += c[x]
            r[to] = 0 
            Q.append(to)

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

Submission status: Accepted

Solution code:
from collections import deque

N, q = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N-1)]

graph = [[] for i in range(N+1)]
for i,j in AB:
    graph[i].append(j)
    graph[j].append(i)

c = [0] * (N+1)
for i in range(q):
    p1 , x1 = map(int, input().split())
    c[p1] += x1
    
r = [-1 for i in range(N+1)] 
Q = deque()
Q.append(1)
r[1] = 0

while Q:
    x = Q.pop()
    for to in graph[x]:
        if r[to] == -1:
            c[to] += c[x]
            r[to] = 0 
            Q.append(to)

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

Submission status: Accepted

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


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


stack = [[0, V[0]]]
while stack:
    n, v = stack.pop()
    ans[n] = v

    for to in T[n]:
        if ans[to] is not None:
            continue

        stack.append([to, v + V[to]])


print(*ans, sep=' ')

Submission status: Accepted

Solution code:
from collections import deque
N,Q = map(int,input().split())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
px = [0 for i in range(N)]
for i in range(Q):
    p,x = list(map(int,input().split()))
    px[p-1] += x
que = deque()
alr = set()
alr.add(0)
que.append(0)
while que:
    q = que.popleft()
    sumq = px[q]
    for i in ab[q]:
        if i in alr:
            continue
        else:
            que.append(i)
            alr.add(i)
            px[i] += sumq
print(*px)

Submission status: Accepted

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

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

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

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

point=[0 for _ in range(n)]
que=deque()
que.append(0)
used=set()
used.add(0)
point[0] += v_counter[0]

while(len(que)>0):
    ind=que.popleft()
    relate=link[ind]
    for i in relate:
        if(i in used):
            continue
        else:
            point[i] += point[ind] + v_counter[i]
            que.append(i)
            used.add(i)

print(*point)

Submission status: Accepted

Solution code:
import collections


def bfs(s_node):
    q = collections.deque()
    q.append(s_node)
    used = set()
    used.add(s_node)
    points[s_node] += X[s_node]

    while len(q) > 0:
        prv_node = q.popleft()
        for node in g[prv_node]:
            if node in used:
                continue
            else:
                points[node] += points[prv_node] + X[node]
                q.append(node)
                used.add(node)


N, Q = map(int, input().split())
g = {i: [] for i 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)

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

points = [0 for _ in range(N)]
bfs(0)
print(*points)

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 i in range(Q):
    p,x = map(int, input().split())
    count[p-1]+=x
q = deque([0])
flag = [False]*N
while q:
    v = q.pop()
    flag[v] = True
    for w in G[v]:
        if flag[w]:
            continue
        count[w]+=count[v]
        q.append(w)
print(*count)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
T=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    T[a].append(b)
    T[b].append(a)
tasu=[0]*(n+1)
for i in range(q):
    p,x=map(int,input().split())
    tasu[p]+=x
    
def bfs(a):
    ans=[-1]*(n+1)
    q=deque([a])
    ans[a]=tasu[a]
    while q:
        x=q.popleft()
        moto=ans[x]
        for w in T[x]:
            if ans[w]<0:
                ans[w]=moto+tasu[w]
                q.append(w)
    return ans
kotae = bfs(1)[1:]
print(*kotae, sep=' ')

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
T=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    T[a].append(b)
    T[b].append(a)
tasu=[0]*(n+1)
for i in range(q):
    p,x=map(int,input().split())
    tasu[p]+=x
    
def dfs(a):
    ans=[-1]*(n+1)
    stack=[a]
    ans[a]=tasu[a]
    while stack:
        x=stack.pop()
        moto=ans[x]
        for w in T[x]:
            if ans[w]<0:
                ans[w]=moto+tasu[w]
                stack.append(w)
    return ans
kotae = dfs(1)[1:]
print(*kotae, sep=' ')

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
n,q = map(int,input().split())
d = defaultdict(list)
dp = [0] * n
ep = [0] * n
for i in range(n-1):
    ta,tb = map(int,input().split())
    d[ta-1].append(tb-1)
    d[tb-1].append(ta-1)
for i in range(q):
    ta,tb = map(int,input().split())
    dp[ta-1] +=tb
ep[0]+=1
l = deque()
l.append(0)

while l:
    t = l.pop()
    ep[t] = 1
    for i in d[t]:
        if not ep[i]:
            dp[i] += dp[t]
            l.append(i)
print(*dp)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
n,q = map(int,input().split())
d = defaultdict(list)
dp = [0] * n
ep = [0] * n
for i in range(n-1):
    ta,tb = map(int,input().split())
    d[ta-1].append(tb-1)
    d[tb-1].append(ta-1)
for i in range(q):
    ta,tb = map(int,input().split())
    dp[ta-1] +=tb
ep[0]+=1
l = deque()
l.append(0)
used = [False] * n
while l:
    t = l.pop()
    used[t] = True
    for i in d[t]:
        if not used[i]:
            dp[i] += dp[t]
            l.append(i)
print(*dp)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,q = inpl()
g = [[]for i in range(n)]
c = [0 for i in range(n)]
seen = [False] * n
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
for i in range(q):
    a,b = inpl()
    c[a-1] += b
def dfs(node):
    for v in g[node]:
        if seen[v]:
            continue
        c[v] += c[node]
        seen[v] = True
        dfs(v) 
seen[0] = True
dfs(0)
for i in c:
    print(i)

Submission status: Accepted

Solution code:
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)

cost = [0 for _ in range(n)]
for _ in range(q):
    pos, point = map(int, input().split())
    cost[pos-1] += point

memo = set([0])
stack = [0]

while len(stack) > 0:
    cur_node = stack.pop()
    cur_cost = cost[cur_node]

    for node in tree[cur_node]:
        if node not in memo:
            memo.add(node)
            cost[node] += cur_cost
            stack.append(node)

print(*cost)

Submission status: Accepted

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

def main():
    V = [0]*(N+1)
    for p,x in PX:
        V[p] += x
    stack = [1]
    gone = [False]*(N+1)
    gone[1] = True
    while len(stack) > 0:
        node = stack.pop(-1)
        for e in E[node]:
            if not(gone[e]):
                stack.append(e)
                V[e] += V[node]
                gone[e] = True
    print(*V[1:],sep =" ")
    return 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
G = [[] for n in range(N)]
for n 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 k in range(K):
    p, x = map(int, input().split())
    C[p - 1] += x

# 親情報の作成
P = [-1]*N
Q = [0]
X = []
count = 0
while Q:
    v = Q.pop()
    X.append(v)
    if v != 0:
        C[v] += C[P[v]]
    for u in G[v]:
        if u == P[v]:
            continue
        P[u] = v
        Q.append(u)

C = [str(c) for c in C]
print(" ".join(C))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000)
N,Q = map(int,readline().split())
abpx = list(map(int,read().split()))
ab = iter(abpx[:N+N-2])
px = iter(abpx[N+N-2:])
dic = {}
dic2=[0]*(N+1)
dic3=[0]*N

for i in range(N):
    dic[i+1] = []
for a,b in zip(ab,ab):
    dic[a].append(b)
    dic[b].append(a)
for p,x in zip(px,px):
    dic2[p] += x
def rec(now_node,prevval):
    nowval = prevval + dic2[now_node]
    dic3[now_node-1] = nowval
    tg_list = dic[now_node][:]
    for elem in tg_list:
        dic[elem].remove(now_node)
        rec(elem,nowval)
rec(1,0)
res = [str(dic3[i-1]) for i in range(1,N+1)]
print(' '.join(res))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N,Q = map(int,input().split())
ab = [ tuple(map(int,input().split())) for i in range(N-1) ]
px = [ tuple(map(int,input().split())) for i in range(Q) ]
dic = {}
dic2=[0]*(N+1)
dic3=[0]*N

for i in range(N):
    dic[i+1] = []
for i in range(N-1):
    tmp1 = ab[i][0]
    tmp2 = ab[i][1]
    dic[tmp1].append(tmp2)
    dic[tmp2].append(tmp1)
ab=0
for i in range(Q):
    dic2[px[i][0]] += px[i][1]
px=0
def rec(now_node,prevval):
    nowval = prevval + dic2[now_node]
    dic3[now_node-1] = nowval
    tg_list = dic[now_node][:]
    for elem in tg_list:
        dic[elem].remove(now_node)
        rec(elem,nowval)
rec(1,0)
res = [str(dic3[i-1]) for i in range(1,N+1)]
print(' '.join(res))

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1)]
PX=[list(map(int,input().split())) for i in range(Q)]

eda=[[] for i in range(N+1)]

pt= [0 for i in range(N+1)]
for a,b in AB:
    eda[a].append(b)
    eda[b].append(a)
for p,x in PX:
    pt[p]+=x


stack=[[1,eda[1]]]
v=set()
v.add(1)
while stack:
    while stack[-1][1]:
        a=stack[-1][1].pop()
        if not a in v:
            v.add(a)
            pt[a]+=pt[stack[-1][0]]
            stack.append([a,eda[a]])
    stack.pop()
print(" ".join(list(map(str,pt[1:]))))

Submission status: Accepted

Solution code:
from collections import deque

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)

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

visited = set()
visited.add(0)

dq = deque()
dq.append(0)

while dq:
    x = dq.popleft()
    for j in Adj[x]:
        if j not in visited:
            visited.add(j)
            dq.append(j)
            Counter[j] += Counter[x]
ans = ''
for i in range(n-1):
    ans += str(Counter[i]) + ' '
ans += str(Counter[n-1])
print(ans)