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
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
aLst = [[int(i) for i in input().split()] for _ in range(N-1)]
pLst = [[int(i) for i in input().split()] for _ in range(Q)]
to = [[]for _ in range(N+1)]

for a,b in aLst:
    to[a].append(b)
    to[b].append(a)

ps = [0]*(N+1)
for a,b in pLst:
    ps[a] += b

def dfs(v, i):
    for j in to[v]:
        if j == i:
            continue
        ps[j] += ps[v]
        dfs(j,v)

dfs(1,0)
print(' '.join(map(str, ps[1:])))

Submission status: Accepted

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

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

tmpLst = [[] for _ in range(N+1)]
for i, j in aLst:
    tmpLst[i].append(j)
    tmpLst[j].append(i)

ansLst = [0] * (N + 1)
for i,j in pLst:
    ansLst[i] += j

def dfs(v, p):
    for i in tmpLst[v]:
        if i == p:
            continue
        ansLst[i] += ansLst[v]
        dfs(i, v)


dfs(1, 0)

ans = ' '.join(map(str, ansLst[1:]))
print(ans)

Submission status: Accepted

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

input = sys.stdin.readline

tree = [[] for _ in range(200001)]
res = [0]*200001

def dfs(p, pre):
    for child in tree[p]:
        if child == pre: continue
        res[child] += res[p]
        dfs(child, p)

def main():
    """ main """
    N, Q = map(int, input().split())
    for _ in range(N-1):
        a,b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    for _ in range(Q):
        p,x = map(int, input().split())
        res[p] += x
    dfs(1, 0)

    print(*res[1:N+1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

checked = [0]*N

import collections
search = collections.deque([0])
while search:
    t = search.pop()
    checked[t] = 1
    for node in Links[t]:
        if checked[node]==1:
            continue
        Ans[node] += Ans[t]
        checked[node] = 1
        search.append(node)
print(*Ans)

Submission status: Accepted

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

#木の作成
tree = [ [] for _ in range(N+1)]
for n in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

#カウンターの作成
counter = [ 0 for _ in range(N+1)]
for q in range(Q):
    p, x = map(int, input().split())
    counter[p] += x
    
mydeaue = deque()
mydeaue.append(1)

checklist = [0 for _ in range(N+1)]
while (mydeaue):
    i = mydeaue.pop()
    checklist[i] = 1
    for j in tree[i]:
        if checklist[j] == 1:
            continue
        counter[j] += counter[i]
        mydeaue.append(j)
    #print(i)
print(' '.join(map(str, counter[1:])))

Submission status: Accepted

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

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

# AB = [[int(x) for x in input().split()] for _ in range(N-1)]

# print(AB)

# 添字を1からにしたいのでN+1
graph = [[] for _ in range(N+1)]

# 各頂点に隣接する頂点
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# print(graph)
counter = [0] * (N+1)

# print(counter)

# PX = [[int(x) for x in input().split()] for _ in range(Q)]

# 各頂点に点数を足す
for _ in range(Q):
  p, x = map(int, input().split())
  counter[p] += x


def shori(pa,c,val):
  val += counter[c]
  counter[c] = val
  for i in graph[c]:
    if i == pa:
      continue
    shori(c,i,val)
  
shori(0,1,0)
  

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

Submission status: Accepted

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

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

stat = [True]*N
stat[0] =False
que =[]
for i in bond[0]:
    que.append([0,i])

for _ in range(N-1):
    ue,sita = que.pop()
    if stat[sita]:
        for i in bond[sita]:
            if stat[i]:
                que.append([sita,i])
        qlis[sita] += qlis[ue]
    stat[sita] = False
anstr = " ".join([str(i)for i in qlis])
print(anstr)

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
tree = [set() for i in range(n+1)]
for _ in range(n-1):
  a,b = map(int, input().split())
  tree[a].add(b)
  tree[b].add(a)
lazy = [0]*(n+1)
cnt = 0

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

que = [(1,0)]
while que:
  v,p = que.pop()
  for x in tree[v]:
    if x == p:
      continue
    lazy[x] += lazy[v]
    que.append((x,v))

print(" ".join(map(str,lazy[1:])))

Submission status: Accepted

Solution code:
"""
N, Q = map(int, input().split())
nodes = [0 for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    nodes[b] = a

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

for i in range(1, N+1):
    counter[i] += counter[nodes[i]]

print(' '.join(map(str, counter[1:])))
"""
from collections import deque
N, Q = map(int, input().split())
counter = [0 for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

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

que = deque()
que.append(1)
checked = [False for _ in range(N+1)]

while(que):
    v = que.pop()
    checked[v] = True
    for u in graph[v]:
        if checked[u]:
            continue
        counter[u] += counter[v]
        que.append(u)

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

Submission status: Accepted

Solution code:
from collections import deque
import sys

input = sys.stdin.readline

def main():
  n, m= map(int, input().split())

  links = [deque() for x in range(n + 1)]
  sums = [0 for x in range(n + 1)]
  adds = [0 for x in range(n + 1)]

  links[0].append(1)

  buf = [map(int, input().split()) for _ in range(n - 1)]

  for link in buf:
    a, b= link
    links[a].append(b)
    links[b].append(a)


  buf = [map(int, input().split()) for _ in range(m)]
  for px in buf:
    p, x = px
    adds[p] += x

  que = [0,[1]]
  checked = [0 for x in range(n+1)]

  que = deque([[-1, [0]]])

  while que:
    link = que.popleft()
    par = link[0]
    childs = link[1]

    for child in childs:
      if checked[child] != 1:
        sums[child] = sums[par] + adds[child]
        que.append([child, links[child]])
        checked[child] = 1


  print(*sums[1:])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

input = sys.stdin.readline

def main():
  n, m= map(int, input().split())

  links = [deque() for x in range(n + 1)]
  sums = [0 for x in range(n + 1)]
  adds = [0 for x in range(n + 1)]

  links[0].append(1)

  buf = [map(int, input().split()) for _ in range(n - 1)]

  for link in buf:
    a, b= link
    links[a].append(b)
    links[b].append(a)


  buf = [map(int, input().split()) for _ in range(m)]
  for px in buf:
    p, x = px
    adds[p] += x

  que = [0,[1]]
  checked = [0 for x in range(n+1)]

  que = deque([[-1, [0]]])

  while que:
    link = que.pop()
    par = link[0]
    childs = link[1]

    for child in childs:
      if checked[child] != 1:
        sums[child] = sums[par] + adds[child]
        que.append([child, links[child]])
        checked[child] = 1


  print(*sums[1:])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
  n, m= map(int, input().split())

  links = [[] for x in range(n + 1)]
  sums = [0 for x in range(n + 1)]
  adds = [0 for x in range(n + 1)]

  links[0].append(1)

  buf = [map(int, input().split()) for _ in range(n - 1)]

  for link in buf:
    a, b= link
    links[a].append(b)
    links[b].append(a)


  buf = [map(int, input().split()) for _ in range(m)]
  for px in buf:
    p, x = px
    adds[p] += x

  que = [0,[1]]
  checked = [0 for x in range(n+1)]

  que = [[-1, [0]]]

  while que:
    link = que.pop()
    par = link[0]
    childs = link[1]

    for child in childs:
      if checked[child] != 1:
        sums[child] = sums[par] + adds[child]
        que.append([child, links[child]])
        checked[child] = 1


  print(*sums[1:])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

links = [[] for x in range(n + 1)]
sums = [0 for x in range(n + 1)]
adds = [0 for x in range(n + 1)]

links[0].append(1)

buf = [map(int, input().split()) for _ in range(n - 1)]

for link in buf:
  a, b= link
  links[a].append(b)
  links[b].append(a)


buf = [map(int, input().split()) for _ in range(m)]
for px in buf:
  p, x = px
  adds[p] += x

que = [0,[1]]
checked = [0 for x in range(n+1)]

que = [[-1, [0]]]

while que:
  link = que.pop()
  par = link[0]
  childs = link[1]

  for child in childs:
    if checked[child] != 1:
      sums[child] = sums[par] + adds[child]
      que.append([child, links[child]])
      checked[child] = 1

  
print(*sums[1:])

Submission status: Accepted

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

links = [[] for x in range(n + 1)]
sums = [0 for x in range(n + 1)]
adds = [0 for x in range(n + 1)]

links[0].append(1)

buf = [map(int, input().split()) for _ in range(n - 1)]

for link in buf:
  a, b= link
  links[a].append(b)
  links[b].append(a)


buf = [map(int, input().split()) for _ in range(m)]
for px in buf:
  p, x = px
  adds[p] += x

que = [0,[1]]
checked = [0 for x in range(n+1)]

que = [[-1, [0]]]

while que:
  link = que.pop()
  par = link[0]
  childs = link[1]

  for child in childs:
    if checked[child] != 1:
      sums[child] = sums[par] + adds[child]
      que.append([child, links[child]])
      checked[child] = 1

  
print(*sums[1:])

Submission status: Accepted

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

links = [[] for x in range(n + 1)]
sums = [0 for x in range(n + 1)]
adds = [0 for x in range(n + 1)]

links[0].append(1)

buf = [map(int, input().split()) for _ in range(n - 1)]

for link in buf:
  a, b= link
  links[a].append(b)
  links[b].append(a)

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

que = [0,[1]]
checked = [0 for x in range(n+1)]

que = [[-1, [0]]]

while que:
  link = que.pop()
  par = link[0]
  childs = link[1]

  for child in childs:
    if checked[child] != 1:
      sums[child] = sums[par] + adds[child]
      que.append([child, links[child]])
      checked[child] = 1

  
print(*sums[1:])

Submission status: Accepted

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

links = [[] for x in range(n + 1)]
sums = [0 for x in range(n + 1)]
adds = [0 for x in range(n + 1)]

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

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

que = [0,[1]]
checked = [0 for x in range(n+1)]

que = [[-1, [0]]]

while que:
  link = que.pop()
  par = link[0]
  childs = link[1]

  for child in childs:
    if checked[child] != 1:
      sums[child] = sums[par] + adds[child]
      que.append([child, links[child]])
      checked[child] = 1

  
print(*sums[1:])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

links = [[] for x in range(n + 1)]
sums = [0 for x in range(n + 1)]
adds = [0 for x in range(n + 1)]

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

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

# print(links)
que = [0,[1]]
checked = [0 for x in range(n+1)]

que = [[-1, [0]]]

while que:
  link = que.pop()
  # print(link)
  par = link[0]
  childs = link[1]

  for child in childs:
    if checked[child] != 1:
      sums[child] = sums[par] + adds[child]
      que.append([child, links[child]])
      checked[child] = 1

  
print(*sums[1:])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
tree_list  = {i:[] for i in range(1,n+1)}
answer_list = [0]*n
for i in range(1,n):
    a,b = map(int,input().split())
    tree_list[a].append(b)
    tree_list[b].append(a)
for i in range(m):
    num1,num2 = map(int,input().split())
    answer_list[num1-1] +=  num2
oya = [0]*n
oya_list = [1]
while len(oya_list) != 0:
    oya_list2 = oya_list
    oya_list = []
    for i in oya_list2:
        oya[i-1]  = 1
        for num in tree_list[i]:
            if oya[num-1] == 0:
                answer_list[num-1] += answer_list[i-1]
                oya_list.append(num)
for i in answer_list:
    print(i)

Submission status: Accepted

Solution code:
#14:03(3)
n,q = map(int,input().split())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(lambda x: int(x)-1, input().split())
  peer[a].append(b)
  peer[b].append(a)
ans = [0 for _ in range(n)]
for _ in range(q):
  p,x = map(int,input().split())
  p -= 1
  ans[p] += x
ect = [0 for _ in range(n)]
ect[0] = 1
now = [0]
while now != []:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if ect[y] == 0:
        now.append(y)
        ans[y] += ans[x]
        ect[y] = 1
print(' '.join(list(map(str,ans))))

Submission status: Accepted

Solution code:
from collections import deque

def main():
  N, Q = map(int, input().split())
  visited = [False] * (N+1)
  graph = {i:deque() for i in range(N+1)}

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

  visited[1] = True

  c = [0] * (N+1)
  for i in range(Q):
    p, x = map(int, input().split())
    c[p] += x
    
  q = [1]
  while q:
    per = q.pop()
    for child in graph[per]:
      if not visited[child]:
        visited[child] = True
        c[child] += c[per]
        q.append(child)

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

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
  N, Q = map(int, input().split())
  visited = [False] * (N+1)
  graph = {i:deque() for i in range(N+1)}

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

  visited[1] = True

  c = [0] * (N+1)
  for i in range(Q):
    p, x = map(int, input().split())
    c[p] += x
    
  q = [1]
  while q:
    per = q.pop()
    for child in graph[per]:
      if not visited[child]:
        visited[child] = True
        c[child] += c[per]
        q.append(child)

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

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque

n, q = map(int, input().split())
G = [[] for yy in range(n)]
count = [0]*n
flag=[False]*n
stack = deque([0])

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

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

print(*count)

Submission status: Accepted

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

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

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

def dfs(v, parent):
    for i in graph[v]:
        if i==parent:
            continue
        counter[i] += counter[v]
        dfs(i, v)
        
dfs(0, -1)
print(*counter)

Submission status: Accepted

Solution code:
from collections import deque

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

a=[0]*n
for i in range(q):
    b,c=map(int,input().split())
    a[b-1]+=c
    
d=deque([0])
f=[0]*n
f[0]=1
while d:
    p=d.pop()
    f[p]=1
    for c in tr[p]:
        if f[c]==1:
            continue
        a[c]+=a[p]
        d.append(c)
print(*a)

Submission status: Accepted

Solution code:
#問題はガバだったけどおかげで良い練習になった
n,q = map(int,input().split())
peer = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(lambda x:int(x)-1,input().split())
  peer[a].append(b)
  peer[b].append(a)
mom = [0 for _ in range(n)]
mom[0] = 1
ans = [0 for _ in range(n)]
for j in range(q):
  p,x = map(int,input().split())
  p -= 1
  ans[p] += x
now = [0]
while now != []:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if mom[y] == 0:
        mom[y] = 1
        ans[y] += ans[x]
        now.append(y)
print(' '.join(list(map(str,ans))))

Submission status: Accepted

Solution code:
#親ー子の順に書かれてるか否かめっちゃ重要なのになあ
n,q = map(int,input().split())

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

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

now = [0]
ans = pq
now = [0]
mom = [0 for _ in range(n)]
mom[0] = 1
while now != []:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if mom[y] == 0:
        now.append(y)
        mom[y] = 1
        ans[y] += ans[x]

print(' '.join(list(map(str,ans))))

Submission status: Accepted

Solution code:
#D
       


#XXX=[int(x) for x in Input.split()]

n,q = (int(x) for x in input().split())
#n,q = XXX[0:2]

E = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = (int(x) for x in input().split())
    #a,b = XXX[i*2+2:i*2+4]
    #A.append(a)
    #B.append(b)
    E[a].append(b)
    E[b].append(a)

P = []
X = []
for i in range(q):
    p,x = (int(x) for x in input().split())
    #p,x = XXX[i*2+n*2:i*2+n*2+2]
    P.append(p)
    X.append(x)

c = [0]*(n+1)
for i in range(len(P)):
    c[P[i]]+=X[i]

#sc = [-1]*(n+1)
sc = [0]*(n+1)
checked = [False]*(n+1)
stac = [1]

#dig(1,-1,0)

while stac:
    th = stac.pop()
    sc[th] += c[th]
    checked[th] = True
    
    for i in E[th]:
        if checked[i] == False:
            sc[i] += sc[th]
            stac.append(i)

result = map(str, sc[1:])
print(" ".join(result))

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
 
tree = {i:[] for i in range(1, n + 1)}
for _ in range(1, n):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
 
cnt = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x
 
check = [0]*n
 
tmp = [1]
while len(tmp) != 0:
    tmp2 = tmp
    tmp = []
    for oya in tmp2:
        check[int(oya)-1] = 1
        for ko in tree[oya]:
            if check[ko-1] == 0:
                cnt[ko-1] += cnt[oya-1]
                tmp.append(ko)
 
 
print(" ".join(map(str, cnt)))

Submission status: Accepted

Solution code:
from collections import deque
import sys
def input():
   return sys.stdin.readline()[:-1]
  
n,q = map(int, input().split())
tree = [[int(i) for i in input().split()] for i in range(n-1)] 
px = [[int(i) for i in input().split()] for i in range(q)] 
A = [set() for i in range(n)]
B = [set() for i in range(n)]
C = [set() for i in range(n)]
flag = [False] * n

for i,a in enumerate(tree):
  A[a[1]-1].add(tree[i][0])
  B[a[0]-1].add(tree[i][1])

for i in range(n):
  C[i] = A[i] | B[i]

ans = [0] * n

for i in px:

  ans[i[0]-1] += i[1]
  
cr = deque()
cr.append(1)
flag[0] = True

while cr:
  c = cr.popleft()
  flag[c-1] = True
  for i in C[c-1]:
    if flag[i-1]:
      continue
    else:
      cr.append(i)
      ans[i-1] += ans[c-1]
print(*ans)

Submission status: Accepted

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

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

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

check = [0]*n

tmp = [1]
while len(tmp) != 0:
    tmp2 = tmp
    tmp = []
    for oya in tmp2:
        check[int(oya)-1] = 1
        for ko in tree[oya]:
            if check[ko-1] == 0:
                cnt[ko-1] += cnt[oya-1]
                tmp.append(ko)


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

Submission status: Accepted

Solution code:
# ki
from collections import deque

# input

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

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

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

score = [0]*(n+1)
visited = [False]*(n+1)

for q in lq:
    score[q[0]] += q[1]

que = deque()
que.append(1)

while que:
    node = que.popleft()
    if not visited[node]:
        visited[node] = True
        for next in edge[node]:
            if not visited[next]:
                score[next] += score[node]
                que.append(next)

print(" ".join([str(n) for n in score][1:]))

Submission status: Accepted

Solution code:
import collections

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

g = [[] for i in range(n+1)]

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

count = [0] * (n+1)
check = [0] * (n+1)

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

q = collections.deque()  
q.append(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())  # N個の頂点, Q回の操作

# 辺を受け取る
graph = [[] for _ in range(N)]

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

count = [0] * N
# その頂点に対して与えられるカウントは伝播する
for i in range(Q):  # Q個の操作について
    p, x = map(int, input().split())
    # ある頂点を根とする部分木には、今現在のcountが全て伝播していく
    count[p-1] += x

q = deque([0])  # 開始のノード
flag = [False] * N

while len(q):
    v = q.pop()
    flag[v] = True  # 部分木の根を到達済みにする

    for e in graph[v]:  # vを根にもつノード全てに操作をする
        # graphは子のみを格納するのではなく、そのノードから出ている辺を
        # 親とか子供とか関係なく全て格納してしまうため、親の方向に
        # 対して伝播をしないようにflagで管理する
        if flag[e]:  # 頂点eがvの親であればスルー
            continue
        # eはvの子供であることが確定する
        count[e] += count[v]  # 親の値を伝播させていく
        q.append(e)

print(*count)

Submission status: Accepted

Solution code:
while True:
    try:
        N, Q = map(int, input().split())
        verts = [None] * N
        qs = [0] * N
        results = [0] * N
        for i in range(N - 1):
            a, b = map(int, input().split())
            a -= 1
            b -= 1
            if verts[a] is None:
                verts[a] = list()
            if verts[b] is None:
                verts[b] = list()
            verts[a].append(b)
            verts[b].append(a)
        for i in range(Q):
            q, x = map(int, input().split())
            q -= 1
            qs[q] += x
        rests = [(0, None)]
        while rests:
            x, parent = rests.pop()
            if parent is not None:
                results[x] += results[parent]
            results[x] += qs[x]
            for i in verts[x]:
                if i != parent:
                    rests.append((i, x))
        print(" ".join(map(str, results)))
    except EOFError:
        break

Submission status: Accepted

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

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

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

q = [(0, -1)]
while q:
    me, parent = q.pop()
    for child in links[me]:
        if child == parent:
            continue
        values[child] += values[me]
        q.append((child, me))

print(*values)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, Q = map(int, input().split())
counts = [0] * N

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

        graph[a].append(b)
        graph[b].append(a)

    return graph

## graph は [[1], [0, 2, 3], [1], [1]]
## 例えば2 なら、1, 3, 4(0, 2, 3)が入ってる
graph = get_graph(N)
#print(graph)

# まず親にだけ足す
ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(current, parent):
    for child in graph[current]:
        if child == parent:
            continue

        ### 親には最初に足してあるので、子・孫だけ考えればいい
        # 子には親のが既に入ってる、孫は（親＋子）を足せばいい
        # 曾孫なら（親＋子＋孫）になってるやつを足せばいい
        ans[child] += ans[current]
        dfs(child, current)

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque


def main():

    setrecursionlimit(2000001)

    n, q = [int(x) for x in stdin.readline().split()]

    tree = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        a, b = [int(x) for x in stdin.readline().split()]
        tree[a].append(b)
        tree[b].append(a)

    count = [0] * (n + 1)
    for _ in range(q):
        parent, x = [int(x) for x in stdin.readline().split()]
        count[parent] += x

    queue = deque([])
    visited = [False] * (n + 1)

    queue.append((0, 1))

    while len(queue) > 0:
        parent, current = queue.pop()
        visited[current] = True
        count[current] += count[parent]
        for child in tree[current]:
            if not visited[child]:
                queue.append((current, child))

    print(*count[1:])


main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():

    setrecursionlimit(2000001)

    current, q = [int(x) for x in stdin.readline().split()]

    tree = [[] for _ in range(current + 1)]
    for _ in range(current - 1):
        a, b = [int(x) for x in stdin.readline().split()]
        tree[a].append(b)
        tree[b].append(a)

    cnt = [0] * (current + 1)
    for _ in range(q):
        parent, x = [int(x) for x in stdin.readline().split()]
        cnt[parent] += x

    stack = []
    visited = [False] * (current + 1)

    stack.append((0, 1))

    while len(stack) > 0:
        parent, current = stack.pop()
        visited[current] = True
        cnt[current] += cnt[parent]
        for child in tree[current]:
            if not visited[child]:
                stack.append((current, child))

    print(*cnt[1:])


main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque


def main():

    setrecursionlimit(2000001)

    n, q = [int(x) for x in stdin.readline().split()]

    tree = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        a, b = [int(x) for x in stdin.readline().split()]
        tree[a].append(b)
        tree[b].append(a)

    count = [0] * (n + 1)
    for _ in range(q):
        parent, x = [int(x) for x in stdin.readline().split()]
        count[parent] += x

    queue = deque([])
    visited = [False] * (n + 1)

    queue.append((0, 1))

    while len(queue) > 0:
        parent, current = queue.pop()
        visited[current] = True
        count[current] += count[parent]
        for child in tree[current]:
            if not visited[child]:
                queue.append((current, child))

    print(*count[1:])


main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque


def main():

    setrecursionlimit(2000001)

    n, q = [int(x) for x in stdin.readline().split()]

    tree = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        a, b = [int(x) for x in stdin.readline().split()]
        tree[a].append(b)
        tree[b].append(a)

    count = [0] * (n + 1)
    for _ in range(q):
        parent, x = [int(x) for x in stdin.readline().split()]
        count[parent] += x

    queue = deque([])
    visited = [False] * (n + 1)

    queue.append((0, 1))

    while len(queue) > 0:
        parent, current = queue.popleft()
        visited[current] = True
        count[current] += count[parent]
        for child in tree[current]:
            if not visited[child]:
                queue.append((current, child))

    print(*count[1:])


main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():

    setrecursionlimit(2000001)

    current, q = [int(x) for x in stdin.readline().split()]

    tree = [[] for _ in range(current + 1)]
    for _ in range(current - 1):
        a, b = [int(x) for x in stdin.readline().split()]
        tree[a].append(b)
        tree[b].append(a)

    cnt = [0] * (current + 1)
    for _ in range(q):
        parent, x = [int(x) for x in stdin.readline().split()]
        cnt[parent] += x

    stack = []
    visited = [False] * (current + 1)

    stack.append((0, 1))

    while len(stack) > 0:
        parent, current = stack.pop()
        visited[current] = True
        cnt[current] += cnt[parent]
        for child in tree[current]:
            if not visited[child]:
                stack.append((current, child))

    print(*cnt[1:])


main()