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 = lambda: sys.stdin.readline().rstrip()
#入力
n, q = map(int, input().split())
G = [[] for _ in range(n+1)]
for i in range(n-1):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

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

"""
#再帰
ans_dfs = [0 for _ in range(n)]
def dfs(now, parent, S):
    ans_dfs[now] = S + counter[now]
    for to in G[now]:
        if to == parent: continue
        dfs(to, now, ans_dfs[now])

"""
#非再帰
class p:
    num = -1
    parent = -1

    def __init__(self, x, y):
        self.num = x
        self.parent = y
#dfsでの探索順
node_list = []
ans = [0 for _ in range(n+1)]

def main():

    #dfs(1, -1, 0)
    #dfsでの探索順の作成
    stack = []
    stack.append(p(1, -1))
    while len(stack) != 0:
        now = stack.pop()
        node_list.append(now)
        for to in G[now.num]:
            if to == now.parent: continue
            stack.append(p(to, now.num))

    for now in node_list:
        ans[now.num] = counter[now.num] + ans[now.parent]

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



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#入力
n, q = map(int, input().split())
G = [[] for _ in range(n+1)]
for i in range(n-1):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

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

"""
#再帰
ans_dfs = [0 for _ in range(n)]
def dfs(now, parent, S):
    ans_dfs[now] = S + counter[now]
    for to in G[now]:
        if to == parent: continue
        dfs(to, now, ans_dfs[now])

"""
#非再帰
class p:
    num = -1
    parent = -1

    def __init__(self, x, y):
        self.num = x
        self.parent = y
#dfsでの探索順
node_list = []
ans = [0 for _ in range(n+1)]

def main():

    #dfs(1, -1, 0)
    #dfsでの探索順の作成
    stack = []
    stack.append(p(1, -1))
    while len(stack) != 0:
        now = stack.pop()
        node_list.append(now)
        for to in G[now.num]:
            if to == now.parent: continue
            stack.append(p(to, now.num))

    for now in node_list:
        ans[now.num] = counter[now.num] + ans[now.parent]

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



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
G = [[] for n 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
Q = [0]
while Q:
    x = Q.pop()
    V[x] = True
    for y in G[x]:
        if not V[y]:
            C[y] += C[x]
            Q.append(y)
print(*C)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    N, Q = input_nums()
    C = [0]*N
    G = [[] for i in range(N)]
    for i in range(N-1):
        a, b = input_nums()
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    for i in range(Q):
        p, x = input_nums()
        C[p-1] += x
    isVisit = [False]*N
    isVisit[0] = True
    stack = [0]

    while stack:
        now = stack.pop()
        for i in G[now]:
            if not isVisit[i]:
                isVisit[i] = True
                stack.append(i)
                C[i] += C[now]
    print(*C)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
count = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    count[p-1]+=x
q = deque([0])
flag = [False]*N
while q:
    v = q.pop()
    flag[v] = True
    for e in G[v]:
        if flag[e]:
            continue
        count[e]+=count[v]
        q.append(e)
print(*count)

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:
import sys

# import bisect

from collections import Counter, deque, defaultdict

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd

# import itertools

# from operator import attrgetter, itemgetter
# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)
# 普通のグラフ
from collections import defaultdict


class Graph:
    # 0-indexed

    def __init__(self, vertices=0):
        self.edges = defaultdict(list)
        self.counter = [0] * vertices
        self._vertex_count = vertices
        self._edges_count = 0

    @property
    def edges_count(self):
        return self._edges_count

    @property
    def vertices_count(self):
        return self._vertices_count

    def add_edge(self, u, v):
        self.edges[u].append(v)
        self.edges[v].append(u)
        self._edges_count += 1

    def add_counter(self, u, cnt):
        self.counter[u] += cnt

    def add_directed_edge(self, u, v):
        self.edges[u].append(v)
        self._edges_count += 1

    def del_edge(self, u, v):
        self.edges[u] = [_ for _ in self.edges[u] if _[0] != v]
        self.edges[v] = [_ for _ in self.edges[v] if _[0] != u]
        self._edges_count -= 1

    # 連結している節点を求める
    def neighbors(self, index):
        return self.edges[index]

    # 連結要素数を求める
    def neighbors_count(self, index):
        return len(self.edges[index])

    # 重そう
    def __str__(self):
        desc = ""
        for u in range(self._edges_count):
            for v in self.edges[u]:
                if u < v:
                    desc += "{} {}".format(u, v)
        return desc


def main():
    n, q = list(map(int, readline().split()))
    g = Graph(n)
    visited = [False] * n

    for _ in range(n - 1):
        a, b = list(map(int, readline().split()))
        a, b = a - 1, b - 1
        g.add_edge(a, b)

    for _ in range(q):
        p, x = list(map(int, readline().split()))
        p = p - 1
        g.add_counter(p, x)

    que = deque()
    que.append((0, 0))
    visited[0] = True

    while que:
        cur, cnt = que.popleft()
        g.add_counter(cur, cnt)
        nxtcnt = g.counter[cur]

        for nxt in g.neighbors(cur):
            if not visited[nxt]:
                visited[nxt] = True
                que.append((nxt, nxtcnt))

    print(*g.counter, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
E=[[] for _ in range(N)]
for i in range(N-1):
  x,y=map(int,input().split())
  x-=1
  y-=1
  E[x].append(y)
  E[y].append(x)
par=[-1]*N
par[0]=0
stack=[0]
order=[]
while stack:
  u=stack.pop()
  order.append(u)
  for v in E[u]:
    if par[v]==-1:
      stack.append(v)
      par[v]=u
counter=[0]*N
for i in range(Q):
  u,x=map(int,input().split())
  u-=1
  counter[u]+=x
for i in order:
  if i==0:
    pass
  else:
    counter[i]+=counter[par[i]]
for i in range(N):
  counter[i]=str(counter[i])
print(' '.join(counter))

Submission status: Accepted

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

def DFS(v, parent):
  global v_count
  for u in adj[v]:
    if u != parent:
      v_count[u] += v_count[v]
      DFS(u,v)

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

adj = [[] for _ in range(N)]
v_count = [0] * N

for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)# aがbの親とは限らないため

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

# 0起点に親ノードの数字を子ノードに足していく
DFS(0, -1)# 現在のノード, 親ノード
print(*v_count)

Submission status: Accepted

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

def DFS(v, parent):
  for u in adj[v]:
    if u != parent:
      v_count[u] += v_count[v]
      DFS(u,v)

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

adj = [[] for _ in range(N)]
v_count = [0] * N

for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)# aがbの親とは限らないため

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

# 0起点に親ノードの数字を子ノードに足していく
DFS(0, -1)# 現在のノード, 親ノード
print(*v_count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())

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

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

def dfs(v1, parent, add):
    values[v1] += add
    for v2 in graph[v1]:
        if v2 == parent:
            continue
        dfs(v2, v1, values[v1])

dfs(0, 0, 0)
print(*values)

Submission status: Accepted

Solution code:
#python3
from collections import deque 
def main():
    n, q = map(int, input().split())
    to = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        to[a].append(b)
        to[b].append(a)

    node = [0 for _ in range(n)]

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

    dq = deque() 
    dq.append(0)
    done = [0 for _ in range(n)]
    done[0] = 1
    while len(dq) > 0:
        x = dq.popleft()
        for i in to[x]:
            if done[i] == 1:
                continue
            node[i] += node[x]
            done[i] = 1 
            dq.append(i)

    for i in range(n):
        print(node[i]) if i == n-1 else print(node[i], end=' ')
main()

Submission status: Accepted

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


def inpl():
    return list(map(int, input().split()))


def bfs():
    visited[0] = True
    ans[0] = counter[0]
    deq = deque()
    deq.append(0)
    while deq:
        v = deq.popleft()
        for nv in edge[v]:
            if visited[nv] is True:
                continue
            visited[nv] = True
            ans[nv] = ans[v] + counter[nv]
            deq.append(nv)


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {k: 0 for k in range(N)}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

ans = [0] * N
visited = [False] * N

bfs()

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

Submission status: Accepted

Solution code:
from collections import deque

n,q = map(int,input().split())
r = [[] for _ in range(n)]
bonus = [0] * n
score = [0] * n

for i in range(n-1):
    a,b = map(int,input().split())
    r[a-1].append(b-1)
    r[b-1].append(a-1)
for i in range(q):
    p,x = map(int,input().split())
    bonus[p-1] += x
q = deque()
q.append(0)
used = [False]*n
used[0] = True
score[0] = bonus[0]

while q:
    p = q.popleft()
    for i in r[p]:
        if not used[i]:
            used[i] = True
            score[i] += score[p] + bonus[i]
            q.append(i)
        
print(*score)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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

n, q = na()
g = [deque() for _ in range(n)]
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
memo = [0] * n
for i in range(q):
    #seen = [False] * n
    p, x = na()
    p -= 1
    memo[p] += x

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

Submission status: Accepted

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

import sys

def dfs(i, p, add):
    add += add_node[i]
    counter[i] += add
    for j in adj[i]:
        if j != p:
            dfs(j, i, add)

sys.setrecursionlimit(10 ** 6)
n, q = map(int, input().split())
adj = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)
add_node = [0 for i in range(n)]
for i in range(q):
    p, x = map(int, sys.stdin.readline().split())
    add_node[p - 1] += x
counter = [0 for i in range(n)]
dfs(0, -1, 0)
print(" ".join(str(x) for x in counter))

Submission status: Accepted

Solution code:
#import deque
import sys

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

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

Graph = [[] for i in range(N)]
#print(Graph)
for _ in range(N-1):
    a, b = map(int, readline().split())
    #print(a, b)
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)

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

ans = [0] * N
def dfs(v, u, counter):
    counter += score[v]
    ans[v] = counter
    for c in Graph[v]:
        if c == u:
            continue
        dfs(c, v, counter)

dfs(0, -1, 0)

print(*ans)

Submission status: Accepted

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

from collections import deque
ans = [0]*n
q = deque()
used = [0]*n
q.append(0)
used[0]=1
ans[0] += count[0]

while q:
    p = q.popleft()
    for i in G[p]:
        if used[i]!=1:
            used[i]=1
            ans[i]+=ans[p]+count[i]
            q.append(i)

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6) #for deep recursion
     
    N, Q = list(map(int, input().split()))
    edges = [list(map(int, input().split())) for _ in range(N-1)]
    operations = [list(map(int, input().split())) for _ in range(Q)]
     
    counts = [0] * N
    for op in operations:
        p, x = op
        counts[p-1] += x
        
    all_connected_vertices = {i: [] for i in range(1, 1+N)}
    for a, b in edges:
        all_connected_vertices[a].append(b)
        all_connected_vertices[b].append(a)
        
    def dfs(point, pre):
        connected_vertices = all_connected_vertices[point]
        for c in connected_vertices:
            if c == pre:
                continue
            counts[c-1] += counts[point-1]
            dfs(c, point)
        
    dfs(1, -1)
        
    print(*counts)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = [0]*n

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

def dfs(i = 0, r = -1):
    for j in e[i]:
        if j != r:
            ans[j] += ans[i]
            dfs(j, i)

dfs()

print(*ans)

Submission status: Accepted

Solution code:
n,Q=map(int,input().split())
g=[[] for i 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)
depth=[-1]*n
depth[0]=0
q=[0]
while q:
  x=q.pop()
  for t in g[x]:
    if depth[t]==-1:
      depth[t]=depth[x]+1
      q.append(t)
cnt=[0]*n
for _ in range(Q):
  p,x=map(int,input().split())
  cnt[p-1]+=x
q=[0]
visited=[False]*n
while q:
  x=q.pop()
  visited[x]=True
  for t in g[x]:
    if not visited[t]:
      cnt[t]+=cnt[x]
      q.append(t)
print(*cnt)

Submission status: Accepted

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

def main():
    n,q=map(int,input().split())
    G=[[] for i in range(n)] #隣接配列
    P=[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
        P[p]+=x
    
    Chk=[0]*n #訪問済みチェック
    q=deque([0])
    while q: #qが空になるまで(BFS:幅優先探索)
        now=q.popleft() #取り出す
        Chk[now]=1 #訪問済みにする
        for i in G[now]: #子に対し
            if Chk[i]==0: #未訪問のとき
                P[i]+=P[now] #ポイント加算
                q.append(i) #親としてqに入れる

    print(*P)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from collections import deque


def read_input():
    n, q = map(int, input().split())
    
    # 辺を整理
    edges = {i: [] for i 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)
    # カウントを整理
    counter = {i: 0 for i in range(n)}
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p - 1] += x
    
    return n, edges, counter


def submit():
    n, edges, counter = read_input()

    # 深さ優先探索で各頂点のカウントを調べる
    v_count = {i: -1 for i in range(n)}
    q = deque()
    q.append((0, 0))
    while len(q):
        v, p = q.pop()
        v_count[v] = p + counter[v]
        for e in edges[v]:
            if v_count[e] < 0:
                q.append((e, v_count[v]))

    res = []
    for i in range(n):       
        res.append(v_count[i])
    print(" ".join(map(str, res)))


submit()

Submission status: Accepted

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

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

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

li = [0]*n

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

def dfs(i=0, r=-1):
    for j in e[i]:
        if j != r:
            li[j] += li[i]
            dfs(j, i)

dfs()

print(*li)

Submission status: Accepted

Solution code:
from collections import deque

n,q=map(int,input().split())
E=[[]for _ in range(n)]
P=[0]*n
V=[False]*n
for i in range(n-1):
    a,b=map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
for i in range(q):
    p,x=map(int,input().split())
    P[p-1]+=x

que=deque([0])
while que:
    s=que.popleft()
    V[s]=True
    for ni in E[s]:
        if V[ni]==False:
            P[ni]+=P[s]
            que.append(ni)
print(*P)

Submission status: Accepted

Solution code:
from collections import deque

n,q=map(int,input().split())
E=[[] for _ in range(n)]
P=[0]*n
V=[False]*n
for i in range(n-1):
    a,b=map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
for i in range(q):
    p,x=map(int,input().split())
    P[p-1]+=x

que=deque([0])
while que:
    s=que.popleft()
    V[s]=True
    for ni in E[s]:
        if V[ni]==False:
            P[ni]+=P[s]
            que.append(ni)
print(*P)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n

# O(2n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

# jun = []
# O(2n)
# def chil_pop(l,p):
#     jun.append(l)
#     for i in b[l]:
#         if i == p:
#             continue
#         chil_pop(i,l)
#     b[l] = p

# chil_pop(0,-1)


# O(q)
for i in range(q):
    p,x = mi()
    ans[p-1] += x


count = 0
q = [(0,-1)]
while q:
    c,p = q.pop()
    for i in b[c]:
        if i == p:
            continue
        ans[i] += ans[c]
        q.append((i,c))
    
    

# for i in jun[1:]:
#     ans[i] += ans[b[i]]

# ans_str = ''
# for i in range(n):
#     print(ans[i],end=' ')
#     # ans_str = ans_str + str(ans[i]) + ' '
print(*ans)

Submission status: Accepted

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

import sys

input = sys.stdin.buffer.readline

sys.setrecursionlimit(10 ** 6)

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)

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

counter = [0 for _ in range(N)]
for p, x in query:
    counter[p - 1] += x


def dfs(v, parent):
    for v_next in edges[v]:
        if v_next != parent:
            counter[v_next] += counter[v]
            dfs(v_next, v)


root = 0
dfs(root, None)

print(*counter)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def main():
    n,q=map(int,input().split())
    tree=[[]*n for i in range(n)]
    score=[0]*n
    
    for i in range(n-1):
        x,y=map(int,input().split())
        tree[x-1].append(y-1)
        tree[y-1].append(x-1)
        
    for i in range(q):
        x,y=map(int,input().split())
        score[x-1]+=y
    
    from collections import deque
    option=deque()
    option.append(0)
    completed=[None]*n
    
    while option:
        before=option.pop()
        completed[before]=True
        for i in tree[before]:
            if completed[i]==None:
                score[i]+=score[before]
                option.append(i)
    print(*score)
if __name__=="__main__":
    main()

Submission status: Accepted

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

tree = {}
for _ in range(n-1):
  a , b = map(lambda x:int(x)-1, input().split())
  if a not in tree:
    tree[a] = [b]
  else:
    tree[a].append(b)
  if b not in tree:
    tree[b] = [a]
  else:
    tree[b].append(a)

ans = [0]*n
ald = [True]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
ald[0] = False
for i in range(n):
  while will_go:
    now = will_go.pop()
    tmp = ans[now]
    for root in tree[now]:
      if ald[root]:
        ald[root] = False
        ans[root] += tmp
        will_go.append(root)
        
print(*ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p,0))

    while q:
        V,P,S=q.pop()
        if S==0:
            #下に遷移していくときの処理
            q.append((V,P,1))
            for new_v in G[V-1]:
                if new_v==P:continue
                score[new_v-1]+=score[V-1]
                q.append((new_v,V,0))


n,q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]

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

G=Graph(ab)
#print(G,score,sep='\n')
dfs(G,1,-1)
print(*score)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
ans=[0]*(n+1)

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


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

visit=[True]*(n+1)
tmp=[1]
for x in tmp:
    visit[x]=False
    for y in neighbor[x]:
        if visit[y]:
            tmp.append(y)
            ans[y]+=ans[x]

print(*ans[1:])

Submission status: Accepted

Solution code:
import sys 
input = sys.stdin.readline
N, Q = list(map(int,input().split()))

from collections import defaultdict
tree = defaultdict(set)

for n in range(N-1):
  a,b = list(map(int,input().split()))
  tree[a] |= {b}
  tree[b] |= {a}

weight = defaultdict(int)
for q in range(Q):
  p,x = list(map(int,input().split()))
  weight[p] += x

score = dict()


Q = [1 for i in range(N)]
determined = set()
next_ptr = 1
for i in range(N):
  q = Q[i]
  for node in tree[q]:
    if node not in determined: 
      Q[next_ptr] = node
      weight[node] += weight[q]
      next_ptr += 1
  determined |= {q}
for i in range(1,N+1):
  print(weight[i],end=" ")

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# クエリでは根だけにカウンターの値を足して、最後に上から足していく(imos法みたいに)
N, Q = lr()
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

counter = [0] * (N+1) # 1-indexed
for _ in range(Q):
    p, x = lr()
    counter[p] += x

root = 1
stack = [(root, None)]
while stack:
    cur, parent = stack.pop()
    c = counter[cur]
    for child in graph[cur]:
        if child == parent:
            continue
        counter[child] += c
        if len(graph[child]) > 1:
            stack.append((child, cur))

print(*counter[1:])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.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())
  G[a-1].append(b-1)
  G[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 G[v]:
    if nv != pv:
      points[nv] += points[v]
      dfs(nv, v)

dfs(0, 0)
print(*points)

Submission status: Accepted

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

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

edges = [[] for _ in range(n)]
cnt = [0 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)
    
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x
    
def dfs(frm, cur):
    for to in edges[cur]:
        if to != frm:
            cnt[to] += cnt[cur]
            dfs(cur, to)
dfs(-1, 0)          
print(*cnt)

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

sys.setrecursionlimit(10 ** 6)

n, q = na()
ab = nan(n - 1)
px = nan(q)

tree = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = ab[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

cnt = [0 for _ in range(n)]
for i in range(q):
    p, x = px[i]
    p -= 1
    cnt[p] += x

def dfs(i, p, s):
    x = s + cnt[i]
    cnt[i] = x
    for j in tree[i]:
        if j == p:
            continue
        dfs(j, i, x)

def bfs():
    q = deque()
    q.append((0, -1, 0))
    while len(q):
        p, b, s = q.popleft()
        x = s + cnt[p]
        cnt[p] = x
        for i in tree[p]:
            if i == b:
                continue
            q.append((i, p, x))

bfs()
print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
K=[set() for _ in range(n)]
V=[False]*n
P=[0]*n
for i in range(n-1):
      a,b=map(int,input().split())
      K[a-1].add(b-1)
      K[b-1].add(a-1)
for i in range(q):
      c,d=map(int,input().split())
      P[c-1]+=d
que=deque([0])
while que:
      s=que.popleft()
      V[s]=True
      for ni in K[s]:
            if V[ni]==False:
                  P[ni]+=P[s]
                  que.append(ni)
print(*P)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
K=[set()for _ in range(n)]
P=[0]*n
V=[False]*n
for i in range(n-1):
      a,b=map(int,input().split())
      K[a-1].add(b-1)
      K[b-1].add(a-1)
for i in range(q):
      p,x=map(int,input().split())
      P[p-1]+=x
que=deque([0])
while que:
      s=que.popleft()
      V[s]=True
      for ni in K[s]:
            if V[ni]==False:
                  P[ni]+=P[s]
                  que.append(ni)
print(*P)

Submission status: Accepted

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

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

edges = [[] for _ in range(n)]
cnt = [0 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)
    
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x
    
def dfs(frm, cur):
    for to in edges[cur]:
        if to != frm:
            cnt[to] += cnt[cur]
            dfs(cur, to)
dfs(-1, 0)          
print(*cnt)