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
readline = sys.stdin.readline

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

G = [[] for i in range(N)]

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

stack = [(0, -1, 0)]
while stack:
  v,parent,p = stack.pop()
  point[v] += p
  p = point[v]
  for child in G[v]:
    if child == parent:
      continue
    stack.append([child, v, p])
  
print(*point)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
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)

subtree_size=[0]*n
cnt=[0]*n

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

def dfs(G,v,p):
    ans[v]+=cnt[v]
    for nv in G[v]:
        if nv==p:
            continue
        cnt[nv]+=cnt[v]
        dfs(G,nv,v)
    
    subtree_size[v]=1
    for c in G[v]:
        if c==p:
            continue
        subtree_size[v]+=subtree_size[c]

root=0
dfs(G,root,-1)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N, Q = [int(n) for n in input().split()]
tree_list = [[] for _ in range(N)]

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

score_list = [0] * N
for j in range(Q):
    p, x = [int(n) for n in input().split()]
    score_list[p-1] += x

reached = [False] * N
def dfs(v):
    reached[v] = True
    for next_v in tree_list[v]:
        if reached[next_v] == True:
            continue
        score_list[next_v] += score_list[v]
        dfs(next_v)
dfs(0)
print(*score_list)

Submission status: Accepted

Solution code:
from collections import deque
N, Q = map(int, input().split())
A = [[] for i in range(N)]
for i in range(N - 1):
  a, b = map(int, input().split())
  A[a-1].append(b-1)
  A[b-1].append(a-1)
B = [[0, -1] for i in range(N)]
for i in range(Q):
  p, x = map(int, input().split())
  B[p-1][0] += x
d = deque([0])
while len(d) != 0:
  x = d.popleft()
  for a in A[x]:
    if a == B[x][1]:
      continue
    B[a][1] = x
    B[a][0] += B[x][0]
    d.append(a)
for i in range(N):
  print(B[i][0], end = "")
  if i != N - 1:
    print(" ", end = "")

Submission status: Accepted

Solution code:
# abc138 D ki

import sys
sys.setrecursionlimit(10**6)

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

N,Q = map(int,input().split())
g=[[] for _ in range(N)]

point=[0]*N

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

def dfs(n,pre=-1):
    for ne in g[n]:
        if ne == pre:
            continue
        
        point[ne]+=point[n]
        
        dfs(ne,n)
        
dfs(0)
print(*point)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def NLI(n):return [[int(i) for i in input().split()] for i in range(n)]
def NLI_(n):return [[int(i)-1 for i in input().split()] for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def INP():
    N=10;A=10
    n=random.randint(1,N)
    a=[random.randint(1,A) for i in range(n)]
    return n,a
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
#mo=998244353
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()


## return prime factors of N as dictionary {prime p:power of p}
## within 2 sec for N = 2*10**20+7
def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret

## return divisors of n as list
def divisor(n):
    div=[1]
    for i,j in primeFactor(n).items():
        div=[(i**k)*d for d in div for k in range(j+1)]
    return div

## return the list of prime numbers in [2,N], using eratosthenes sieve
## around 800 ms for N = 10**6  by PyPy3 (7.3.0) @ AtCoder
def PrimeNumSet(N):
    M=int(N**0.5)
    seachList=[i for i in range(2,N+1)]
    primes=[]
    while seachList:
        if seachList[0]>M:
            break
        primes.append(seachList[0])
        tmp=seachList[0]
        seachList=[i for i in seachList if i%tmp!=0]
    return primes+seachList


## retrun LCM of numbers in list b
## within 2sec for no of B = 10*5  and  Bi < 10**6
def LCM(b,mo=10**9+7):
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r


def dfs(x,edge,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
    q=deque([x])
    v=[None]*len(edge)
    v[x]=root_v
    while q:
        c=q.pop()
        for nb,d in edge[c]:
            if v[nb]==None:
                q.append(nb)
                v[nb]=func(c,v[c],nb,d)
    return v

def bfs(x,edge,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
    q=deque([x])
    v=[None]*len(edge)
    v[x]=root_v
    while q:
        c=q.popleft()
        for nb,d in edge[c]:
            if v[nb]==None:
                q.append(nb)
                v[nb]=func(c,v[c],nb,d)
    return v

show_flg=False
show_flg=True

ans=0

n,q=LI()
g,_=TI(n)

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

v=dfs(0,g,func=lambda pr,prv,nx,dist:prv+p[nx],root_v=p[0])
print(*v)

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)
#print(graph)
for _ in range(Q):
    a , b = map(int,input().split())
    a = a - 1
    point[a] += b
# dfsを用いて累積和を計算する
# 初期状態だと前の値がないためデフォルト引数に-1を代入
def dfs(now , prev = -1):
    for next in graph[now]:
        # 次のノードが前に参照した値の時はcontinue
        if next == prev:
            continue
        # 現在の値を次のポイントに加算することで累積和をとる
        point[next] += point[now]
        # 次のノードと現在のノードを引数にdfsを継続する
        dfs(next , now)

dfs(0)
print(*point)

Submission status: Accepted

Solution code:
from collections import deque
N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N-1)]
px = [list(map(int,input().split())) for _ in range(Q)]

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

counter = [0] * N
for p, x in px:
  counter[p-1] += x
  
flag = [1] * N
t = deque()
t.append(0)

#1(0)から順に探索していけば、自然と親→子の順番になる
while t:
  v = t.popleft()
  flag[v] = 0
  for i in tree[v]:
    if flag[i]:
      counter[i] += counter[v]
      t.append(i)
      
print(*counter)

Submission status: Accepted

Solution code:
def main():
	N, Q = [int(n) for n in input().split(" ")]
	edges = [[] for i in range(N)]
	counter = [0] * N

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

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

	to_visit = [0]
	checked = [1] + [0] * (N - 1)
	tree = [0] * N

	while len(to_visit) > 0:
		visiting = to_visit.pop()
		tree[visiting] += counter[visiting]
		for e in edges[visiting]:
			if checked[e] == 0:
				checked[e] = 1
				to_visit.append(e)
				tree[e] = tree[visiting]

	print(" ".join([str(s) for s in tree]))

main()

Submission status: Accepted

Solution code:
# import itertools
# import math
import sys
sys.setrecursionlimit(500*500)
# import numpy as np
# from collections import deque
# import heapq

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, Q = map(int, input().split())
# A = list(map(int, input().split()))
# A = list(map(lambda x: int(x)*(-1), input().split()))
# B = list(map(int, input().split()))
# A_B = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

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

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

depth = [-1] * (N + 1)
depth[1] = 0
count = [0] * (N + 1)

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

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + 1
#             dfs(tree, l[0])
# dfs(tree, 1)
def dfs(tree, s):
    for l in tree[s]:
        if depth[l] == -1:
            depth[l] = 0
            count[l] += count[s]
            dfs(tree, l)
dfs(tree, 1)


for i in count[1:]:
    print(i, end = ' ')

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr



# bfs
# tree = [[] for _ in range(N + 1)]
# edges = [list(map(int,input().split())) for _ in range(M)]

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

# depth = [-1] * (N + 1)
# depth[1] = 0

# d = deque()
# d.append(1)

# ans = [0] * (N + 1)
# while d:
#  v = d.popleft()
#  for i in tree[v]:
#    if depth[i] != -1:
#      continue
#    depth[i] = depth[v] + 1
#    ans[i] = v
#    d.append(i)

# # ans = depth[2:]
# print('Yes')
# print(*ans[2:], sep="\n")

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
G = [[] for n in range(N)]
ans = N*[0]

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

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

f = N*[1]
t = [0]
while t:
  v = t.pop()
  f[v] = 0
  for k in G[v]:
    if f[k]:
      ans[k]+=ans[v]
      t.append(k)

print(*ans)

Submission status: Accepted

Solution code:
import sys
import math

#https://atcoder.jp/contests/agc008/submissions/15248942
sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

class Node:
    def __init__(self):
        self.edge = []
        self.count = 0

def dfs(tree,node,p_node,p_count,counts):
    count = tree[node].count + p_count
    counts[node] = count
    for x in tree[node].edge:
        if x == p_node:
            continue
        dfs(tree,x,node,count,counts)

N,Q = inm()

tree = []
for _ in range(N):
    tree.append(Node())

#node = Node()
#tree = [node]*N

for _ in range(N-1):
    a,b = inm()
    tree[a-1].edge.append(b-1)
    tree[b-1].edge.append(a-1)

for _ in range(Q):
    p,x = inm()
    tree[p-1].count += x

val = []
for _ in range(N):
    val.append(0)

#for i in range(N):
#    print(tree[i].edge)
#    print(tree[i].count)

dfs(tree,0,-1,0,val)

counts_str = [str(n) for n in val]
s = " ".join(counts_str)
print(s)

Submission status: Accepted

Solution code:
from collections import deque
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)
    
X =[0]*n
for w in range(q):
    p,x = map(int,input().split())
    X[p-1]+=x
    
def bfs(u):
    queue = deque([u])
    d = [None]*n
    
    d[u] = 0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v]+1
                X[i] += X[v]
                queue.append(i)
    return d

p = [None]*n
d = bfs(0)

print(*X)

Submission status: Accepted

Solution code:
n,q=map(int, input().split())
go_list=[[] for i in range(n+1)]
cnt=[0]*(n+1)
Oya=[False]*(n+1)
Oya[1]=True
for i in range(n-1):
    a,b=map(int, input().split())
    go_list[a].append(b)
    go_list[b].append(a)

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

from collections import deque
que=deque()

que.append(1)
sumi=[False]*(n+1)
sumi[1]=True
while que:
    ne=que.popleft()
    for i in go_list[ne]:
        if not sumi[i]:
            cnt[i]+=cnt[ne]
            sumi[i]=True
            que.append(i)

cnt.pop(0)
print(*cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
edge=[[] for _ in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
def dfs(c,p):
    for i in edge[c]:
        if i==p:
            continue
        ans[i]+=ans[c]
        dfs(i,c)
dfs(0,-1)
print(*ans)

Submission status: Accepted

Solution code:
import collections

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

value = ['-'] * (n+1)

connected = [set() for i in range(n+1)]

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

for i in range(q):
  p,x = map(int, input().split())
  if value[p] == '-':
    value[p] = 0
  value[p] -= x

queue = collections.deque(connected[1])

if value[1] == '-':
  value[1] = 0
else:
  value[1] = -value[1]

for i in queue:
  if value[i] == '-':
    value[i] = 0
  else:
    value[i] = -value[i]
  value[i] += value[1]


while queue:
  s = queue.popleft()
  v = value[s]
  for i in connected[s]:
    vi = value[i]
    if vi == '-' or vi < 0:
      if vi == '-':
        vi = 0
      value[i] = -(vi-v)
      queue.append(i)
    
print(' '.join(str(i) for i in value[1:]))

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

N,Q=mint()
node=[list() for _ in range(N+1)]
done=[0]*(N+1)
X=[0]*(N+1)
for _ in range(N-1):
    a,b=mint()
    node[a].append(b)
    node[b].append(a)
for _ in range(Q):
    p,x=mint()
    X[p]+=x
q=deque([1])
while len(q)>0:
    i=q.popleft()
    done[i]=1
    for j in node[i]:
        if not done[j]:
            X[j]+=X[i]
            q.append(j)
lprint(X[1:],' ')

Submission status: Accepted

Solution code:
n,q=map(int, input().split())
go_list=[[] for i in range(n+1)]
cnt=[0]*(n+1)
Oya=[False]*(n+1)
Oya[1]=True
for i in range(n-1):
    a,b=map(int, input().split())
    go_list[a].append(b)
    go_list[b].append(a)

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

from collections import deque
que=deque()

que.append(1)
sumi=[False]*(n+1)
sumi[1]=True
while que:
    ne=que.popleft()
    for i in go_list[ne]:
        if not sumi[i]:
            cnt[i]+=cnt[ne]
            sumi[i]=True
            que.append(i)

cnt.pop(0)
print(*cnt)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]
g = [[] for _ in range(N)]
for a, b in ab:
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

children = [[] for _ in range(N)]
parent = [-1]*N
q = [0]
while len(q) > 0:
    v = q.pop()
    for u in g[v]:
        if u != parent[v]:
            parent[u] = v
            children[v].append(u)
            q.append(u)

counter = [0]*N
for p, x in px:
    counter[p - 1] += x

ans = [0]*N
q = [(0, 0)]
while len(q) > 0:
    v, c = q.pop()
    ans[v] = c + counter[v]
    for u in children[v]:
        q.append((u, ans[v]))
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n,q = map(int,readline().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:n+n-2])
PX = iter(ABPX[n+n-2:])

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

val = [0] * (n+1)
for p, x in zip(PX, PX):
    val[p] += x

stack = [1] #queue的なやつ
parent = [0] * (n+1)
while stack:
    x = stack.pop() #根を引っこ抜く
    for y in graph[x]: #木を見る
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        val[y] += val[x]
        
print(' '.join(map(str, val[1:])))

Submission status: Accepted

Solution code:
def solve():
    import sys
    sys.setrecursionlimit(10**6)
    def dfs(tree, n, ans):
        for i in tree[n]:
            ans[i] += ans[n]
            tree[i].remove(n)
            dfs(tree, i, ans) #再帰関数になっている。次の木の中を探索
     
    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)]
     
    g = [[] for _ in range(n)]
    for i in range(n-1):
        g[ab[i][0]-1].append(ab[i][1]-1)
        g[ab[i][1]-1].append(ab[i][0]-1)
    
    ans = [0]*n
    for i in range(q):
        ans[px[i-1][0]-1] += px[i-1][1]
    dfs(g, 0, ans)
     
    print(*ans)
    
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(tree, n, ans):
    for i in tree[n]:
        ans[i] += ans[n]
        tree[i].remove(n)
        dfs(tree, i, ans)
 
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)]
 
g = [[] for _ in range(n)]
for i in range(n-1):
    g[ab[i][0]-1].append(ab[i][1]-1)
    g[ab[i][1]-1].append(ab[i][0]-1)
 
ans = [0]*n
for i in range(q):
    ans[px[i-1][0]-1] += px[i-1][1]
dfs(g, 0, ans)
 
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N, LIST):
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR):
    que, frag = deque([0]), set([0])
    while que:
        q = que.popleft()
        for i in NEAR[q]:
            if i in frag:
                continue
            ans[i] += ans[q]
            que.append(i), frag.add(i)
    return

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)]

ans = [0] * n
for p, x in px:
    ans[p - 1] += x

near = nearlist(n, ab)
bfs(near)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N, LIST):
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR):
    que, frag = deque([0]), set([0])
    while que:
        q = que.popleft()
        for i in NEAR[q]:
            if i in frag:
                continue
            ans[i] += ans[q]
            que.append(i), frag.add(i)
    return

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)]

ans = [0] * n
for p, x in px:
    ans[p - 1] += x

near = nearlist(n, ab)
bfs(near)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

def nearlist(N, LIST):
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR):  # 幅優先探索  # キュー
    que, frag = deque([0]), set([0])
    while que:
        q = que.popleft()
        for i in NEAR[q]:  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            ans[i] += ans[q]
            que.append(i), frag.add(i)
    return

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)]

ans = [0] * n
for p, x in px:
    ans[p - 1] += x

near = nearlist(n, ab)
bfs(near)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(tree, n, ans):
    for i in tree[n]:
        ans[i] += ans[n]
        tree[i].remove(n)
        dfs(tree, i, ans)

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)]

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

ans = [0]*n
for i in range(q):
    ans[px[i-1][0]-1] += px[i-1][1]
dfs(g, 0, ans)

print(*ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.buffer.readline
    import collections

    n, q = map(int, readline().split())
    ab = [list(map(int, readline().split())) for _ in range(n-1)]
    px = [list(map(int, readline().split())) for _ in range(q)]

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

    point = [0] * n
    for p, x in px:
        point[p-1] += x

    parents = [0] * n
    ans = [0] * n
    q = collections.deque()
    q.append(0)
    while q:
        v = q.pop()
        ans[v] = ans[parents[v]] + point[v]
        for i in c[v]:
            if i == parents[v]:
                continue
            parents[i] = v
            q.append(i)
    print(' '.join(list(map(str, ans))))

main()

Submission status: Accepted

Solution code:
import collections

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)]

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

point = [0] * n
for p, x in px:
    point[p-1] += x

parents = [0] * n
ans = [0] * n
q = collections.deque()
q.append(0)
while q:
    v = q.pop()
    ans[v] = ans[parents[v]] + point[v]
    for i in c[v]:
        if i == parents[v]:
            continue
        parents[i] = v
        q.append(i)
print(' '.join(list(map(str, ans))))

Submission status: Accepted

Solution code:
import sys
import math

#https://atcoder.jp/contests/agc008/submissions/15248942
sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

counts = []

class Node:
    def __init__(self):
        self.edge = []
        self.count = 0

def dfs(tree,node,p_node,p_count):
    count = tree[node].count + p_count
    counts[node] = count
    for x in tree[node].edge:
        if x == p_node:
            continue
        dfs(tree,x,node,count)

N,Q = inm()

tree = []
for _ in range(N):
    tree.append(Node())

#node = Node()
#tree = [node]*N

for _ in range(N-1):
    a,b = inm()
    tree[a-1].edge.append(b-1)
    tree[b-1].edge.append(a-1)

for _ in range(Q):
    p,x = inm()
    tree[p-1].count += x

for _ in range(N):
    counts.append(0)

#for i in range(N):
#    print(tree[i].edge)
#    print(tree[i].count)


dfs(tree,0,-1,0)

counts_str = [str(n) for n in counts]
s = " ".join(counts_str)
print(s)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

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

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


ans = [0 for _ in range(N)]
for i in range(Q):
  ans[P[i][0] - 1] += P[i][1]

dist = [-1 for _ in range(N)]
dist[0] = 0
d = deque([0])
while d:
    now = d.pop()
    for i in range(len(link[now])):
        if dist[link[now][i]] == -1:
            ans[link[now][i]] += ans[now]
            dist[link[now][i]] = 0
            d.append(link[now][i])

for i in range(N):
    if i != N - 1:
        print(ans[i], end=" ")
    else:
        print(ans[i])