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:
n,q = map(int,input().split())
g = [[] for i in range(n)]
c = [0]*n
reach = [False]*n
for i in range(n-1):
    a,b = map(lambda x: int(x)-1,input().split())
    g[a].append(b)
    g[b].append(a)

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

reach[0] = True
q = [0]
while q:
    cur = q.pop()
    reach[cur] = True
    for i in g[cur]:
        if not reach[i]:
            c[i] += c[cur]
            q.append(i)
print(*c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,q=mii()
mat = [[] for _ in range(n)]

for i in range(n-1):
    a,b=mii()
    mat[a-1].append(b-1)
    mat[b-1].append(a-1)
cnt=[0]*n

for i in range(q):
    p,x=mii()
    cnt[p-1]+=x

ans=[0]*n

def dfs(point,now,parent):
    point+=cnt[now]
    ans[now]=point
    for visit in mat[now]:
        if visit==parent:continue
        dfs(ans[now],visit,now)
dfs(0,0,0)
for i in ans:
    print(i)

Submission status: Accepted

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

n, q = map(int, input().split())
nodes = [[] for _ in range(n)]  # 隣接ノード
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    nodes[a].append(b)
    nodes[b].append(a)

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

ans = [0] * n
ans[0] = counts[0]
done = [0] * n
queue = Queue()
queue.put(0)
while True:
    node = queue.get()
    done[node] = 1
    next_nodes = nodes[node]
    for next_node in next_nodes:
        if not done[next_node]:
            queue.put(next_node)
            ans[next_node] = ans[node] + counts[next_node]
    if queue.empty():
        break

print(*ans)

Submission status: Accepted

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

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

from collections import deque
q = deque()
q.append(0)
visited = [False]*N
visited[0] = True
while len(q) > 0:
    index = q.pop()
    
    for e in edge[index]:
        if visited[e]:
            continue
        node[e] += node[index]
        visited[e] = True
        q.append(e)
print(*node)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
A = [LIST() for i in range(N-1)]
P = [LIST() for i in range(Q)]

graph = defaultdict(list)
for a, b in A:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

cnt = [0] * N
ans = [0] * N

for node, point in P:
    cnt[node-1] += point

check = [False] * N
q = deque([])
q.append(0)
check[0] = True

while q:
    a = q.pop()
    for node in graph[a]:
        if check[node] == True:
            continue
        cnt[node] += cnt[a]
        check[node] = True
        q.append(node)
print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque
N,Q = (int(x) for x in input().split())
connected = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append(b)
    connected[b-1].append(a)
counter = [0] * N
for _ in range(Q):
    p,x = (int(y) for y in input().split())
    counter[p-1] += x
ans = counter
q = deque([(1,0)])
searched = [0] * N
while q:
    a,p = q.popleft()
    if p != 0:
        ans[a-1] += ans[p-1]
    searched[a-1] = 1
    for child in connected[a-1]:
        if searched[child-1] == 0:
            q.append((child,a))
print(*ans)

Submission status: Accepted

Solution code:
import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
input = sys.stdin.readline # 文字列の入力のとき'/n'まで受け取るので注意!!!
sys.setrecursionlimit(500000)

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

C = [0]*N
for q in range(Q):
    p,x = map(int,input().split())
    C[p-1] += x
visited = [0]*N
def dfs(i):
    visited[i] = 1
    for k in d[i]:
        if visited[k]==1:
            continue
        C[k]+=C[i]
        dfs(k)
dfs(0)
print(*C)

Submission status: Accepted

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

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

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

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


ans = [0]*n

def dfs(f,cnt):
    ans[f] += cnt + X[f]
    for nxt in path[f]:
        if reached[nxt] : continue
        reached[nxt] = True
        dfs(nxt,cnt + X[f])
    return

reached = [True] + [False]*(n-1)
dfs(0,0)

print(' '.join(str(i) for i in ans))

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


if __name__ == '__main__':
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
    node = [0 for _ in range(N)]
    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1
        node[p] += x

    que = queue.Queue()
    que.put(0)
    res = [0 for _ in range(N)]
    unvisit = [True for _ in range(N)]
    while not que.empty():
        s = que.get()
        unvisit[s] = False
        res[s] += node[s]
        for ns in edge[s]:
            if unvisit[ns]:
                res[ns] += res[s]
                que.put(ns)

    print(*res)

Submission status: Accepted

Solution code:
# solution
# online help taken
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
aLst = [[int(i) for i in input().split()] for _ in range(N-1)]
pLst = [[int(i) for i in input().split()] for _ in range(Q)]
to = [[]for _ in range(N+1)]

for a,b in aLst:
    to[a].append(b)
    to[b].append(a)

ps = [0]*(N+1)
for a,b in pLst:
    ps[a] += b

def dfs(v, i):
    for j in to[v]:
        if j == i:
            continue
        ps[j] += ps[v]
        dfs(j,v)

dfs(1,0)
print(' '.join(map(str, ps[1:])))

Submission status: Accepted

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


def DFS(num,parent,point):
    D[num]=point+Q[num]
    for i in M[num]:
        if i!=parent:
            DFS(i,num,D[num])


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

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

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

D=[0]*n
DFS(0,-1,0)
print(*D)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
N, Q = map(int, input().split())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]
graph = [[] for _ in range(N)]
for a, b in ab:
  graph[a] += [b]
  graph[b] += [a]
dist = [0 for _ in range(N)]
for p, x in px:
  dist[p-1] += x

def dfs(u, pre):
  for v in graph[u]:
    if v != pre:
      dist[v] += dist[u]
      dfs(v, u)
  return


dfs(0, -1)
dist = list(map(str, dist))
print(" ".join(dist))

Submission status: Accepted

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

from collections import deque
que = deque([[-1, 0]])
while que:
    parent, child = que.popleft()
    for num in connect[child]:
        if num == parent:
            continue
        values[num] += values[child]
        que.append([child, num])
print(*values)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
import math
import bisect
import numpy as np
from collections import defaultdict, deque
from operator import itemgetter
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N, Q = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        G[a].append(b)
        G[b].append(a)
    A = [0] * N  # 頂点数分だけ準備する
    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1
        A[p] += x
    que = deque([[-1, 0]])
    while que:
        par, vi = que.popleft()
        for vj in G[vi]:
            if vj == par:  # 探索が親の時はスルー
                continue
            A[vj] += A[vi]  # 数値を追加する
            que.append([vi, vj])  # queに(親，子)を追加する
    print(*A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
rela = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    rela[a].append(b)
    rela[b].append(a)
hoge = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    hoge[p] += x
from collections import deque
que = deque([[-1, 0]])
while que:
    par, cur = que.popleft()
    for new in rela[cur]:
        if new == par:
            continue
        hoge[new] += hoge[cur]
        que.append([cur, new])
print(*hoge)

Submission status: Accepted

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

taiki = deque()
taiki.append(0)
owari = [True] * n
while  taiki:
    s = taiki.pop()
    for i in lot[s]:
        if owari[i]:
            tyu[i] += tyu[s]
            taiki.append(i)
    owari[s] = False
print(*tyu)

Submission status: Accepted

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

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

for abi in ab:
    a, b = abi
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

stack = deque()
stack.append([0])
while stack[0]:
    nstack = []
    cstack = stack.pop()
    #print('cstack:', cstack)
    for index in cstack:
        seen[index] = 1
        for edgei in edge[index]:
            if seen[edgei] == 0:
                nstack.append(edgei)
                cnter[edgei] += cnter[index]
    stack.append(nstack)

print(*cnter)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.buffer.readline
def dfs(G,v,p):
    for nv in G[v]:
        if(nv==p):
            continue
        point[nv]+=point[v]
        dfs(G,nv,v)

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

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

g = [[] for _ in range(n)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)

#親のノードに子を入れてくdfs
root = 0 #根
stack = [0]
parent = [0]*n
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in g[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)

#ここで、何らかのクエリを消化する。
query = [0]*n
for i in range(q):
    p,x = map(int,readline().split())
    p -= 1
    query[p] += x

#全ての親についての累積和を取る。
#この時、親方向に逆流しないように注意。
for x in order: #親
    a = query[x]
    for y in g[x]: #子
        if y == parent[x]: #逆流防止弁(無向グラフにしているので双方向の道がある)
            continue
        query[y] += a #子にクエリを適応

#output
print(*query)

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 defaultdict, deque

n, q = map(int, readline().split())
graph = defaultdict(list)
for i in range(n - 1):
    u, v = map(int, readline().split())
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)
v = [0] * n
for i in range(q):
    p, x = map(int, readline().split())
    v[p - 1] += x


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


dfs(0)
print(*v)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
#from math import floor, ceil
#from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [LI()for i in range(n)]
#inf = 10**17
#mod = 10**9 + 7

n,q=MI()
relation=[[] for i in range(n)]
for i in range(n-1):
    a,b=MI()
    a-=1
    b-=1
    relation[a].append(b)
    relation[b].append(a)
#print(relation)

nodes=[0]*n
for i in range(q):
    p,r=MI()
    p-=1
    nodes[p]+=r

Q=deque()
Q.append([-1,0])
#print(Q.popleft())

while Q:
    s,t=Q.popleft()
    for um in relation[t]:
        if um ==s:
            continue
        nodes[um]+=nodes[t]
        Q.append([t,um])
        
print(" ".join(map(str,nodes)))

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
rela = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    rela[a].append(b)
    rela[b].append(a)
hoge = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    hoge[p] += x
from collections import deque
que = deque([[-1, 0]])
while que:
    par, cur = que.popleft()
    for new in rela[cur]:
        if new == par:
            continue
        hoge[new] += hoge[cur]
        que.append([cur, new])
print(*hoge)

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)
ans = [0]*n
for i in range(q):
    p,x = map(int,input().split())
    p -= 1
    ans[p] +=x
visited = [0]*n
stack = deque()
stack.append(0)
visited[0] = 1
while stack:
    now = stack.popleft()
    for next in ki[now]:
        if visited[next]:continue
        ans[next] += ans[now]
        stack.append(next)
        visited[next] = 1

print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
f=lambda:map(int,sys.stdin.readline().split())
n,q=f()
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=f()
  g[a-1]+=[b-1]
  g[b-1]+=[a-1]
l=[0]*n
for i in range(q):
  p,x=f()
  l[p-1]+=x
def dfs(v,p=-1):
  for c in g[v]:
    if c==p: continue
    l[c]+=l[v]
    dfs(c,v)
dfs(0)
print(*l)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
f=lambda:map(int,sys.stdin.readline().split())
n,q=f()
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=f()
  g[a-1]+=[b-1]
  g[b-1]+=[a-1]
c=[0]*n
for i in range(q):
  v,x=f()
  c[v-1]+=x
def dfs(v,p=-1):
  for i in g[v]:
    if i==p: continue
    c[i]+=c[v]
    dfs(i,v)
dfs(0)
print(*c)

Submission status: Accepted

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

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

n, q = map(int,input().split())
g = [[] for _ in range(n+1)]
for  _ in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)
points = [0]*(n+1)
for _ in range(q):
    p, x = map(int,input().split())
    points[p] += x
# print(g)
# print(points)
def dfs(e,preve = -1):
    for nexte in g[e]:
        # print(nexte)
        if nexte == preve:
            continue
        points[nexte] = points[nexte] + points[e]
        dfs(nexte,e)
dfs(1)
print(*points[1:])

Submission status: Accepted

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

def input():
    return sys.stdin.readline()[:-1]

n, q = map(int,input().split())
g = [[] for _ in range(n+1)]
for  _ in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)
points = [0]*(n+1)
for _ in range(q):
    p, x = map(int,input().split())
    points[p] += x
# print(g)
# print(points)
def dfs(e,preve = -1):
    for nexte in g[e]:
        # print(nexte)
        if nexte == preve:
            continue
        points[nexte] = points[nexte] + points[e]
        dfs(nexte,e)
dfs(1)
print(*points[1:])

Submission status: Accepted

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

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

def dfs(now,prev=-1):
    for next in graph[now]:
        if next==prev:
            continue
        point[next]=point[next]+point[now]
        dfs(next,now)
dfs(0)
print(*point)

Submission status: Accepted

Solution code:
from collections import deque
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7


def main():
  N, Q = map(int, readline().split())
  AB = [[int(x) for x in readline().split()] for _ in range(N-1)]
  PX = [[int(x) for x in readline().split()] for _ in range(Q)]
  
  graph = [[] for _ in range(N+1)]
  for ab in AB:
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])
  
  value = [0] * (N+1)
  for px in PX:
    value[px[0]] += px[1]
  
  stack = deque([1])
  parent = [0] * (N+1)
  while stack:
    x = stack.popleft()
    for y in graph[x]:
      if y == parent[x]:
        continue
      parent[y] = x
      stack.append(y)
      value[y] += value[x]
      
  print(' '.join(map(str, value[1:])))
      
if __name__ == '__main__':
  main()

Submission status: Accepted

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

def dfs(ve, add):
  global seen
  global r
  seen[ve] = True
  r[ve] = add
  a = len(ki[ve])
  for i in range(a):
    b = ki[ve][i]
    if not seen[b]:
      dfs(b, add+ook[b])

N,Q = map(int, input().split())
side = [list(map(int, input().split())) for _ in range(N-1)]
op = [list(map(int, input().split())) for _ in range(Q)]
ki = [[] for _ in range(N)]
ook = [0]*N
seen = [False]*N
r = [0]*N

for i in range(N-1):
  a = side[i][0] -1
  b = side[i][1] -1
  ki[a].append(b)
  ki[b].append(a)
  
for i in range(Q):
  ook[op[i][0] -1] += op[i][1]
  
for i in range(N):
  if seen[i]:
    continue
  dfs(i, ook[i])
    
print(" ".join(map(str,r)))

Submission status: Accepted

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

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

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

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

st = [(0, 0, -1)]
while st:
	l = st.pop()
	ans[l[0]] = l[1] + queries[l[0]]
	for v in adj[l[0]]:
		if v != l[2]:
			st.append((v, ans[l[0]], l[0]))

print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1


N, Q = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(N - 1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

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

q = [(1, 0)]
while q:
    x, parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y, x))

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

Submission status: Accepted

Solution code:
from collections import deque
n,Q = map(int,input().split())
ki = [[] for i in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)
q = deque()
cnt = [0] * n
for _ in range(Q):
    p,x = map(int,input().split())
    cnt[p-1] += x
vis = [-1] * n
q.append(0)
vis[0] = 1
while q:
    a = q.popleft()
    a_ = ki[a]
    for i in a_:
        if vis[i] == -1:
            q.append(i)
            vis[i] = 1
            cnt[i] += cnt[a]
print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque
N,Q= map(int, input().split())
tree = [[] for _ in range(N)]
counter = [0]*N
visited = [False]*N
q = deque([0])

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())
    counter[p-1] += x

while q:
    parent = q.popleft()
    visited[parent] = True
    for child in tree[parent]:
        if visited[child]:
            continue
        counter[child] += counter[parent]
        q.append(child)
print(*counter)

Submission status: Accepted

Solution code:
from collections import deque
n,q = map(int,input().split())
graph = [[] for _ in range(n)]
cnt = [0] * n
already = [False] * n

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

while wait_q:
    parent = wait_q.pop()
    already[parent] = True
    for child in graph[parent]:
        if already[child] == True:continue
        cnt[child] += cnt[parent]
        wait_q.append(child)
print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque
n,q = map(int,input().split())
graph = [[] for _ in range(n)]
cnt = [0] * n
already = [False] * n

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

while len(wait_q) > 0:
    parent = wait_q.popleft()
    already[parent] = True
    for child in graph[parent]:
        if child == 0:continue
        if already[child] == True:continue
        cnt[child] += cnt[parent]
        wait_q.append(child)
print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque
n,q = map(int,input().split())
graph = [[] for _ in range(n)]
cnt = [0] * n
already = [False] * n

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

while len(wait_q) > 0:
    parent = wait_q.popleft()
    for child in graph[parent]:
        if child == 0:continue
        if already[child] == True:continue
        already[child] = True
        cnt[child] += cnt[parent]
        wait_q.append(child)
print(*cnt)

Submission status: Accepted

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

    def dfs(mae,ima):
        for tsugi in T[ima]:
            if tsugi != mae:
                V[tsugi] += V[ima]
                dfs(ima,tsugi)
    dfs(-1,0)
    print(*V)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int, input().split())
edges = [[]for _ in range(n)]
counter = [0]*n
visited=[-1]*n
que=deque()

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



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


que.append(0)
while que:
    v=que.popleft()
    visited[v]=1
    for next_v in edges[v]:
        if visited[next_v]!=-1:continue
        counter[next_v]+=counter[v]
        que.append(next_v)
print(*counter)

Submission status: Accepted

Solution code:
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)]

graph = [[] for _ in range(N)]
for ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

parent = [None] * N
parent[0] = 0

score = [0] * N
for pi, xi in px:
    score[pi - 1] += xi

ans = [None] * N

from collections import deque

q = deque([(0, 0)])
while len(q) > 0:
    src, score_tmp = q.popleft()
    score_tmp += score[src]
    ans[src] = score_tmp
    for dst in graph[src]:
        if ans[dst] != None: continue
        q.append((dst, score_tmp))

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
G=[[] for i in range(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)
c=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  c[p-1]+=x
from collections import deque
visited=[-1]*n
q=deque()
q.append(0)
while q:
  cur=q.popleft()
  visited[cur]=0
  for nx in G[cur]:
    if visited[nx]!=-1:continue
    c[nx]+=c[cur]
    q.append(nx)
print(*c)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
edge = [[] for _ in range(n)]
count = [0] * n

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

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

not_yet = [True] * n
not_yet[0] = False
stack = [0]
while stack:
    parent = stack.pop()
    for child in edge[parent]:
        if not_yet[child]:
            count[child] += count[parent]
            not_yet[child] = False
            stack.append(child)
print(*count)

Submission status: Accepted

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

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

s = []
visit = [-1]*n
s.append(0)
visit[0] = 0
while s:
    v = s.pop()
    for u in g[v]:
        if visit[u] == -1:
            X[u] += X[v]
            s.append(u)
            visit[u] = 0
print(*X)