atcoder ABC138 D - Ki - stosasa’s blog

・説明：いもす法を木でやれば良い。いもす法については
いもす法 - いもす研 (imos laboratory)
を参考。
注意として途中でlru_cacheを使っているが使わないほうがはやい。

import sys
sys.setrecursionlimit(10**6)   #再帰関数の上限を上げる
#from functools import lru_cache   #メモ化再帰で高速化

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)

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

#@lru_cache(maxsize=1000)
def dfs (v,bv=-1):   #vが今の頂点、bvが前の頂点、はじめは-1。
  for nv in G[v]:
    if nv==bv:    #前の頂点と次の頂点が同じ、つまり無限ループしたらスルー。
      continue
    ans[nv]+=ans[v]   #いもす法
    dfs(nv,v)

for i in range(q):
  p,x=map(int,input().split())
  p-=1
  ans[p]+=x   #いもす法
  
dfs(0) 
print(*ans)