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**6)

def slove():
    n, q = map(int,input().split())
    tree = [ [] for _ in range(n) ]
    for _ in range(n-1):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)
    score = [0]*n
    for _ in range(q):
        a, b = map(int,input().split())
        score[a-1] += b
    dfs(0,-1,tree,score)
    #print(score)
    print(" ".join(str(_) for _ in score))



def dfs(me,parent,tree,score):
    for child in tree[me]:
        if child == parent:
            continue
        score[child] += score[me]
        dfs(child,me,tree,score)

if __name__ == "__main__":
    slove()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
tree = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a].append([a, b])
    tree[b].append([b, a])
val = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split())
    val[p] += x
ans = [-1] * (N + 1)
ans[1] = val[1]
bfs = deque(tree[1])
while bfs:
    p,n = bfs.popleft()
    if ans[n] == -1:
        ans[n] = val[n]+ans[p]
        for i in tree[n]:
            bfs.append(i)
print(' '.join(list(map(str,ans[1:]))))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
N, Q = map(int, input().split(' '))
input = sys.stdin.readline

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


def dfs(v, par):
    for i in tree[v]:
        if i == par:
            continue
        memo[i] += memo[v]
        dfs(i, v)


dfs(0, -1)

print(*memo)

Submission status: Accepted

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

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

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

memo = [0] * n

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

def dfs(v, par):
    for nv in g[v]:
        if nv == par:
            continue
        memo[nv] += memo[v]
        dfs(nv, v)

dfs(0, -1)

print(*memo)

Submission status: Accepted

Solution code:
from collections import deque
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)
check = [0]*(N+1)
point = [0]*(N+1)
for i in range(Q):
    p,x = map(int,input().split())
    point[p] += x
q = deque([])
q.append(1)

while len(q)>0:
    nn = q.popleft()
    check[nn] = 1
    for i in edge[nn]:
        if check[i] == 0:
            point[i] += point[nn] 
            q.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque

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

eds = {i+1:[] for i in range(N)}

st = set([1])
rlt = [0]*(N+1)

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

que = deque([1])

while len(que) > 0:
  p = que.popleft()
  for c in eds[p]:
    if c not in st:
      st.add(c)
      que.append(c)
      rlt[c] += rlt[p]

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

d = deque()
d.append(0)
visited = [False] * n
while d:
    node = d.pop()
    visited[node] = True
    for next_node in edge[node]:
        if not visited[next_node]:
            res[next_node] += res[node]
            d.append(next_node)

for c in res:
    print(c, end=' ')

Submission status: Accepted

Solution code:
from collections import deque

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

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

d = deque()
d.append(0)
visited = [False] * n
while d:
    node = d.popleft()
    visited[node] = True
    for next_node in edge[node]:
        if not visited[next_node]:
            res[next_node] += res[node]
            d.append(next_node)

for c in res:
    print(c, end=' ')

Submission status: Accepted

Solution code:
#上流からスコアが流れてくるイメージ
from sys import stdin
from collections import deque
input = stdin.readline


def bfs():
  d.append(0)
  trace[0] = 1
 
  while d:
    now = d.pop()
    for next in g[now]:
      if trace[next] == 0:
        trace[next] = 1
        score[next] += score[now]
        d.append(next)


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

trace = [0]*n#頂点の個数
score = [0]*n

for i in range(n-1):#各々の頂点から行ける頂点のリスト
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  g[a].append(b)
  g[b].append(a)

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

d = deque([])

bfs()
      
print(*score)

Submission status: Accepted

Solution code:
from collections import deque


def bfs():
  d.append(0)
  trace[0] = 1
 
  while d:
    now = d.pop()
    for next in g[now]:
      if trace[next] == 0:
        trace[next] = 1
        score[next] += score[now]
        d.append(next)


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

trace = [0]*n#頂点の個数
score = [0]*n

for i in range(n-1):#各々の頂点から行ける頂点のリスト
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  g[a].append(b)
  g[b].append(a)

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

d = deque([])

bfs()
      
print(*score)

Submission status: Accepted

Solution code:
from queue import deque


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

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

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

P = [-1] * N

root = 0
q = deque([root])
while q:
    x = q.popleft()
    for y in graph[x]:
        if y == P[x]:
            continue
        C[y] += C[x]
        q.append(y)
        P[y] = x

print(*C)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, Q, AB, PX):
    from collections import defaultdict
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    C = [0] * (N+1)
    for p, x in PX:
        C[p] += x

    s = [(1, -1)]
    while s:
        u, p = s.pop()
        for v in g[u]:
            if v == p:
                continue
            s.append((v, u))
            C[v] += C[u]
    return C[1:]







def main():
    N, Q = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    PX = [read_int_n() for _ in range(Q)]
    print(*slv(N, Q, AB, PX))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

for a, b in ab:
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)

for p, x in px:
    count[p - 1] += x

d = deque([])


def dfs(p):
    d.append(p)
    seen[p] = 1

    while d:
        p = d.pop()

        for np in tree[p]:
            if seen[np] == 0:
                seen[np] = 1
                count[np] += count[p]
                d.append(np)


dfs(0)

for c in count:
    print(c, end=" ")

print()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, Q = geta(int)
    g = [set() for _ in range(N + 1)]
    v = [-1 for _ in range(N + 1)]

    for _ in range(N - 1):
        a, b = geta(int)
        g[a].add(b)
        g[b].add(a)

    d = [0] * (N + 1)
    for _ in range(Q):
        p, x = geta(int)
        d[p] += x

    def dfs(i, c):
        c2 = c + d[i]
        v[i] = c2
        for j in g[i]:
            if v[j] < 0:
                dfs(j, c2)

    dfs(1, 0)

    print(*v[1:], sep=" ")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os
from collections import deque

# 検索用タグ、累積和、木、クエリ処理、遅延評価

relations = []


# 実装を行う関数
def resolve():
    global relations

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

    # 木のつながりを整理する
    relations = [[] for i in range(n + 1)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        relations[a].append(b)
        relations[b].append(a)

    # どの木がきたら、いくら値を加算するか、を保持する(同じ木を何度か加算することもある)
    # 最終的に、これと「木のつながり」を組み合わせて各枝の累積和を求める。
    counters = [0 for i in range(n + 1)]
    for i in range(q):
        p, x = map(int, input().split())
        counters[p] += x

    # queを作成
    que = deque()
    que.append([1, 1])  # 初期値：スタート地点

    # BFS開始
    while len(que) is not 0:

        a = que.pop()
        now = a[0]
        bef = a[1]

        if not now == bef == 1:
            counters[now] += counters[bef]

        # 再帰処理のためのループ
        for target in relations[now]:

            if target == bef:
                continue

            que.appendleft([target, now])

    print(*counters[1:])


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 3
1 2
2 3
2 4
2 10
1 100
3 1"""
        output = """100 110 111 110"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10"""
        output = """20 20 20 20 20 20"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

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

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

counter = [0] * (n + 1)

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

parents = [0] * (n + 1)

q = [1]
while q:
    y = q.pop()
    for x in graph[y]:
        if x == parents[y]:
            continue
        counter[x] += counter[y]
        q.append(x)
        parents[x] = y

print(*counter[1:])

Submission status: Accepted

Solution code:
import sys
import io
#sys.stdin = io.StringIO(input_string)
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
    
def resolve():
	from collections import deque
	
	n, q = map(int, input().split())
	adj = [[] for i in range(n+1)]
	for i in range(n-1):
		a, b = map(int, input().split())
		adj[a-1].append(b-1)
		adj[b-1].append(a-1)
	ans = [0 for i in range(n)]
	for i in range(q):
		p, x = map(int, input().split())
		p -= 1
		ans[p] += x
#	print(f"{adj=}\n{ans=}")

	def dfs(now, prv):
		for next in adj[now]:
#			print(f"{now=}, {next=}")
			if next == prv:
				continue
			ans[next] += ans[now]
			dfs(next, now)

	dfs(0, 0)
	print(*ans)

resolve()

Submission status: Accepted

Solution code:
# ABC138D - Ki
from collections import deque


def main():
    N, Q, *X = map(int, open(0).read().split())
    AB, PX = X[: 2 * (N - 1)], X[2 * (N - 1) :]

    tree, cnt = [[] for _ in range(N + 1)], [0] * (N + 1)
    for a, b in zip(*[iter(AB)] * 2):
        tree[a].append(b), tree[b].append(a)
    for p, x in zip(*[iter(PX)] * 2):
        cnt[p] += x

    queue = deque([1])
    is_searched = [False] * (N + 1)
    while queue:
        u = queue.popleft()
        cur_cnt = cnt[u]
        is_searched[u] = True
        for v in tree[u]:
            if is_searched[v]:
                continue
            cnt[v] += cur_cnt
            queue.append(v)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC138D - Ki
from collections import deque


def main():
    N, Q, *X = map(int, open(0).read().split())
    AB, PX = X[: 2 * (N - 1)], X[2 * (N - 1) :]

    tree, cnt = [[] for _ in range(N + 1)], [0] * (N + 1)
    for a, b in zip(*[iter(AB)] * 2):
        tree[a].append(b), tree[b].append(a)
    for p, x in zip(*[iter(PX)] * 2):
        cnt[p] += x

    queue = deque([1])
    is_searched = [False] * (N + 1)
    is_searched[1] = True
    while queue:
        u = queue.popleft()
        cur_cnt = cnt[u]
        is_searched[u] = True
        for v in tree[u]:
            if is_searched[v]:
                continue
            cnt[v] += cur_cnt
            queue.append(v)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

visited = [False for i in range(n)]
visited[0] = True

queue = deque()
queue.append(0)
while queue:
  x = queue.popleft()
  for i in ki[x]:
    if visited[i] == True:
      continue
    cnt[i] += cnt[x]
    queue.append(i)
    visited[i] = True
print (*cnt)

Submission status: Accepted

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

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

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

visited = [False for i in range(n)]
visited[0] = True

queue = deque()
queue.append(0)
r = [0 for i in range(n)]
r[0] = cnt[0]
while queue:
  x = queue.popleft()
  for i in ki[x]:
    if visited[i] == True:
      continue
    # cnt[i] += cnt[x]
    r[i] = cnt[i] + r[x]
    queue.append(i)
    visited[i] = True
print (*r)

Submission status: Accepted

Solution code:
from collections import deque

n,q = map(int,input().split())
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)

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


isVisited = [False] * n
dq = deque([0])
isVisited[0] = True
while len(dq) > 0:
    parent = dq.popleft()
    for j, son in enumerate(edge[parent]):
        if isVisited[son]:
            continue
        ans[son] += ans[parent]
        isVisited[son] = True
        dq.append(son)

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
parent = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    parent[a].append(b)
    parent[b].append(a)
import collections
check = [0] * n

ans = [0] * n

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

a = ''
qq = collections.deque([0])
check[0] = 1
while len(qq) > 0:
    now = qq.popleft()
    for j, son in enumerate(parent[now]):
        if check[son] == 1:
            continue
        ans[son] += ans[now]
        check[son] = 1
        qq.append(son)
for i in range(n):
    a += str(ans[i]) + ' '
print(a)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
route = [[] for _ in range(N)]
count = [0 for i in range(N)]
for i in range(N - 1):
    a, b = map(int,input().split())
    route[a - 1].append(b - 1)
    route[b - 1].append(a - 1)
for i in range(Q):
    p, x = map(int, input().split())
    count[p - 1] += x
check = [(0,-1)]#(now, From)
while check:
    for _ in range(len(check)):
        now, From = check.pop()
        for next in route[now]:
            if next == From:
                continue
            else:
                count[next] += count[now]
                check.append((next, now))
print(' '.join(list(map(str, count))))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, Q = map(int, readline().split())
G = [[] for _ in range(N+1)]
score = [0]*(N+1)
for i in range(N-1):
  x,y = map(int, readline().split())
  G[x].append(y)
  G[y].append(x)

for _ in range(Q):
  a,p = map(int, readline().split())
  score[a] += p
  
def dfs(a,b):
  score[a] += score[b]
  for x in G[a]:
    if x == b:
      continue
    dfs(x,a)
    
dfs(1,0)
print(*score[1:])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
root = [[] for _ in range(N + 10)]
counter = [0 for _ in range(N + 10)]
for _ in range(N - 1):
  a, b = map(int, input().split())
  root[a].append(b)
  root[b].append(a)
for _ in range(Q):
  p, x = map(int, input().split())
  counter[p] += x
from collections import deque
d = deque([1])
while d:
  vertex = d.pop()
  for v in root[vertex]:
    counter[v] += counter[vertex]
    d.append(v)
    root[v].remove(vertex)
for i in range(1, N):
  print('{} '.format(counter[i]), end='')
print(counter[N])

Submission status: Accepted

Solution code:
# 深さ優先探索（行きがけ）
import sys
from collections import deque  # 両端の配列アクセスのときは高速、それ以外はlistのままのほうがいい


def main():
    N, Q = map(int, input().split())
    tree = [deque([]) for _ in range(N)]
    value = [0]*N
    flag = [0]*N

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

    stack = deque()
    stack.append(0)

    def dfs(v):
        now = v
        nowArray = tree[v]
        flag[v] = 1
        l = len(nowArray)

        for _ in range(l):  # 子ノードに値を追加
            w = tree[v].popleft()  # 子ノード
            if v not in tree[w]:
                continue
            value[w] += value[now]
            stack.append(w)

    while stack:
        top = stack.popleft()
        if flag[top] != 1:
            dfs(top)

    print(*value)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]

branch = [[] for _ in range(N)]
for i in range(N-1):
    branch[ab[i][0]-1].append(ab[i][1]-1)
    branch[ab[i][1]-1].append(ab[i][0]-1)

counters = [0 for _ in range(N)]
for i in range(Q):
    counters[px[i][0]-1] += px[i][1]
results = [0 for _ in range(N)]

seen = [False for _ in range(N)]
from collections import deque
seen[0] = True
todo = deque([0])
results[0] = counters[0]

while len(todo)>0:
    checking = todo.pop()
    candidates = branch[checking]
    for candidate in candidates:
        if seen[candidate] == False:
            todo.append(candidate)
            seen[candidate] = True
            results[candidate] = results[checking]+counters[candidate]


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

Submission status: Accepted

Solution code:
# ABC138D

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)

def dfs(adj,v,p,px,x,ct):
    x+=px[v]
    for nv in adj[v]:
        if nv==p:
            continue
        else:
            dfs(adj,nv,v,px,x,ct)
    ct[v]+=x

def main():
    N,Q=map(int,input().split())
    adj=[[] for i in range(N)]
    for i in range(N-1):
        a,b=map(int,input().split())
        adj[a-1]+=[b-1]
        adj[b-1]+=[a-1]
    px=[0]*N
    for i in range(Q):
        p,x=map(int,input().split())
        px[p-1]+=x
        
    ct=[0]*N
    dfs(adj,0,-1,px,0,ct)
    
    
    print(ct[0], end="")
    for i in range(1,N):
        print(" {}".format(ct[i]),end="")
    print("")
    
if __name__=="__main__":
    main()

Submission status: Accepted

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

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

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

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

q = queue.Queue()
q.put(0)
seen = [0] * n
ans = [0] * n

while True:
    if q.empty(): break
    v = q.get()
    seen[v] = 1
    ans[v] += counter[v]

    for next_v in graph[v]:
        if seen[next_v]: continue
        q.put(next_v)
        ans[next_v] += ans[v]

print(*ans)

Submission status: Accepted

Solution code:
# 早くなるおまじない
import sys
input = sys.stdin.buffer.readline

# 再帰関数の呼び出し制限
sys.setrecursionlimit(3 * 10 ** 5)

# 深さが一つ前のやつのresの値を足す
# dfsはおk，ここで累積和を使う発想が出てこなかった
# def dfs(node, prev):
#     visited.add(node)
#     if prev != 0:
#         res[node-1] += res[prev-1]
#     for i in dic[node]:
#         if i not in visited:
#             prev = node
#             dfs(i, prev)

def dfs(node, prev, visited, res, dic):
    visited.add(node)
    if prev != 0:
        res[node-1] += res[prev-1]
    for i in dic[node]:
        if i not in visited:
            prev = node
            dfs(i, prev, visited, res, dic)


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

    dic = {}
    for i in range(n-1):
        aa, bb = map(int,input().split())

        if aa not in dic:
            dic[aa] = set()
            dic[aa].add(bb)
        else:
            dic[aa].add(bb)

        if bb not in dic:
            dic[bb] = set()
            dic[bb].add(aa)
        else:
            dic[bb].add(aa)


    p = []
    x = []
    for _ in range(q):
        s, t = map(int,input().split())
        p.append(s)
        x.append(t)

    res = [0]*n
    for i in range(q):
        res[p[i]-1] += x[i]

    visited = set()

    dfs(1, 0, visited, res, dic)
    print(*res, sep=" ")

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main() -> None:
    def dfs(v, par, cnt):
        ans[v] += cnt
        for c in edges[v]:
            if c == par:
                continue
            dfs(c, v, ans[v])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main() -> None:
    def dfs(v, par, cnt):
        ans[v] = cnt + vs[v]
        for c in edges[v]:
            if c == par:
                continue
            dfs(c, v, ans[v])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def solve(N, children, weights):
    ret = [0 for _ in range(N + 1)]
    stack = deque()
    stack.append([0, 1])
    used = [False for _ in range(N + 1)]
    used[1] = True
    while stack:
        weights_sum, node = stack.pop()
        weights_sum += weights[node]
        ret[node] = weights_sum

        if not children[node]:
            continue

        for c in children[node]:
            if used[c]:
                continue
            stack.append([weights_sum, c])
            used[c] = True

    for idx in range(1, N + 1):
        print(ret[idx], end=" ")

if __name__ == "__main__":
    N, Q = map(int, input().split())
    children = [[] for _ in range(N + 1)]

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

    weights = [0 for _ in range(N + 1)]

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

    solve(N, children, weights)

Submission status: Accepted

Solution code:
from collections import deque

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

deq = deque()
pnt = [0] * n

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

visited = set()

deq.append(0)
visited.add(0)

while deq:
    ptr = deq.pop()
    for item in rg[ptr]:
        if item not in visited:
            visited.add(item)
            pnt[item] += pnt[ptr]
            deq.append(item)

print(' '.join(map(str, pnt)))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,q=map(int,input().split())
cnt=[0]*(n)
edges=[0]*n
for i in range(n):
    edges[i]=[]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)

from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

for i in edges[0]:
    dq.append((0,i))
while dq:
    f,t=dq.popleft()
    cnt[t]+=cnt[f]
    for to in edges[t]:
        if to!=f:dq.append((t,to))
    
print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque
n,q=list(map(int,input().split()))
graph=[[] for _ in range(n+1)]

for i in range(n-1):
  a,b=list(map(int,input().split()))
  graph[a].append(b)
  graph[b].append(a)
#print('graph:',graph)

cnt=[0] *(n+1)#q回繰り返して頂点とカウンターの値を整理
for _ in range(q):
    p,x =list(map(int, input().split()))
    cnt[p] += x
#print('cnt:',cnt)

ans = [-1] * (n+1)#ans作る
ans[1] = cnt[1]#ans初期化

que = deque()
que.append(1)#deque初期値

while que:
  v = que.popleft()
  for w in graph[v]:
    if ans[w] != -1:
      continue
    ans[w]=ans[v]+cnt[w]#ans[v]は一個上のnodeの値、cnt[w]は自分のカウンターの値
    que.append(w)
#    print('que:',que)
#    print('ans:',ans)
print(*ans[1:])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
res = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    res[p - 1] += x
s = [0]
d = [True] * n
while s:
    p = s.pop()
    d[p] = False
    for node in g[p]:
        if d[node]:
            res[node] += res[p]
            s.append(node)
print(' '.join(map(str, res)))