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)
edges = {}
p = {}
done_nodes = set()

def dfs(target_node, keisyo_point):
    global p
    done_nodes.add(target_node)
    p[target_node] += keisyo_point
    next_node = edges[target_node]
    if not next_node:
        return
    else:
        for next in next_node:
            #edges[next].pop(edges[next].index(target_node))
            #dfs(next, p[target_node])
            if next in done_nodes:
                pass
            else:
                dfs(next, p[target_node])

def main():
    global edges, p
    n, q = map(int, input().split())
    edges = {e: [] for e in range(1, n+1)}
    for _ in range(n - 1):
        a, b = tuple(map(int, input().split()))
        edges[a].append(b)
        edges[b].append(a)
    p = {e: 0 for e in range(1, n+1)}
    for _ in range(q):
        p1, x1 = map(int, input().split())
        p[p1] += x1

    dfs(1, 0)
    for i1 in range(1, n + 1):
        print(p[i1], end=' ')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
n, q = map(int, input().split())

edges = [[] for _ in range(n)]
for _ in range(n - 1):
    frm, to = map(int, input().split())
    # 0-index
    edges[frm - 1].append(to - 1)
    edges[to - 1].append(frm - 1)

scores = [0] * n
for _ in range(q):
    v, s = map(int, input().split())
    scores[v - 1] += s


def dfs(frm, cur):
    if cur > 0:
        scores[cur] += scores[frm]
    for to in edges[cur]:
        if frm != to:
            dfs(cur, to)


dfs(-1, 0)
print(" ".join([str(w) for w in scores]))

Submission status: Accepted

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

tree_list = [input().split() for _ in range(N-1)]

query_list = [input().split() for _ in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]

val_list = [0]*N
linked_node_list = [[] for _ in range(N)]

# 無向グラフのリンク関係を作成（上流への接続も含んでいる）
for a, b in tree_list:
  a, b = int(a)-1, int(b)-1
  linked_node_list[a].append(b) #子の追加
  linked_node_list[b].append(a) #子の追加
  
for index, val in query_list_int:
  val_list[index-1] += val

stack = [0] #ルートノードの値を入れたスタックを生成、巡回するターゲットを格納する
parent = [0] * (N+1) #訪問済みノードを記憶するスタックを格納する

#再帰関数を使うとメモリ制限に引っかかるので、whileで順次実行する
# スタックでLIFOを使う。LIFOになるので、一番若い者をみながら深さ優先探索にできる。
# 親ノードを覚えておいて弾くようにする
# 有向グラフで定義すれば親を弾く処理はいらない

while True:
  #ルートから順に巡回
  v=stack.pop()   # 後ろから要素を取り出す
  for child in linked_node_list[v]:
    if child != parent[v]:
      parent[child] = v # 訪問済みノードを格納
      stack.append(child) #このノードvの接続先ノードをスタックに格納
      val_list[child] += val_list[v] #累積和
  if not stack:
    #スタックがなくなれば巡回終了
    break

print(*val_list)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    import sys
    sys.setrecursionlimit(2*10**6)

    N, Q = map(int, sys.stdin.readline().split())

    tree = [[] for _ in range(N)]  # 木構造
    for _ in range(N-1):
        a, b = map(int, sys.stdin.readline().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)

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

    def dfs(a, p):
        """
        a:対象番号
        p:親番号
        """
        for b in tree[a]:
            if b == p: continue
            anss[b] += anss[a]
            dfs(b, a)

    dfs(0, -1)

    print(*anss)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(1000000)

"""解説
いもす法っぽいことする
[入力例]
4 3
1 2
2 3
2 4
2 10
1 100
3 1

[出力例]
"""
def solve():
    N, Q = map(int, sys.stdin.readline().split())
    to = [[] for _ in range(N)]  # 木

    for _ in range(N-1):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1  # 0始まりになるように
        to[a].append(b)  # 無向グラフになるように両方に加える
        to[b].append(a)  # 無向グラフになるように両方に加える

    #print(to)

    ans = [0 for _ in range(N)]
    for _ in range(Q):
        p, x = map(int, sys.stdin.readline().split())
        p = p-1  # 0始まりになるように
        ans[p] += x

    #print(ans)

    def dfs(v, p=-1):
        for u in to[v]:
            if u==p: continue
            ans[u] += ans[v]  # いもす法っぽい累積和をする
            dfs(u, v)

    dfs(0)

    print(*ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque
def main():
    _map, _input, _int = map, input, int
    n, q = _map(_int, _input().split())
    values = [0] * n
    links = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = _map(_int, _input().split())
        links[a - 1].append(b - 1)
        links[b - 1].append(a - 1)
    for _ in range(q):
        p, x = _map(_int, _input().split())
        values[p - 1] += x
    d = deque()
    d.append((0, -1))
    while len(d) != 0:
        i, p = d.popleft()
        for j in links[i]:
            if j == p:
                continue
            values[j] += values[i]
            d.append((j, i))
    print(*values)
main()

Submission status: Accepted

Solution code:
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,Q = LI()
ab = [LI() for _ in [None]*(N-1)]
px = [LI() for _ in [None]*(Q)]
ans = [0]*(N+1) #1_index
graph = [collections.deque() for _ in [None]*(N+1)] #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [0]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,Q = LI()
ab = [LI() for _ in [None]*(N-1)]
px = [LI() for _ in [None]*(Q)]
ans = [0]*(N+1) #1_index
graph = [deque() for _ in [None]*(N+1)] #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [0]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(50000000)

ans=[]
tree=[]

def do(root,next):
    global ans
    global tree
    if root >= 0:
        ans[next]+=ans[root]
    for a in tree[next]:
        if a==root:
            continue
        do(next,a)

def resolve():
    global ans
    global tree
    readline=sys.stdin.readline
    n,q=map(int, readline().rstrip().split())
    tree=[[] for i in range(n)]
    ans=[0]*n
    for i in range(n-1):
        a,b=map(int, readline().rstrip().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    for i in range(q):
        p,x=map(int, readline().rstrip().split())
        p-=1
        ans[p]+=x
    do(-1,0)
    print(" ".join(map(str,ans)))

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(50000000)

def do(root,next,tree,ans):
    if root >= 0:
        ans[next]+=ans[root]
    for a in tree[next]:
        if a==root:
            continue
        do(next,a,tree,ans)

def resolve():
    readline=sys.stdin.readline
    n,q=map(int, readline().rstrip().split())
    tree=[[] for i in range(n)]
    ans=[0]*n
    for i in range(n-1):
        a,b=map(int, readline().rstrip().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    for i in range(q):
        p,x=map(int, readline().rstrip().split())
        p-=1
        ans[p]+=x
    do(-1,0,tree,ans)
    print(" ".join(map(str,ans)))

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(50000000)

class check():
    def __init__(self):
        readline=sys.stdin.readline
        n,q=map(int, readline().rstrip().split())
        self.tree=[[] for i in range(n)]
        self.ans=[0]*n
        for i in range(n-1):
            a,b=map(int, readline().rstrip().split())
            a-=1
            b-=1
            self.tree[a].append(b)
            self.tree[b].append(a)
        for i in range(q):
            p,x=map(int, readline().rstrip().split())
            p-=1
            self.ans[p]+=x
    def do(self,root,next):
        if root >= 0:
            self.ans[next]+=self.ans[root]
        for a in self.tree[next]:
            if a==root:
                continue
            self.do(next,a)
    def answer(self):
        print(" ".join(map(str,self.ans)))

def resolve():
    readline=sys.stdin.readline

    dfs=check()
    dfs.do(-1,0)
    dfs.answer()

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(50000000)

class check():
    def __init__(self,n,q):
        readline=sys.stdin.readline
        self.tree=[[] for i in range(n)]
        self.ans=[0]*n
        for i in range(n-1):
            a,b=map(int, readline().rstrip().split())
            a-=1
            b-=1
            self.tree[a].append(b)
            self.tree[b].append(a)
        for i in range(q):
            p,x=map(int, readline().rstrip().split())
            p-=1
            self.ans[p]+=x
    def do(self,root,next):
        if root >= 0:
            self.ans[next]+=self.ans[root]
        for a in self.tree[next]:
            if a==root:
                continue
            self.do(next,a)
    def answer(self):
        print(" ".join(map(str,self.ans)))






def resolve():
    readline=sys.stdin.readline

    n,q=map(int, readline().rstrip().split())
    c=check(n,q)
    c.do(-1,0)
    c.answer()

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

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

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

def dfs(frm, cur):
    if cur > 0:
        cnt[cur] += cnt[frm]
    for to in edges[cur]:
        if frm != to:
            dfs(cur, to)

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

Submission status: Accepted

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


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

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

def dfs(v=0, pre=-1, x=0):
    cnt[v] += x
    for u in G[v]:
        if u == pre:
            continue
        dfs(u, v, cnt[v])
    return


dfs()
print(*cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import sys
sys.setrecursionlimit(10**7)
def main(n,ab,px):
  g=[[]for _ in range(n)]
  for a,b in ab:
    g[a-1].append(b-1)
    g[b-1].append(a-1)
  ans=[0 for _ in range(n)]
  for p,x in px:
    ans[p-1]+=x  
  def dfs(seen,i):
    seen[i]=1
    for li in g[i]:
      if seen[li]==0:
        ans[li]+=ans[i]
        dfs(seen,li)
  seen=[0 for _ in range(n)]
  dfs(seen,0)
  print(' '.join(list(map(str,ans))))

if __name__=='__main__':
  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)]
  main(n,ab,px)

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 = set()
def dfs(n):
    seen.add(n)
    for child in lst[n]:
        if child not in seen:
            cnt[child]+=cnt[n]
            dfs(child)
 
dfs(1)
#print(cnt)
print(' '.join(list(map(str, cnt[1:]))))

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,q = mi()
A = [[]for _ in range(n)]
for _ in range(n-1):
    a,b = mi()
    A[a-1].append(b-1)
    A[b-1].append(a-1)
P = [0]*(2*(10**5))
for _ in range(q):
    p,x = mi()
    P[p-1] += x

from collections import deque
que = deque()
dp = [0]*(n)
que.append((0,0))

while que:
    ima,mae = que.popleft()
    dp[ima] = P[ima] + dp[mae]
    for i in A[ima]:
        if i!= mae:
            que.append((i,ima)) 

print(*dp)

Submission status: Accepted

Solution code:
from collections import defaultdict


def sum_counter(N, adj_nodes, counter_roots, root=0):
    parents = [-1 for _ in range(N)]
    counter = [0 for _ in range(N)]
    frontier = [root]
    counter[root] += counter_roots[root]
    parents[root] = root
    while len(frontier) > 0:
        parent = frontier.pop()
        for child in adj_nodes[parent]:
            if parents[child] >= 0:
                continue
            frontier.append(child)
            parents[child] = parent
            counter[child] += counter[parent] + counter_roots[child]
    return counter


def main():
    N, Q = list(map(int, input().split(' ')))
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    counter_roots = [0 for _ in range(N)]
    for _ in range(Q):
        p, x = list(map(int, input().split(' ')))
        p -= 1
        counter_roots[p] += x
    c = sum_counter(N, adj_nodes, counter_roots)
    print(' '.join(map(str, c)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,Q = LI()
ab = [LI() for _ in [None]*(N-1)]
px = [LI() for _ in [None]*(Q)]
ans = [0]*(N+1) #1_index
graph = [collections.deque() for _ in [None]*(N+1)] #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [0]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Accepted

Solution code:
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = [0]*(N+1) #1_index
graph = [collections.deque() for _ in range(N+1)] #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [0]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Accepted

Solution code:
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = [0]*(N+1) #1_index
graph = [collections.deque() for _ in range(N+1)] #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [0]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Accepted

Solution code:
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = {i:0 for i in range(1,N+1)} #1_index
graph = {i:collections.deque() for i in range(1,N+1)} #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = {i:-1 for i in range(1,N+1)} #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*[a for a in ans.values()])

Submission status: Accepted

Solution code:
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = [0]*(N+1) #1_index
graph = {i:collections.deque() for i in range(1,N+1)} #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [-1]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Accepted

Solution code:
import collections,copy,sys
def LI(): return list(map(int,sys.stdin.readline().split()))
N,Q = LI()
ans = [0]*(N+1)
graph = [collections.deque() for _ in range(N+1)] #1_index
for _ in range(N-1):
    a,b = LI()
    graph[a].append(b)
    graph[b].append(a)
for _ in range(Q):
    p,x = LI()
    ans[p] += x
seen = [-1]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,Q=map(int,input().split())
ans=[0]*N
ki=[[] for _ in range(N)]
for i in range(N-1):
 a,b=map(int,input().split())
 ki[a-1].append(b-1)
 ki[b-1].append(a-1)
for i in range(Q):
 p,q=map(int,input().split())
 ans[p-1]+=q
# dfs
stack = [0]
visited = ["False"] * N
while stack:
 ne = stack.pop()
 if visited[ne] == "False":
  visited[ne] = "True"
  for j in ki[ne]:
   if visited[j] == "False":
    ans[j]+=ans[ne]
    stack.append(j)
print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,Q=map(int,input().split())
ans=[0]*N
ki=[[] for _ in range(N)]
for i in range(N-1):
 a,b=map(int,input().split())
 ki[a-1].append(b-1)
 ki[b-1].append(a-1)
for i in range(Q):
 p,q=map(int,input().split())
 ans[p-1]+=q
# dfs
stack = [0]
visited = ["False"] * N
while stack:
 ne = stack.pop()
 if visited[ne] == "False":
  visited[ne] = "True"
  for j in ki[ne]:
   if visited[j] == "False":
    ans[j]+=ans[ne]
    stack.append(j)
L=[str(a) for a in ans]
L=' '.join(L)
print(L)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
ans=[0]*N
ki=[[] for _ in range(N)]
for i in range(N-1):
 a,b=map(int,input().split())
 ki[a-1].append(b-1)
 ki[b-1].append(a-1)
for i in range(Q):
 p,q=map(int,input().split())
 ans[p-1]+=q
# dfs
stack = [0]
visited = ["False"] * N
while stack:
 ne = stack.pop()
 if visited[ne] == "False":
  visited[ne] = "True"
  for j in ki[ne]:
   if visited[j] == "False":
    ans[j]+=ans[ne]
    stack.append(j)
L=[str(a) for a in ans]
L=' '.join(L)
print(L)

Submission status: Accepted

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

from collections import deque

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


def dfs(s):
    check = [False] * (n + 1)
    stack = deque([s])
    while stack:
        now = stack.pop()
        check[now] = True
        for nxt in graph[now]:
            if check[nxt]:
                continue
            stack.appendleft(nxt)
            cnt[nxt] += cnt[now]


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

Submission status: Accepted

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

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

graph = [deque() 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

stack = [0]
seen = [0]*n
seen[0] = 1
while True:
    rute = stack[-1]
    if graph[rute]:
        leaf = graph[rute].popleft()
        if seen[leaf] == 0:
            seen[leaf] = 1
            counter[leaf] += counter[rute]
            stack.append(leaf)
    else:
        stack.pop()
    if not stack:
        break

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

Submission status: Accepted

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

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

for i in range(N-1):
    G[A[i][0]].append(A[i][1])
    G[A[i][1]].append(A[i][0])

from collections import deque

H = {}
for i in range(1,N+1):
    H[i] = 0

for i in range(Q):
    H[B[i][0]] += B[i][1]

#bfs

r = 0
P = [0]*(N+1)  #ポイント

D = [0]+[-1]*(N)
D[1] = 1
P[1] = H[1]
q = deque([1])

while q:
    n = q.pop()
    for d in G[n]:
        if D[d] != -1:
            continue
        else:
            D[d] = 1
            q.appendleft(d)
            P[d] = P[n] + H[d]
del P[0]

print(*P)

Submission status: Accepted

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

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

graph = [[] for _ in range(N+1)]
value = [0] * (N + 1)

for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

for que in process:
    value[que[0]] += que[1]

def dfs(s, parent, add):
    value[s] += add
    for x in graph[s]:
        if x == parent:
            continue
        dfs(x, s, value[s])

dfs(1, 0, 0)

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

print(ans)

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, b = a - 1, b - 1
    g[a].append(b)
    g[b].append(a)
point = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    point[p] += x
ans = [0] * N
# 探索
def dfs(pre, now):
    # ansを更新
    ans[now] = ans[pre] + point[now]
    # 隣接頂点を探索
    for nxt in g[now]:
        if nxt == pre:
            continue
        dfs(now, nxt)
dfs(0, 0)
print(*ans)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(1000000)


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


def main():
    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)

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

    scores = [0] * N

    def dfs(g, v, v_prev):
        scores[v] = points[v]
        if v_prev >= 0:
            scores[v] += scores[v_prev]

        for w in g[v]:
            if w == v_prev:
                continue
            dfs(g, w, v)

    dfs(g, 0, -1)

    print(*scores)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n, q = map(int, input().split())
cnt = [0] * n
tree = [[] for i 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)

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

def dfs(cur, par):
    for chi in tree[cur]:
        if chi == par:
            continue
        cnt[chi] += cnt[cur]
        dfs(chi, cur)
dfs(0, -1)
print(*cnt)

Submission status: Accepted

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

N,Q=map(int,input().split())
a=[0]*(N-1)
b=[0]*(N-1)
p=[0]*Q
x=[0]*Q
c=[[] for _ in range(N)]  #接続リスト
cnt=[0]*N  #カウンター値

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

def dfs(x,parent):
  if parent!=-1:
    cnt[x] += cnt[parent]
  for child in c[x]:
    if child!=parent:
      dfs(child,x)

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