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: Runtime Error

Solution code:
def dfs(_v, _u):
  for u in v[_v]:
    if u==_u: continue;
    ans[u]+=ans[_v]
    dfs(u, _v)
        
  
def main():
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1, input().split())
    v[a].append(b)
    v[b].append(a)
  
  for i in range(q):
    p,x=map(lambda x:int(x)-1, input().split())
    ans[p]+=x+1
  
  dfs(0,-1)
  
  print(*ans, sep=' ')
  
if __name__=='__main__':
  n,q=map(int,input().split())
  ans=[0]*n
  v=[[]*n for i in range(n)]
  main()

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
def main():
  n,q=map(int,input().split())
  g=[[] for i in range(n)]
  g[0]=[0]
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    g[b].append(a)
    
  ans=[0]*n
  for i in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x
  
  g=sorted(enumerate(g), key=lambda x:(x[1][0]))
  #print(g)
  for i in range(1,n):
    e,rs=g[i][0],g[i][1]
    for r in rs:
      ans[e]+=ans[r]
    
  print(*ans,sep=' ')


if __name__=='__main__':
  main()

Submission status: Runtime Error

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

#print(tree_list)

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: Runtime Error

Solution code:
N, Q = [int(n) for n in input().split()]

tree_list = [[] for _ in range(N)]
count_list = [0] * N

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

#print(tree_list)
#print(count_list)

for j in range(Q):
    p, x = [int(n) for n in input().split()]

    def func(pn, xn):
        count_list[pn] += xn
        if not tree_list[pn]:
            return
        for k in tree_list[pn]:
            func(k, xn)

    func(p-1, x)
    
#print(count_list)

print(*count_list)

Submission status: Runtime Error

Solution code:
N, Q = [int(n) for n in input().split()]

tree_list = [[] for _ in range(N)]
count_list = [0] * N

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

#print(tree_list)
#print(count_list)

for j in range(Q):
    p, x = [int(n) for n in input().split()]

    def func(pn, xn):
        count_list[pn] += xn
        for k in tree_list[pn]:
            func(k, xn)

    func(p-1, x)
    
#print(count_list)

print(*count_list)

Submission status: Runtime Error

Solution code:
N, Q = [int(n) for n in input().split()]

tree_list = {n:[] for n in range(1, N+1)}
count_list = {n:0 for n in range(1, N+1)}

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

#print(tree_list)
#print(count_list)

def func(pn, xn):
    count_list[pn] += xn
    if not tree_list[pn]:
        return
    else:
        for k in tree_list[pn]:
            func(k, xn)

for j in range(Q):
    p, x = [int(n) for n in input().split()]
    func(p, x)
    
#print(count_list)

print(' '.join([str(v) for v in count_list.values()]))

Submission status: Runtime Error

Solution code:
N, Q = [int(n) for n in input().split()]

tree_list = {n:[] for n in range(1, N+1)}
count_list = {n:0 for n in range(1, N+1)}

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

#print(tree_list)
#print(count_list)

def func(pn, xn):
    count_list[pn] += xn
    for k in tree_list[pn]:
        func(k, xn)

for j in range(Q):
    p, x = [int(n) for n in input().split()]
    func(p, x)
    
#print(count_list)

print(' '.join([str(v) for v in count_list.values()]))

Submission status: Runtime Error

Solution code:
N, Q = [int(n) for n in input().split()]

tree_list = {n:[] for n in range(1, N+1)}
count_list = {n:0 for n in range(1, N+1)}

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

#print(tree_list)
#print(count_list)

def func(pn):
    count_list[pn] += x
    for k in tree_list[pn]:
        func(k)

for j in range(Q):
    p, x = [int(n) for n in input().split()]
    func(p)
    
#print(count_list)

print(' '.join([str(v) for v in count_list.values()]))

Submission status: Runtime Error

Solution code:
N, Q = [int(n) for n in input().split()]

tree_list = {n:[] for n in range(1, N+1)}
count_list = {n:0 for n in range(1, N+1)}

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

#print(tree_list)
#print(count_list)

for j in range(Q):
    p, x = [int(n) for n in input().split()]
   
    def func(pn):
        count_list[pn] += x
        for k in tree_list[pn]:
            func(k)
    
    func(p)
    
#print(count_list)

print(' '.join([str(v) for k, v in count_list.items()]))

Submission status: Runtime Error

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

v = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1 # listのindex参照をそのまま使いたいので頂点id(1から始まっている)を-1しておく
  b -= 1 # aと同様
  v[a].append(b)
  v[b].append(a)

f = [0]*n
for i in range(q):
  p,x = map(int,input().split())
  p -= 1 # aと同様
  f[p] += x

def dfs(x,d,s): # x:計算する頂点（上側）, d:計算済み(0)か否か(1), s:頂点xの値
  for y in v[x]: # 頂点xとつながる各頂点yの計算を行う
    if d[y]: # 頂点yが計算未了の場合
      s += f[y] # 頂点xの値sに頂点yの値を足す
      ans[y] = s # 頂点yの値はsに確定
      d[y] = 0 # 頂点yの計算は終わったのでd[y]=0とする
      dfs(y,d,s) # 頂点yの下層についても再帰的に計算
      s -= f[y] # 頂点yの下層の計算が終わったので、sを頂点xの値に戻す

ans = [0]*n
d = [1]*n
d[0] = 0
ans[0] = f[0]
s = f[0]
dfs(0,d,s)
Z=[str(a) for a in ans]
Z=" ".join(Z)
print(Z)

Submission status: Runtime Error

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

v = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1 # listのindex参照をそのまま使いたいので頂点id(1から始まっている)を-1しておく
  b -= 1 # aと同様
  v[a].append(b)
  v[b].append(a)

f = [0]*n
for i in range(q):
  p,x = map(int,input().split())
  p -= 1 # aと同様
  f[p] += x

def dfs(x,d,s): # x:計算する頂点（上側）, d:計算済み(0)か否か(1), s:頂点xの値
  for y in v[x]: # 頂点xとつながる各頂点yの計算を行う
    if d[y]: # 頂点yが計算未了の場合
      s += f[y] # 頂点xの値sに頂点yの値を足す
      ans[y] = s # 頂点yの値はsに確定
      d[y] = 0 # 頂点yの計算は終わったのでd[y]=0とする
      dfs(y,d,s) # 頂点yの下層についても再帰的に計算
      s -= f[y] # 頂点yの下層の計算が終わったので、sを頂点xの値に戻す

ans = [0]*n
d = [1]*n
d[0] = 0
ans[0] = f[0]
s = f[0]
dfs(0,d,s)
print(*ans)

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5+5)
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
def count(p,x):
    ans[p]+=x
    for i in edge[p]:
        if i<p:
            continue
        count(i,x)
for i in range(q):
    p,x=map(int,input().split())
    count(p-1,x)
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**10+5)
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
def count(p,x):
    ans[p]+=x
    for i in edge[p]:
        if i<p:
            continue
        count(i,x)
for i in range(q):
    p,x=map(int,input().split())
    count(p-1,x)
print(*ans)

Submission status: Runtime Error

Solution code:
def solve():
    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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
n,q = map(int,input().split())
graph = [[] for i in range(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)

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

st = [0]
visit = [false for i in range(n)]
while not len(st) == 0:
  now = st.pop()
  visit[now] = true
  for e in graph[now]:
    if visit[e]:
      continue
    weight[e] += weight[e]
    st.push(e)
    
print(' '.join(map(str,weight)))

Submission status: Runtime Error

Solution code:
# D - Ki TLE
import sys
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
root = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if not(b in root):
        G[a].append(b)
    # b が根と繋がっているとき
    else:
        G[b].append(a)
    if a == 0:
        root.add(b)


cnt = [0]*N
for p,x in lst:
    cnt[p] += x 
    
seen = [False]*N
def dfs(v):
    seen[v] = True# v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        cnt[next_v] += cnt[v] 
        dfs(next_v)
dfs(0)
print(*cnt)

Submission status: Runtime Error

Solution code:
# D - Ki TLE
import sys
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
root = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if not(b in root):
        G[a].append(b)
    # b が根と繋がっているとき
    else:
        G[b].append(a)
    if a == 0:
        root.add(b)

lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))

seen = [False]*N
cnt = [0]*N
def dfs(v,point,seen):
    seen[v] = True# v を訪問済みにする
    cnt[v] += point
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        dfs(next_v,point,seen)

for p,x in lst:
    seenC = seen.copy()
    dfs(p,x,seenC)
print(*cnt)
    
lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))


cnt = [0]*N
for p,x in lst:
    cnt[p] += x 
    
seen = [False]*N
def dfs(v):
    seen[v] = True# v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        cnt[next_v] += cnt[v] 
        dfs(next_v)
dfs(0)
print(*cnt)

Submission status: Runtime Error

Solution code:
# D - Ki TLE
import sys
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
root = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if not(b in root):
        G[a].append(b)
    # b の方が根に近いとき
    else:
        G[b].append(a)
    root.add(b)

lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))

cnt = [0]*N
for p,x in lst:
    cnt[p] += x 
    
def dfs(v):
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        cnt[next_v] += cnt[v] 
        dfs(next_v)
dfs(0)
print(*cnt)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
ab = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
p, x = [], []
px = dict()
for _ in range(q):
    pp, xx = map(int, input().split())
    p.append(pp-1)
    x.append(xx)
    px[pp-1] = xx


def dfs(now):
    for i in ab[now]:
        if d[i] == -1:
            d[i] = d[now]+1
            dfs(i)


d = [-1]*n
d[0] = 0
dfs(0)
ans = [0]*n
for i in range(len(p)):
    for j in range(n):
        if d[j] >= d[p[i]]:
            ans[j] += x[i]

print(*ans)

Submission status: Runtime Error

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

N, Q = map(int,input().split())
G = [[] for _ in range(N)]
counter = [0] * N

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

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

seen = [False]*N

def dfs(v, seen, G, counter):
    seen[v] = True
    for u in G[v]:
        if not seen[u]:
            counter[u] += counter[v]
            dfs(u, seen, G, counter)

dfs(0, seen, G, counter)

for c in counter:
    print(c, end = " ")
print("")

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc138/tasks/abc138_d
from collections import deque

#入力受付
N,Q = map(int, input().split())

connection_dict = {i:set() for i in range(1,N+1)}

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

#一個ずつ操作する必要はないので、まとめて実施する
#入力受付
px_list = [0 for i in range(0,N+1)]
for i in range(Q):
    p,x = map(int, input().split())
    px_list[p] += x

#実施
ans = [0 for _ in range(0,N+1)]
#1から始めて下流に値を流していく
def add_counter(node,from_upstream):
    ans[node] = from_upstream + px_list[node]
    for downstream in connection_dict[node]:
        add_counter(downstream,ans[node])

add_counter(1,0)

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

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import defaultdict
import sys
sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, q = input_int_list()
    cnt = [0] * (n + 1)  # 1-indexed
    tree = defaultdict(list)

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

    # 遅延評価をする O(q)
    for _ in range(q):
        p, x = input_int_list()
        cnt[p] += x

    # 遅延評価（DFS）O(n)
    def tree_walk(root, add):
        cnt[root] += add
        for node in tree[root]:
            if node not in visited:
                visited.add(node)
                tree_walk(node, cnt[root])

    visited = set([1])
    # ルート(1)から結果を評価する
    tree_walk(1, 0)

    print(" ".join([str(i) for i in cnt[1:]]))
    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, q = input_int_list()
    cnt = [0] * (n + 1)  # 1-indexed
    tree = defaultdict(list)

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

    # 遅延評価をする
    for _ in range(q):
        p, x = input_int_list()
        cnt[p] += x

    # 遅延評価（DFS）
    def tree_walk(root, add):
        cnt[root] += add
        for node in tree[root]:
            if node not in visited:
                visited.add(node)
                tree_walk(node, cnt[root])

    visited = set([1])
    # ルート(1)から結果を評価する
    tree_walk(1, 0)

    print(*cnt[1:])
    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, q = input_int_list()
    cnt = [0] * (n + 1)  # 1-indexed
    tree = defaultdict(list)
    depth = [0] * (n + 1)  # 1-indexed

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

    dq = deque()

    dq.append((1, 0))  # node,depth
    visited = set([1])

    while dq:
        root, dep = dq.popleft()
        for node in tree[root]:
            if node not in visited:
                visited.add(node)
                depth[node] = dep + 1
                dq.append((node, dep + 1))

    def tree_walk(root, x):
        cnt[root] += x
        d = depth[root]
        for node in tree[root]:
            if node not in visited and d < depth[node]:
                visited.add(node)
                tree_walk(node, x)

    for _ in range(q):
        p, x = input_int_list()
        visited = set([p])
        tree_walk(p, x)

    print(*cnt[1:])
    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, q = input_int_list()
    cnt = [0] * (n + 1)  # 1-indexed
    tree = defaultdict(list)

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

    def tree_walk(root, x):
        cnt[root] += x
        for node in tree[root]:
            tree_walk(node, x)

    for _ in range(q):
        p, x = input_int_list()
        tree_walk(p, x)

    print(*cnt[1:])
    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n,q=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in range(n-1)]
    tree=[list() for _ in range(n)]
    score=[0]*n
    for a,b in ab:
        a-=1
        b-=1
        tree[a].append(b)
    px=[list(map(int,input().split())) for _ in range(q)]
    for p,x in px:
        p-=1
        add(p,x,tree,score)
    print(s)

def add(p,x,tree,score):
    score[p] += x
    s=tree[p][:]
    while len(s)>0:
        t = s.pop()
        score[t] += x
        for i in tree[t]:
            s.append(i)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def dfs(atai,n):
    global tokuten,visited
    #print(atai,n)
    tokuten[n] += atai
    for i in tree[n]:
        if not visited[n]:
            dfs(tokuten[n],i)

n,q = map(int,input().split())
tree = [[] for i in range(n+1)]
tokuten = [int(0) for i in range(n+1)]
visited = [False for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    tree[a].append(b)
#print(tree)

for j in range(q):
    p,x = map(int,input().split())
    tokuten[p] += x
#print(tokuten)

dfs(0,1)

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

Submission status: Runtime Error

Solution code:
def dfs(atai,n):
    global tokuten
    #print(atai,n)
    tokuten[n] += atai
    if len(tree[n])==0:
        return
    else:
        for i in tree[n]:
            dfs(tokuten[n],i)

n,q = map(int,input().split())
tree = [[] for i in range(n+1)]
tokuten = [int(0) for i in range(n+1)]

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

for j in range(q):
    p,x = map(int,input().split())
    tokuten[p] += x
#print(tokuten)

dfs(0,1)

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

Submission status: Runtime Error

Solution code:
def dfs(atai,n):
    global tokuten
    #print(atai,n)
    tokuten[n] += atai
    if len(tree[n])==0:
        return
    else:
        for i in tree[n]:
            dfs(tokuten[n],i)

n,q = map(int,input().split())
tree = [[] for i in range(n+1)]
tokuten = [int(0) for i in range(n+1)]

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

for j in range(q):
    p,x = map(int,input().split())
    tokuten[p] += x
#print(tokuten)

dfs(0,1)

for i in range(1,n+1):
    print(tokuten[i])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int,input().split())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

d = defaultdict(int)
for _ in range(Q):
    p,x = map(int,input().split())
    d[p-1] += x
visited = [False]*N
cnt = [0]*N
def dfs(n, acc):
    cnt[n] = acc
    for m in edges[n]:
        if not visited[m]:
            visited[m] = True
            dfs(m, acc+d[m])
visited[0] = True
dfs(0, d[0])
print(*cnt)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, Q = map(int,input().split())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

d = defaultdict(int)
for _ in range(Q):
    p,x = map(int,input().split())
    d[p-1] += x
visited = [False]*N
cnt = [0]*N
def dfs(n, acc):
    cnt[n] = acc
    for m in edges[n]:
        if not visited[m]:
            visited[m] = True
            dfs(m, acc+d[m])
visited[0] = True
dfs(0, d[0])
print(*cnt)

Submission status: Runtime Error

Solution code:

n, q = map(int, input().split())
point = [0]*n
graph = [[] for i in range(n)]
visited = [False]*n


def dfs(n):
    visited[n-1] = True
    for node in graph[n-1]:
        if visited[node-1]:
            continue
        point[node-1] += point[n-1]
        dfs(node)


def main():

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

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

    dfs(1)

    print(*point)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().rsplit()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


n, q = LI()
point = [0]*n
graph = [[] for i in range(n)]
visited = [False]*n


def dfs(n):
    visited[n-1] = True
    for node in graph[n-1]:
        if visited[node-1]:
            continue
        point[node-1] += point[n-1]
        dfs(node)


def main():

    for i in range(n - 1):
        a, b = LI()
        graph[a - 1].append(b)
        graph[b - 1].append(a)

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

    dfs(1)

    print(*point)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().rsplit()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def dfs(n):
    visited[n-1] = True
    for node in graph[n-1]:
        if visited[node-1]:
            continue
        point[node-1] += point[n-1]
        dfs(node)


n, q = LI()
point = [0]*n
graph = [[] for i in range(n)]

for i in range(n - 1):
    a, b = LI()
    graph[a - 1].append(b)
    graph[b - 1].append(a)


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

visited = [False]*n

dfs(1)

print(*point)

Submission status: Runtime Error

Solution code:
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def dfs(n):
    visited[n-1] = True
    for node in graph[n-1]:
        if visited[node-1]:
            continue
        point[node-1] += point[n-1]
        dfs(node)


n, q = LI()
point = [0]*n
graph = [[] for i in range(n)]

for i in range(n - 1):
    a, b = LI()
    graph[a - 1].append(b)
    graph[b - 1].append(a)


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

visited = [False]*n

dfs(1)

print(*point)

Submission status: Runtime Error

Solution code:
def dfs(n):
    visited[n-1] = True
    for node in graph[n-1]:
        if visited[node-1]:
            continue
        point[node-1] += point[n-1]
        dfs(node)


n, q = LI()
point = [0]*n
graph = [[] for i in range(n)]

for i in range(n - 1):
    a, b = LI()
    graph[a - 1].append(b)
    graph[b - 1].append(a)


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

visited = [False]*n

dfs(1)

print(*point)