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

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

cnt=[0]*(N+1)
for el in px:
    cnt[el[0]] += el[1]
#print(cnt)


lst=[[] for _ in range(N+1)]
for el in ab:
    lst[el[0]].append(el[1])
    lst[el[1]].append(el[0])
#print(lst)

seen = [False] * (N + 1)
def dfs(n):
    seen[n] = True
    for child in lst[n]:
        if seen[child] == False:
            cnt[child]+=cnt[n]
            dfs(child)

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

Submission status: Accepted

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

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

visit=[0]*N
pts=[0]*N
ans=['']*N

for _ in range(Q):
    p,x=list(map(int,input().split()))

    pts[p-1]+=x

stack=[[0,0]]

while len(stack)>0:
    u,p=stack.pop()
    visit[u]=1
    p=p+pts[u]
    ans[u]=str(p)

    for v in edge[u]:
        if visit[v]==1:
            continue

        stack.append([v,p])

print(' '.join(ans))

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    ans = [0]*n
    for _ in range(q):
        p, x = map(int, input().split())
        ans[p-1] += x
    
    not_yet = deque([0])
    already = [False]*n
    already[0] = True
    
    while not_yet:
        key = not_yet.popleft()
        for value in tree[key]:
            if already[value]:
                continue
            already[value] = True
            not_yet.append(value)
            ans[value] += ans[key]
    
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
def dfs(G,s,p):
    for nv in G[s]:
        if(nv==p):
            continue
        Count[nv]+=Count[s]
        dfs(G,nv,s)
    
N,Q=map(int,input().split())
Count=[0]*N
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
for i in range(Q):
    p,x=map(int,input().split())
    Count[p-1]+=x
dfs(G,0,-1)
print(*Count)

Submission status: Accepted

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

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

def update(v, p):
    for next in tree[v]:
        if next == p:
            continue
        counter[next] += counter[v]
        update(next, v)

tree = [[] for _ in range(N)]
counter = [0] * N

for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x
update(0, -1)
print(" ".join(map(str, counter)))

Submission status: Accepted

Solution code:
from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
rootflag=[0]*N
rootflag[0]=1
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
points=[list(map(int,input().split())) for _ in range(Q)]
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
score=[0]*N
ans=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input(
#print(dirtree)
for i in range(Q):
    score[points[i][0]-1]=score[points[i][0]-1]+points[i][1]
#print(score)
v=0
d=deque()
d.append(v)
ans[0]=score[0]
while len(d)!=0:
    v=d.popleft()
    for j in dirtree[v]:
        ans[j]=ans[v]+score[j]
        d.append(j)
    #input()
    #print(ans)
print(*ans,sep=" ")

Submission status: Accepted

Solution code:
from collections import deque

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

adj_list = [[] for _ in range(n + 1)]
val = [0] * (n + 1)
visited = [False] * (n + 1)

for i in range(n - 1):
    u, v = map(int, input().split())
    adj_list[u].append(v)
    adj_list[v].append(u)

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

dq = deque()
prev = -1
cur = 1
dq.append([cur, prev])

while len(dq) > 0:

    cur, prev = dq.popleft()
    if prev != -1:
        val[cur] += val[prev]
    visited[cur] = True

    for next in adj_list[cur]:
        if visited[next] is False:
            dq.append([next, cur])

print(*val[1:])

Submission status: Accepted

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

def dfs(G,v,p):
    for next in G[v]:
        if next == p:
            continue
        counter[next]+=counter[v]
        dfs(G,next,v)
    

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

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

#print(subtree)
for _ in range(Q):
    p,x = map(int, input().split())
    p-=1
    counter[p]+=x
dfs(G,0,-1)
counter = map(str,counter)
print(' '.join(counter))

Submission status: Accepted

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

for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    X[p] += x
# p親、n現在、s合計
def dfs(p, n):
    for i in V[n]:
        if i == p:
            continue
        X[i] += X[n] 
        dfs(n, i)
dfs(-1,0)
print(*X)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
 
n , q = map(int,input().split())
point = [0] * n
edge = [[] 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 _ in range(q):
    a , b = map(int,input().split())
    point[a-1] += b
 
def dfs(now, last=-1):
    for nxt in edge[now]:
        if nxt==last: continue
        point[nxt] += point[now]
        dfs(nxt, now)
dfs(0)
print(*point)

Submission status: Accepted

Solution code:
#26　AtCoder Beginner Contest 138 D - Ki
from collections import deque
n, q = map(int, input().split())
edge = [[] for _ in range(n)]
counter  = [0]*n
for _ in range(n-1):
    u, v = map(int, input().split())
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)
for _ in range(q):
    u, v = map(int, input().split())
    counter[u-1] += v
que = deque([0])
check = [0]*n
while que:
    k = que.pop()
    check[k] = 1
    for i in edge[k]:
        if check[i]: continue
        counter[i] += counter[k]
        que.append(i)
print(*counter)

Submission status: Accepted

Solution code:
from collections import deque


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

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

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

    counter = [-1] * n
    d = deque([(-1, 0, 0)])
    while len(d) > 0:
        p, i, v = d.pop()
        total = operations[i] + v
        for c in edges[i]:
            if c != p:
                d.append((i, c, total))
        counter[i] = total

    print(*counter)


main()

Submission status: Accepted

Solution code:
from _collections import deque

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

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

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

ans = [0]*N
q = deque()
q.append((0,-1))
while(len(q)>0):
    a,parent = q.popleft()
    ans[a] = ans[parent] + point[a]
    for i in K[a]:
        if i != parent:
            q.append((i,a))

for i in ans:
    print(i,end=" ")

Submission status: Accepted

Solution code:
def main():
    def dfs_rec(start,prev):
        ans[start] = cnt[start]
        if start!=0:
            ans[start] +=ans[prev]
        for node in tree[start]:
            if node != prev:
                dfs_rec(node,start)
        return
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline

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

    for i in range(n-1):
        a,b = map(int,input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    for i in range(q):
        p,x = map(int,input().split())
        cnt[p-1]+=x
    dfs_rec(0,0)
    print(*ans)
if __name__=="__main__":
    main()

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)]
px = [list(map(int, readline().split())) for j in range(q)]
graph = [[] for _ in range(n + 1)]

for a, b in ab:
  graph[a].append(b)
  graph[b].append(a)
memo = [0] * (n + 1)
for p, x in px:
  memo[p] += x
stack = [(1, 0)]

while stack:
  x, parent = stack.pop()
  memo[x] += memo[parent]
  for y in graph[x]:
    if y == parent:
      continue
    stack.append((y, x))
print(*memo[1:])

Submission status: Accepted

Solution code:
import sys
from collections import OrderedDict

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


class Graph():
    def __init__(self):
        self.adjacency_dict = {}
        self.counter_dict = OrderedDict()

    def add_vertex(self, v):
        self.adjacency_dict[v] = set()
        self.counter_dict[v] = 0

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].add(v2)
        self.adjacency_dict[v2].add(v1)

    def add_count(self, v, count):
        self.counter_dict[v] += count

    def dfs_stack(self, start):
        stack = [start]
        visited = set()

        parent_vertex = 0
        while stack:
            current_vertex = stack.pop()
            visited.add(current_vertex)
            for v in self.adjacency_dict[current_vertex]:
                if v not in visited and v != parent_vertex:
                    self.counter_dict[v] += self.counter_dict[current_vertex]
                    stack.append(v)
            parent_vertex = current_vertex

    def dfs_rec(self, v, pv):
        for nv in self.adjacency_dict[v]:
            if nv != pv:
                self.counter_dict[nv] += self.counter_dict[v]
                self.dfs_rec(nv, v)

    def print_counters(self):
        print(*self.counter_dict.values())


def main():
    n, q = map(int, input().split())
    tree = Graph()
    for v in range(1, n+1):
        tree.add_vertex(v)
    for _ in range(n-1):
        a, b = map(int, input().split())
        tree.add_edge(a, b)
    for _ in range(q):
        p, x = map(int, input().split())
        tree.add_count(p, x)
    tree.dfs_stack(1)
    # tree.dfs_rec(1, 0)
    tree.print_counters()


if __name__ == "__main__":
    main()

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(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])
    
dfs(1,0,0)
    
answer = ' '.join(map(str,value[1:]))
print(answer)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N, Q = map(int, readline().split())
T = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, readline().split())
    T[a - 1].add(b - 1)
    T[b - 1].add(a - 1)

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

done = set()
for s in range(N):
    if s in done:
        continue
    todo = [s]
    while todo:
        c = todo.pop()
        for n in T[c]:
            if not n in done:
                todo.append(n)
                ans[n] += ans[c]
        done.add(c)

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

Submission status: Accepted

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

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)

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

def dfs(v, pv):
  for nv in tree[v]:
    if nv != pv:
      points[nv] += points[v]
      dfs(nv, v)

dfs(0, 0)
print(*points)

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)]
px = [list(map(int, readline().split())) for j in range(q)]
graph = [[] for _ in range(n + 1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)
memo = [0] * (n + 1)
for p, x in px:
    memo[p] += x
stack = [(1, 0)]
while stack:
    x, parent = stack.pop()
    memo[x] += memo[parent]
    for y in graph[x]:
        if y == parent:
            continue
        stack.append((y, x))
print(*memo[1:])

Submission status: Accepted

Solution code:
def submit():
  from collections import deque
  import sys
  input = sys.stdin.readline
  n,q = map(int,input().split())
  y = [[] for _ in range(n)]
  c = [0]*n
  for _ in range(n-1):
    ai,bi = map(int,input().split())
    y[ai-1].append(bi-1)
    y[bi-1].append(ai-1)
  for _ in range(q):
    pi,xi = map(int,input().split())
    c[pi-1] += xi
  z = deque([0])
  while z:
    zp = z.popleft()
    j = zp//10**6
    b = zp%(10**6)
    for yj in y[j]:
      if yj != b:
        z.append(yj*10**6+j)
        c[yj] += c[j]
  for i in range(n):
    print(c[i],end=" ")
submit()

Submission status: Accepted

Solution code:
def submit():
  from collections import deque
  import sys
  input = sys.stdin.readline
  n,q = map(int,input().split())
  y = [[] for _ in range(n)]
  c = [0]*n
  for _ in range(n-1):
    ai,bi = map(int,input().split())
    y[ai-1].append(bi-1)
    y[bi-1].append(ai-1)
  for _ in range(q):
    pi,xi = map(int,input().split())
    c[pi-1] += xi
  z = deque([[0,-1]])
  while z:
    j,b = z.popleft()
    for yj in y[j]:
      if yj != b:
        z.append([yj,j])
        c[yj] += c[j]
  for i in range(n):
    print(c[i],end=" ")
submit()

Submission status: Accepted

Solution code:
from collections import deque
def submit():
  n,q = map(int,input().split())
  y = [[] for _ in range(n)]
  c = [0]*n
  for _ in range(n-1):
    ai,bi = map(int,input().split())
    y[ai-1].append(bi-1)
    y[bi-1].append(ai-1)
  for _ in range(q):
    pi,xi = map(int,input().split())
    c[pi-1] += xi
  z = deque([[0,-1]])
  while z:
    j,b = z.popleft()
    for yj in y[j]:
      if yj != b:
        z.append([yj,j])
        c[yj] += c[j]
  for i in range(n):
    print(c[i],end=" ")
submit()

Submission status: Accepted

Solution code:
from collections import deque
n,Q=map(int,input().split())
tr=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    tr[a-1].append(b-1)
    tr[b-1].append(a-1)
counter=[0]*n
for _ in range(Q):
    p,x=map(int,input().split())
    counter[p-1]+=x
al=[0]*n
qi=deque([0])
while qi:
    x=qi.pop()
    al[x]=1
    for i in tr[x]:
        if al[i]==0:
            counter[i]+=counter[x]
            qi.append(i)
print(*counter)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from fractions import gcd                    # for Python3.4.3


def main():
    mod = 10000007                  # 10^9+7
    inf = float('inf')
    input = sys.stdin.readline      # 改行文字が残ることに注意
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def ii():  return int(input())
    def mi():  return map(int, input().rstrip().split())
    def lmi(): return list(map(int, input().rstrip().split()))
    def li():  return list(input().rstrip())


    def dfs_traverse(start, ans_lst, val=0):
        val += counter[start]
        ans_lst[start] = val
        for v in adj[start]:
            if ans_lst[v] is None:
                dfs_traverse(v, ans_lst, val)
    
    
    n, q = mi()
    L = [list(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(n-1)]
    count_up_commands = [lmi() for _ in range(q)]

    adj = [[] for _ in range(n)]
    for link in L:
        adj[link[0]].append(link[1])
        adj[link[1]].append(link[0])
    
    counter = [0] * n
    for command in count_up_commands:
        ind = command[0] -1
        count = command[1]
        counter[ind] += count
    
    ans_lst = [None] * n
    dfs_traverse(0, ans_lst)
    for ans in ans_lst:
        print(ans, end=" ")
    print("")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())
tree = [[] for i in range(n)]
ans = [0]*n
for i in range(n-1):
    a,b = map(lambda x:int(x)-1,input().split())
    tree[a].append(b)
    tree[b].append(a)

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

d = deque([[0,0]])
c = [False]*n
c[0] = True
while d:
    x,s = d.pop()
    s += ans[x]
    ans[x] = s
    for e in tree[x]:
        if not c[e]:
            c[e] = True
            d.append([e,s])

print(*ans)

Submission status: Accepted

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

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def main():
    n, q = map(int, input().split())
    edges = [[] for _ in range(n+1)]

    for a, b in readlines(n-1):
        edges[a].append(b)
        edges[b].append(a)

    counter = [0] * (n+1)
    for q, x in readlines(q):
        counter[q] += x

    def dfs(u, prev):
        for v in edges[u]:
            if v == prev:
                continue
            counter[v] += counter[u]
            dfs(v, u)

    dfs(1, 0)

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

main()

Submission status: Accepted

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

N, Q = list(map(int, input().split()))
nodes = [[] for i in range(N)]
for i in range(N-1):
  r, e = list(map(int, input().split()))
  r, e = r - 1, e - 1
  nodes[r].append(e)
  nodes[e].append(r)
#print(nodes)

result = [0] * N
for i in range(Q):
  r, s = list(map(int, input().split()))
  result[r-1] += s

def dfs(r, prev=-1):
  for i in nodes[r]:
    if i == prev:
      continue
    result[i] += result[r]
    dfs(i, r)

if __name__ == "__main__":
  dfs(0)
  print(*result)

Submission status: Accepted

Solution code:
#人の（ほぼ同じなのにうまくいかないので）
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

def dfs(v, parent):
    for u in lines[v]:
        if u != parent:
            ans[u] += ans[v]
            dfs(u, v)

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

Submission status: Accepted

Solution code:
N, Q = [int(i) for i in input().split()]
G = [[] for _ in range(N)]
counter = [0] * N
res = [0] * N
visited = [0] * N

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

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

# def dfs(G, v, p):
#     visited[v] = 1
#     res[v] = res[p]+counter[v]
#     for nv in G[v]:
#         if visited[nv]: continue
#         dfs(G, nv, v)

stack = [0]
parent = [0]
while stack:
    v = stack.pop()
    p = parent.pop()
    visited[v] = 1
    res[v] = res[p]+counter[v]
    for nv in G[v]:
        if visited[nv]: continue
        stack.append(nv)
        parent.append(v)

# dfs(G, 0, 0)
print(*res)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
from collections import deque

def main():
    N, Q = iip(listed=False)

    ql = [0 for i in range(N)]
    ll = [[] for i in range(N)]

    for i in range(N-1):
        a, b = iip(True)
        ll[a-1].append(b-1)
        ll[b-1].append(a-1)

    for i in range(Q):
        p, x = iip(True)
        ql[p-1] += x

    que = deque([])
    que.append((0, None))

    result = [None for i in range(N)]
    while que:
        data = que.popleft()
        node = data[0]
        before_node = data[1]
        if before_node is None:
            before_num = 0
        else:
            before_num = result[before_node]

        result[node] = before_num + ql[node]

        for child in ll[node]:
            if child != before_node:
                que.append((child, node))


    print(" ".join([str(i) for i in result]))




#####################################################ライブラリ集ここから

def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        return r
    if side == "right":
        return l+1



def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
from collections import deque


def read():
    N, Q = list(map(int, input().strip().split()))
    G = [list() for i in range(N+1)]
    PX = list()
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[a].append(b)
        G[b].append(a)
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX


def bfs(parent, G, C, V):
    q = deque()
    q.append(1)
    while len(q) > 0:
        parent = q.pop()
        V[parent] = True
        for child in G[parent]:
            if not V[child]:
                C[child] += C[parent]
                q.append(child)
    

def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    V = [False for i in range(N+1)]
    for p, x in PX:
        C[p] += x
    bfs(1, G, C, V)
    return ' '.join(map(str, C[1:]))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

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):
    u, v = map(int, input().split())
    cnt[u] += v

q = deque()
q.append(1)
checked = [0] * (n + 1)

while q:
    v = q.pop()
    checked[v] = 1
    for u in g[v]:
        if checked[u] == 1:
            continue
        cnt[u] += cnt[v]
        q.append(u)
print(*cnt[1:])

Submission status: Accepted

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

class Tree:
    def __init__(self, ind):
        self.children = []
        self.counter = 0
        self.index = ind
        self.parent = -1


N, Q = map(int, input().strip().split(" "))
tree = [Tree(i) for i in range(N)]
ans = [0 for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().strip().split(" "))
    tree[a - 1].children.append(b - 1)
    tree[b - 1].children.append(a - 1)

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

# bfs
que = queue.Queue()
que.put(0)  # root is 0

while not que.empty():
    ind = que.get()
    ans[ind] = tree[ind].counter
    for child in tree[ind].children:
        if child == tree[ind].parent:
            continue
        tree[child].counter += tree[ind].counter
        tree[child].parent = ind
        que.put(child)

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

Submission status: Accepted

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

stk = deque()
stk.append((0,-1))
while stk:
    cur,prev = stk.pop()
    for nxt in ki[cur]:
        if nxt == prev: continue
        ans[nxt] += ans[cur]
        stk.append((nxt,cur))

print(*ans)

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 = map(int, input().split())
  AB[a-1].append(b-1)
  AB[b-1].append(a-1)

count = [0]*N

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

used = [0]*N
used[0] = 1
que = deque([0])

while que:
  i = que.popleft()
  for j in AB[i]:
    if used[j] != 0:
      continue
    used[j] = 1
    count[j] += count[i]
    que.append(j)

print(*count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

n , q = map(int,input().split())
point = [0] * n
edge = [[] 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 _ in range(q):
    a , b = map(int,input().split())
    point[a-1] += b

def dfs(now, last=-1):
    for nxt in edge[now]:
        if nxt==last: continue
        point[nxt] += point[now]
        dfs(nxt, now)
dfs(0)
print(*point)

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)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
ans=[0 for _ in range(n)]
def dfs(u,par):
    if par!=-1:
        ans[u]+=ans[par]
    for v in g[u]:
        if v==par:
            continue
        dfs(v,u)
for _ in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x
dfs(0,-1)
print(*ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N, K = map(int, input().split())
    G = [[] for _ 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

    V = [False]*N
    stack = [0]
    while stack:
        x = stack.pop()
        V[x] = True
        for y in G[x]:
            if V[y]:
                continue

            C[y] += C[x]
            stack.append(y)

    print(*C)