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())
adj = [[] for _ in range(N)]
count = [0] * N

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

queue = deque([0])
visit = [True] * N
visit[0] = False

while queue:
  now = queue.popleft()
  for u in adj[now]:
    if visit[u]:
      count[u] += count[now]
      queue.append(u)
      visit[u] = False
print(*count)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,Q=map(int, input().split())
    G=[[] for _ in range(N)]
    for _ in range(N-1):
        a,b=map(int, input().split())
        a,b=a-1,b-1
        G[a].append(b)
        G[b].append(a)
    C=[0]*N
    for _ in range(Q):
        p,x=map(int, input().split())
        C[p-1]+=x
    stk=[0]
    used=[False]*N
    used[0]=True
    while stk:
        v = stk.pop()
        for to in G[v]:
            if used[to]: continue
            used[to] = True
            C[to]+=C[v]
            stk.append(to)
    print(*C)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
ps = [0] * N
for p,x in PX:
    ps[p-1] += x

ans = [0] * N
ans[0] = ps[0]
stack = [0]
visited = [0] * N
visited[0] = 1
while stack:
    v = stack.pop()
    for to in es[v]:
        if visited[to]: continue
        visited[to] = 1
        ans[to] = ans[v] + ps[to]
        stack.append(to)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
def solve():
    n,q = map(int,input().split())
    l = [[] for _ in range(n)]
    fl = [True for _ in range(n)]
    dp = [0]*n
    for _ in range(n-1):
        a,b = map(int,input().split())
        l[a-1].append(b-1)
        l[b-1].append(a-1)
    for _ in range(q):
        p,x = map(int,input().split())
        p-=1
        dp[p]+=x
    d = deque()
    d.append(0)
    fl[0] = False
    while len(d):
        it = d.pop()
        for i in l[it]:
            if fl[i]:
                dp[i]+=dp[it]
                fl[i]=False
                d.append(i)
    for i in range(n):
        print(dp[i],end=' ')
    print()
if __name__=='__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)
    count = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        count[p-1] += x
    q = deque()
    for nextN in Edge[0]: q.append((nextN, 0))
    while q:
        nowN, parN = q.popleft()
        count[nowN] += count[parN]
        for nextN in Edge[nowN]:
            if nextN != parN: q.append((nextN, nowN))
    print(" ".join(map(str, count)))
    
    
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
ans=[0]*n
for _ in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x
Q=[0]
visited={0}
while Q:
  P=[]
  for i in Q:
    for j in edge[i]:
      if j in visited:continue
      visited.add(j)
      ans[j]+=ans[i]
      P.append(j)
  Q=P
print(*ans)

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

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

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

Submission status: Accepted

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

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

dist = [0] * (N + 1)
seen = [False] * (N + 1)
seen[1] = True
node = [1]

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

while node:
    s = node.pop()
    d = dist[s]
    for t in edge[s]:
        if seen[t]:
            continue
        dist[t] += d
        seen[t] = True
        node.append(t)

print(*dist[1:])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1E+7))

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

def dfs(i, parent, acc):
    V[i] += acc
    for j in link[i]:
        if j != parent:
            dfs(j,i,V[i])
cur = 1
parent = 0
acc = 0
dfs(cur, parent , acc)
V = [str(v) for v in V]
print (" ".join(V[1:]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1E+7))
def main():
    N, Q = map(int, input().split())
    link = [[] for _ in range(N+1)]
    for n in range(N-1):
        a, b = map(int, input().split())
        link[a].append(b)
        link[b].append(a)
    V = [0] * (N+1)
    ans = [0] * (N+1)
    for q in range(Q):
        p, x = map(int, input().split())
        V[p] += x

    def dfs(i, parent, acc):
        V[i] += acc
        for j in link[i]:
            if j != parent:
                dfs(j,i,V[i])
    cur = 1
    parent = 0
    acc = 0
    dfs(cur, parent , acc)
    V = [str(v) for v in V]
    print (" ".join(V[1:]))

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())
#link = [[0]*(N+1) for _ in range(N+1)]
link = [[] for _ in range(N+1)]
for n in range(N-1):
    a, b = map(int, input().split())
    # link[a][b] = 1
    # link[b][a] = 1
    link[a].append(b)
    link[b].append(a)
V = [0] * (N+1)
ans = [0] * (N+1)
for q in range(Q):
    p, x = map(int, input().split())
    V[p] += x

def dfs(i, parent, acc):
    V[i] += acc
    # for j in range(1,N+1):
    #     if link[i][j] == 1 and parent!=j:
    #         dfs(j,i,V[i])
    for j in link[i]:
        if j==parent:
            continue
        dfs(j,i,V[i])
cur = 1
parent = 0
acc = 0

dfs(cur, parent , acc)
V = [str(v) for v in V]
print (" ".join(V[1:]))

Submission status: Accepted

Solution code:
from collections import deque

n, k = list(map(int,input().split(' ')))
path = []
for i in range(n+1):
    path.append([])
for i in range(n-1):
    a, b = list(map(int,input().split(' ')))
    path[a].append(b)
    path[b].append(a)
val = [0] * (n+1)
for i in range(k):
    v, pt = list(map(int,input().split(' ')))
    val[v] += pt

used = {}
q = deque([1])
used[1] = True
while q:
    v = q.pop()
    for next_v in path[v]:
        if next_v not in used:
            used[next_v] = True
            val[next_v] += val[v]
            q.append(next_v)

print(' '.join([str(pt) for pt in val[1:]]))

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
edges = [[] for _ in range(n)]
counter = [0] * n
for a, b in [list(map(int, input().split())) for _ in range(n - 1)]:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
for p, x in [list(map(int, input().split())) for _ in range(q)]:
    counter[p - 1] += x

ret = [-1] * n
ret[0] = counter[0]
q = [0]
index = 0
while index < len(q):
    i = q[index]
    index += 1
    for j in edges[i]:
        if ret[j] < 0:
            q.append(j)
            ret[j] = counter[j] + ret[i]

print(' '.join(str(c) for c in ret))

Submission status: Accepted

Solution code:
from collections import deque

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

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

queue = deque([0])
visited = [0]*N
while queue:
    v = queue.pop()
    if(visited[v]):
        continue
    visited[v] = 1
    for value in graph[v]:
        if(visited[value]):
            continue
        nums[value] += nums[v]
        queue.append(value)
print(*nums)

Submission status: Accepted

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

# 親の頂点和を遷移させていく感じ

from collections import deque

N, Q = [int(s) for s in input().split()]
edge = [[int(s) - 1 for s in input().split()] for _ in range(N-1)]

v_value = [0]*N

for _ in range(Q):
    p, x = [int(s) for s in input().split()]
    v_value[p - 1] += x
    
tree = [[] for _ in range(N)]

for i, j in edge:
    tree[i].append(j)
    tree[j].append(i)

## bfs
dq = deque([0])
visited = [False]*N

while dq:
    v_parent = dq.pop()
    for v_child in tree[v_parent]:
        if not visited[v_child]:
            dq.appendleft(v_child)
            v_value[v_child] += v_value[v_parent]
    visited[v_parent] = True

for v in v_value:
    print(v, end=' ')

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)
print(*value[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n,q=map(int,input().split())
es=[[] for i in range(n)]
for i in range(n-1):
   a,b=map(int,input().split())
   es[a-1].append(b-1)
   es[b-1].append(a-1)
use=[1]*n
cnt=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x
def dfs(v,c):
    k=c+cnt[v]
    cnt[v]=k
    use[v]=0
    for i in es[v]:
        if use[i]:
            dfs(i,k)
dfs(0,0)
print(*cnt)

Submission status: Accepted

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

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

AB = [[int(x) for x in input().split()] for _ in range(n - 1)]
PX = [[int(x) for x in input().split()] for _ in range(q)]

graph = [[] for _ in range(n + 1)]
# 各ノードと連結するノードを要素に持つ配列
# e.g., graph[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

# 根から値を流す
q = [(1, 0)]
while q:
	x, parent = q.pop() # (1, 0)
	value[x] += value[parent]
	# 連結する成分について繰り返す
	# このとき、親のノードに流さないように注意
	# ここでの操作は、自分の子のノードを加えること
	for y in graph[x]:
		if y == parent:
			continue
		q.append((y, x)) #(親,子)

res = ' '.join(map(str, value[1:]))
print(res)

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  from collections import deque
  
  n,q=map(int,input().split())
  ab=[[] for _ in range(n+1)]
  for _ in range(n-1):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
  ans=[0]*(n+1)
  for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x
  
  l,parent=deque([1]),[0]*(n+1)
  parent[1]=1
  while l:
    x=l.popleft()
    for i in ab[x]:
      if parent[i]:
        continue
      l.append(i)
      ans[i]+=ans[x]
      parent[i]=1
      
  print(*ans[1:])
if __name__=='__main__':
  main()

Submission status: Accepted

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

neighbor = defaultdict(list)
counter = [0] * N

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

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

def propagate():
    stack = [(0, None)]
    while stack:
        node, parent = stack.pop()
        for c in neighbor[node]:
            if c != parent:
                counter[c] += counter[node]
                stack.append((c, node))

propagate()
print(*counter)

Submission status: Accepted

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

neighbor = defaultdict(list)
counter = [0] * N

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

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

def propagate():
    stack = [(0, None)]
    while stack:
        (node, parent) = stack.pop()
        for c in neighbor[node]:
            if c != parent:
                counter[c] += counter[node]
                stack.append((c, node))

propagate()
print(*counter)

Submission status: Accepted

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

neighbor = defaultdict(list)
counter = [0] * N

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

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

def propagate():
    stack = deque([(0, None)])
    while stack:
        (node, parent) = stack.pop()
        if parent is not None:
            counter[node] += counter[parent]
        for c in neighbor[node]:
            if c != parent:
                stack.append((c, node))

propagate()
print(*counter)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N

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

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

def solve():
    stack = [(0, None)]
    while stack:
        (node, parent) = stack.pop()
        if parent is not None:
            counter[node] += counter[parent]
        for c in neighbor[node]:
            if c != parent:
                stack.append((c, node))

solve()
print(*counter)

Submission status: Accepted

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

neighbor = defaultdict(list)
counter = [0] * N
pcounter = [None] * N
depth = {0: 0}

for i in range(N-1):
    a, b = map(int, input().split())
    a_deper, b_deeper = False, False
    if a in depth and b not in depth:
        depth[b] = depth[a] + 1
    if b in depth and a not in depth:
        depth[a] = depth[b] + 1
    if a in depth and b in depth:
        if depth[a] < depth[b]:
            neighbor[a-1].append(b-1)
        else:
            neighbor[b-1].append(a-1)
    else:
            neighbor[a-1].append(b-1)
            neighbor[b-1].append(a-1)

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

def solve():
    stack = [(0, None)]
    while stack:
        (node, parent) = stack.pop()
        pcounter[node] = counter[node]
        if parent is not None:
            pcounter[node] += pcounter[parent]
        for c in neighbor[node]:
            if pcounter[c] is None:
                stack.append((c, node))

solve()
print(*pcounter, sep=' ')

Submission status: Accepted

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

# 併せられるものは足し算して合わせる
# 直線形式に変更する
points = [0 for _ in range(N)]
for _ in range(Q):
    i, point = map(int, input().split())
    points[i - 1] += point
# print(bars)
# print(points)
# counters = [0 for _ in range(N)]
seen_points = [False for _ in range(N)]
queue = deque([0])
while queue:
    now_index = queue.pop()
    seen_points[now_index] = True
    for next_index in bars[now_index]:
        if not seen_points[next_index]:
            points[next_index] += points[now_index]
            queue.append(next_index)
# print(points)
print(*points)

Submission status: Accepted

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

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


N,Q = map(int,input().split())
K = [[] for _ in range(N+1)]
nums = [0 for _ in range(N+1)]

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

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

def dfs(now,parent):
    for i in K[now]:
        if i != parent:
            nums[i] += nums[now]
            dfs(i,now)

dfs(1,0)
print(*nums[1:])

Submission status: Accepted

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

def input():
    return sys.stdin.readline().strip()
def main():
    N,Q = map(int,input().split())
    K = [[] for _ in range(N+1)]
    nums = [0 for _ in range(N+1)]

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

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

    def dfs(now,parent):
        for i in K[now]:
            if i != parent:
                nums[i] += nums[now]
                dfs(i,now)

    dfs(1,0)
    print(*nums[1:])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n, q = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)

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

queue = deque([0])
visited = [0]*n
while queue:
    v = queue.pop()
    if visited[v]:
        continue
    visited[v] = 1
    for v2 in edges[v]:
        if visited[v2]:
            continue
        values[v2] += values[v]
        queue.append(v2)
print(*values)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)

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

stack = [0]
visited = [0]*n
while stack:
    v = stack.pop()
    if visited[v]:
        continue
    visited[v] = 1
    for v2 in edges[v]:
        if visited[v2]:
            continue
        values[v2] += values[v]
        stack.append(v2)
print(*values)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)

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

stack = [0]
visited = [0]*n
while stack:
    v = stack.pop()
    if visited[v]:
        continue
    visited[v] = 1
    for v2 in edges[v]:
        if visited[v2]:
            continue
        values[v2] += values[v]
        stack.append(v2)
print(*values)

Submission status: Accepted

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

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

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

def dfs(v, parent, add):
    nodes[v] += add
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v, nodes[v])

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

Submission status: Accepted

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

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

counter = [0 for _ in range(n)]
E = [[] for _ in range(n)]

#辺の定義
#辺E(u,v)の重みがw
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  E[b].append(a)
  E[a].append(b)

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

res = 0
#行ったかどうか
color = [-1 for _ in range(n)]

#dfsで色を塗っていく
stack = [0]
color[0] = counter[0]
while stack:
  u = stack.pop()
  for v in E[u]:
    if color[v] == -1:
      stack.append(v)
      color[v] = color[u] + counter[v]

ans = [str(color[i]) for i in range(n)]
print(" ".join(ans))

Submission status: Accepted

Solution code:
from collections import deque

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

#print(count)

q=deque() #queueとして(popleftとappend)
q.append(1)
parent=[-1]*(N+1)
#parent[1]=1

while q:
    now=q.popleft()
    for k in L[now]:
        if parent[now]==k:
            continue
        count[k]+=count[now]
        parent[k]=now
        q.append(k)
        #print(parent)

print(*count[1:])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d
#　木探索

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

from collections import deque

N, Q = MAP()
counter = [0]*N
tree = [[] for _ in range(N)]
parent = [-1]*N
for _ in range(N-1):
    a, b = MAP()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for _ in range(Q):
    p, x = MAP()
    counter[p-1] += x

q = deque()
q.append(0)

while q:
    index = q.pop()
    pindex = parent[index]
    for i in tree[index]:
        if i == pindex:
            continue
        counter[i] += counter[index]
        parent[i] = index
        q.append(i)

print(*counter)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N, Q = map(int, input().split())

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

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

    def dfs(now, parent):
        for i in edges[now]:
            if i != parent:
                nums[i] += nums[now]
                dfs(i, now)

    dfs(1, 0)
    for n in nums[1:]:
        print(n)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

q  = deque()
q.append(0)

while q:
  index = q.pop()
  pindex = parent[index]
  for i in tree[index]:
    if i == pindex: continue
    counter[i] += counter[index]
    parent[i] = index
    q.append(i)
    
print(*counter)

Submission status: Accepted

Solution code:
from collections import deque
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
counter = [0]*N
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())
    counter[p-1] += x
# print(G)
# print(counter)
seen = [0]*N
todo = deque([0])
seen[0] = 1
while todo:
    v = todo.pop()
    cost = counter[v]
    for nv in G[v]:
        if seen[nv]:
            continue
        seen[nv] = 1
        counter[nv] += cost
        todo.append(nv)

print(*counter)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
counter = [0]*N
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())
    counter[p-1] += x
# print(G)
# print(counter)
seen = [0]*N
todo = [0]
seen[0] = 1
while todo:
    v = todo.pop()
    cost = counter[v]
    for nv in G[v]:
        if seen[nv]:
            continue
        seen[nv] = 1
        counter[nv] += cost
        todo.append(nv)

print(*counter)

Submission status: Accepted

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

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

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

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

def dfs(now, prev):
    # リストはglobal宣言の必要がない？
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            chk[next] += chk[now]
            dfs(next, now)

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

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## BFS
from collections import deque

def main():

    #入力受け取り
    N, Q = mi()
    x = li2(N-1)

    cnt = [0]*N
    for i in range(Q):
        p0, p1 = mi()
        cnt[p0-1] += p1

    #隣接リスト作成
    adj = [[] for i in range(N)]
    for i in range(N-1):
        adj[x[i][0]-1].append(x[i][1]-1)
        adj[x[i][1]-1].append(x[i][0]-1)

    que = deque()
    ans = [0]*N

    # BFS
    que.append((0, 0))
    num = 0
    while que!=deque():
        v = que.popleft()
        ans[v[1]] = ans[v[0]] + cnt[v[1]]
        for next in adj[v[1]]:
            if next != v[0]:
                que.append((v[1], next))

    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## BFS
from collections import deque

def main():

    #入力受け取り
    N, Q = mi()
    x = li2(N-1)

    cnt = [0]*N
    for i in range(Q):
        p0, p1 = mi()
        cnt[p0-1] += p1

    #隣接リスト作成
    adj = [[] for i in range(N)]
    for i in range(N-1):
        x[i][0] -= 1
        x[i][1] -= 1
        adj[x[i][0]].append(x[i][1])
        adj[x[i][1]].append(x[i][0])

    que = deque()
    ans = [0]*N

    # BFS
    que.append((0, 0))
    num = 0
    while que!=deque():
        v = que.popleft()
        ans[v[1]] = ans[v[0]] + cnt[v[1]]
        for next in adj[v[1]]:
            if next != v[0]:
                que.append((v[1], next))

    for k in ans:
        print(k, '', end='')

if __name__ == "__main__":
    main()