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:
N, Q = map(int, input().split())


tree_dict = {}
value_dict = {}


def update_children(children, value):
    for child in children:
        value_dict[child] += value
        if len(tree_dict[child]) != 0:
            grandchildren = tree_dict[child]
            update_children(grandchildren, value)


for i in range(N):
    tree_dict[i + 1] = []
    value_dict[i + 1] = 0

for _ in range(N - 1):
    p, c = map(int, input().split())
    tree_dict[p].append(c)

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

print(' '.join(map(str, list(value_dict.values()))))

Submission status: Runtime Error

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

v_depth=[0 for _ in range(n+1)]
v_depth[1]=1
depth=[[] for _ in range(n+1)]
depth[1].append(1)

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

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

v_list=[]
i=1
while(len(depth[i])!=0):
    v_list.extend(depth[i])
    i+=1

for i in range(n):
    vi=v_list[i]
    v_counter[vi]+=v_counter[v_parent[vi]]

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

Submission status: Runtime Error

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

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

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

def dfs(chi_idx, parent):
	for child in node_idxes[chi_idx]:
		if child == parent:
			continue
		vals[child] += vals[chi_idx]
		dfs(child, chi_idx)

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

Submission status: Runtime Error

Solution code:
class Node(object):
	def __init__(self):
		self.val = 0
		self.children = []
	
	def add_child(self, child):
		self.children.append(child)

	def add_counter(self, val):
		self.val += val
		for child in self.children:
			child.add_counter(val)

n, q = map(int, input().split())
nodes = [Node() for i in range(n)]

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

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

for node in nodes:
	print(node.val, end=" ")

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import groupby

n,q = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n-1)]
lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]

kazu = [[]for _ in range(n)]
point = [0]*n

for i in range(len(li)):
    kazu[li[i][0]-1].append(li[i][1]-1)
    kazu[li[i][1]-1].append(li[i][0]-1)
for i in range(q):
    point[lin[i][0]-1] += lin[i][1]

def dfs(li,li2,now,before):
    for i in (li[now]):
        if i == before:
            continue
        li2[i] += li2[now]
        dfs(kazu,point,i,now)
dfs(kazu,point,0,-1)
print(*point)

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import groupby

n,q = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n-1)]
lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]

kazu = [[]for _ in range(n)]
point = [0]*n

for i in range(len(li)):
    kazu[li[i][0]-1].append(li[i][1]-1)
    kazu[li[i][1]-1].append(li[i][0]-1)
for i in range(q):
    point[lin[i][0]-1] += lin[i][1]

#深さ優先探索を実装したい(liが各ノードを入れたリスト、li2が)

def dfs(li,li2,now,before):
    for i in (li[now]):
        if i == before:
            continue
        li2[i] += li2[now]
        dfs(kazu,point,i,now)
dfs(kazu,point,0,-1)
print(*point)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N,Q = map(int, input().split())
ki = [[] for i in range(N+1)]
val = [0 for _ in range(N+1)]
 
for _ in range(N-1):
    a,b = map(int, input().split())
    ki[a].append(b)
for _ in range(Q):
    p,x = map(int, input().split())
    val[p] += x

touched = []
def add_num(p):
  touched.append(p)
  for k in ki[p]:
    if (k!=p)&(k not in touched):
      val[k] += val[p]
      add_num(k)

add_num(1)
print(*val[1:])

Submission status: Runtime Error

Solution code:
def search_add_num(p,x):
    for k in ki[p]:
        if k!=p:
            search_add_num(k,x)
        else:
            k_values[p] += x
N,Q = map(int, input().split())
ki = [[i] for i in range(N+1)]
k_values = [0 for _ in range(N+1)]

for _ in range(N-1):
    a,b = map(int, input().split())
    ki[a].append(b)
for _ in range(Q):
    p,x = map(int, input().split())
    search_add_num(p,x)
print(' '.join(map(str, k_values[1:])))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**10)


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))

Submission status: Runtime Error

Solution code:
n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))

Submission status: Runtime Error

Solution code:
from collections import deque

N, Q = [int(i) for i in input().split()]
trees = [[] for _ in range(N+1)]
for _ in range(N-1):
  a, b = [int(i) for i in input().split()]
  trees[a].append(b)    
count = [0]*(N+1)
for _ in range(Q):
  p, x = [int(i) for i in input().split()]
  count[p] = x

ans = [0]*(N+1)
d = deque(trees[1])
while len(d) > 0:
  elem = d.popleft()
  print(elem)
  ans[elem-1:] += count[elem-1]
  for next_elem in trees[elem]:
    d.append(next_elem)
  print(ans)

Submission status: Runtime Error

Solution code:
def solve():
    N, Q = map(int, input().split())
    tree = [[] for i in range(N)]
    counter = [0] * N
    for i in range(N-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
    
    for i in range(Q):
        p, x = map(int, input().split())
        adder(p-1, x, counter, tree)

    print(counter)

def adder(ind, add_val, counter, tree):
    counter[ind] += add_val
    if not tree[ind]:
        return

    for i in tree[ind]:
        adder(i, add_val, counter, tree)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
ki = [[[],0] for i in range(N)]
result = [0]*N

def dfs(i, num, parent):
    num_tmp = num+ki[i][1]
    result[i] = num_tmp
    if not ki[i][0]:
        return
    for j in ki[i][0]:
        if j == parent:
            continue
        dfs(j, num_tmp, i)
    return

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

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

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

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
ki = [[[],0] for i in range(N)]
result = [0]*N

def dfs(i, num, parent):
    num_tmp = num+ki[i][1]
    result[i] = num_tmp
    for j in ki[i][0]:
        if j == parent:
            continue
        dfs(j, num_tmp, i)
    return

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

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

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

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
ki = [[[],0] for i in range(N)]
result = [0]*N

def dfs(i, parent):
    if parent != -1:
        ki[i][1] += ki[parent][1]
    result[i] = ki[i][1]
    if not ki[i][0]:
        return
    for j in ki[i][0]:
        if j == parent:
            continue
        dfs(j, i)
    return

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

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

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

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
ki = [[[],0] for i in range(N)]
result = [0]*N

def dfs(i, num, ki, result, parent):
    num_tmp = num+ki[i][1]
    result[i] = num_tmp
    if not ki[i][0]:
        return
    for j in ki[i][0]:
        if j == parent:
            continue
        dfs(j, num_tmp, ki, result, i)
    return

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

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

dfs(0, 0, ki, result, -1)
print(*result)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
ki = [[[],0] for i in range(N)]
result = [0]*N

def dfs(i, num, ki, result):
    num_tmp = num+ki[i][1]
    result[i] = num_tmp
    if not ki[i][0]:
        return
    for i in ki[i][0]:
        dfs(i, num_tmp, ki, result)
    return

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

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

dfs(0, 0, ki, result)
print(*result)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
ki = [[[],0] for i in range(N)]
result = [0]*N

def dfs(i, num, ki, result):
    num_tmp = num+ki[i][1]
    result[i] = num_tmp
    if not ki[i][0]:
        return
    for i in ki[i][0]:
        dfs(i, num_tmp, ki, result)
    return

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

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

dfs(0, 0, ki, result)
tmp = ""
for i in result:
    tmp += str(i) + " "
print(tmp.rstrip())

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
ki = [[[],0] for i in range(N)]

def dfs(ki_elms, num, ki, result):
    num_tmp = num+ki_elms[1]
    result += str(num_tmp) + " "
    if not ki_elms[0]:
        return result
    for child in ki_elms[0]:
        result = dfs(ki[child], num_tmp, ki, result)
    return result

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

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

print(dfs(ki[0], 0, ki, "").rstrip())

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
ki = [[[],0] for i in range(N)]

def dfs(ki_elms, num, ki):
    num_tmp = num+ki_elms[1]
    print(num_tmp)
    if not ki_elms[0]:
        return
    for child in ki_elms[0]:
        dfs(ki[child], num_tmp, ki)

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

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

dfs(ki[0], 0, ki)

Submission status: Runtime Error

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N, Q = LI()
P = [0] * N
V = [[] for _ in range(N)]

w = [0]*N
for i in range(N-1):
    A, B = LI()
    V[A-1].append(B-1)
    V[B-1].append(A-1)
#    AB[i] = LI()
for i in range(Q):
    p, x = LI()
    P[p-1] += x

#print(V)
for i in range(N):
    w[i] += P[i]

#i = int(0)
#for l in V:
#   for j in l:
#        print(i, j)
#        w[j] += w[i]
#        print(w)
#    i +=1
def solve(v,i):
#    print(v,i)
#    print(w)
#    print("#####")
    if not v[i]:
        return
    else:
        for l in v[i]:
            w[l] += w[i]
            v[l].remove(i)
            solve(v,l)
        return
i =int(0)
solve(V,i)

print(" ".join(map(str,w)))

Submission status: Runtime Error

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

atai=[0]*n
oya=[0]*n

for i in range(1,n):
  a,b=map(int,input().split())
  oya[b-1]=a
#↑これにより、各木の親がどの番号なのかをメモっとく

sousa=[list(map(int,input().split())) for i in range(q)]
sousa.sort()

for i in range(q):
  #まず親の値を足す。
  if oya[sousa[i][0]-1]!=0:
    atai[i]+=atai[oya[i]-1] #(親の値は、実際のatai配列には1小さいインデックス番号にある)
    #足した後は「既に足した」証明として-1を代入。
    oya[sousa[i][0]-1]=-1
  #操作で足される文を足す
  atai[sousa[i][0]-1]+=sousa[i][1]

for i in range(n):
  if oya[i]!=-1:
    if oya[i]!=0:
      atai[i]+=atai[oya[i]-1]

for i in atai:
  print(i)

#むずｗ

Submission status: Runtime Error

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

atai=[0]*n
oya=[0]*n

for i in range(1,n):
  a,b=map(int,input().split())
  oya[b-1]=a
#↑これにより、各木の親がどの番号なのかをメモっとく

sousa=[list(map(int,input().split())) for i in range(q)]
sousa.sort()

for i in range(q):
  #まず親の値を足す。
  if oya[sousa[i][0]-1]!=0:
    atai[i]+=atai[oya[i]-1] #(親の値は、実際のatai配列には1小さいインデックス番号にある)
    #足した後は「既に足した」証明として0を代入。
    oya[sousa[i][0]-1]=0
  #操作で足される文を足す
  atai[sousa[i][0]-1]+=sousa[i][1]

for i in range(n):
  if oya[i]!=0:
    atai[i]+=atai[oya[i]-1]

for i in atai:
  print(i)

#むずｗ

Submission status: Runtime Error

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

atai=[0]*n
oya=[0]*n

for i in range(1,n):
  a,b=map(int,input().split())
  oya[b-1]=a
#↑これにより、各木の親がどの番号なのかをメモっとく

sousa=[list(map(int,input().split())) for i in range(q)]
sousa.sort()

for i in range(q):
  #まず親の値を足す。
  if oya[sousa[i][0]-1]!=0:
    atai[i]+=atai[oya[i]-1] #(親の値は、実際のatai配列には1小さいインデックス番号にある)
    #足した後は「既に足した」証明として0を代入。
    oya[sousa[i][0]-1]=0
  #操作で足される文を足す
  atai[sousa[i][0]-1]+=sousa[i][1]

for i in range(n):
  if oya[i]!=0:
    atai[i]+=atai[oya[i]-1]

print(atai)

#むずｗ

Submission status: Runtime Error

Solution code:
nodeN, tryN = map(int, input().split())
dic_cp = {}
sum_value =[0] * (nodeN + 1)
for _ in range(nodeN - 1):
    parent, child = map(int, input().split())
    dic_cp[child] = parent


for _ in range(tryN):
    no, value = map(int, input().split())
    sum_value[no] += value

ans = []
for i in range(1, nodeN + 1):
    wa = sum_value[i]
    k = i
    while k > 1:
        parent = dic_cp[k]
        wa += sum_value[parent]
        k = parent
    ans.append(wa)

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

Submission status: Runtime Error

Solution code:
import numpy as np
n, q = map(int, input().split())
e = np.eye(n + 1, dtype=int)
point = np.zeros(n+1, dtype=int)
for i in range(n - 1):
    a, b = map(int, input().split())
    if a != 1 and sum(e[1:a, a]) == 0:
        e[b][a] = 1
    else:
        e[a][b] = 1

def calc(x, y):
    for i in range(y):
        for j in range(y):
            if x[i][j] >= 1:
                x[i][j] = 1

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

for i in range(1, n+1):
    for j in range(i+1,n+1):
        if e[i][j] == 1:
            e[i] += e[j]
        else:
            continue

calc(e[1:, 1:], n)
ans = np.dot(point[1:], e[1:, 1:])
print(*ans)

Submission status: Runtime Error

Solution code:
N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
cnt = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x


flag = [-1]*N
q = [0]
cnt[0] = qlist[0]
while q:
    temp = q.pop(0)
    for i in L[temp]:
        if flag[i] < 0:
            q.append(i)
            cnt[i] += cnt[temp]
            flag[i] = 1
            
for i in range(N):
    print(cnt[i])

Submission status: Runtime Error

Solution code:
import numpy as np
n, q = map(int, input().split())
e = np.eye(n + 1, dtype=int)
point = np.zeros(n+1, dtype=int)
for i in range(n - 1):
    a, b = map(int, input().split())
    e[a][b] = 1
for i in range(q):
    p, x = map(int, input().split())
    point[p] += x

for i in range(1, n):
    for j in range(i+1,n):
        if e[i][j] == 1:
            e[i][j+1:] += e[j][j+1:]
        else:
            continue
ans = np.dot(point[1:], e[1:, 1:])
print(*ans)

Submission status: Runtime Error

Solution code:
N,Q = map(int, input().split())

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

question = [[int(q) for q in input().split()] for _ in range(Q)]

L = [[] for _ in range(N)]
for i in range(N-1):
    L[edge[i][0]-1].append(edge[i][1]-1)
    L[edge[i][1]-1].append(edge[i][0]-1)
    
qlist = [0]*N
for i in range(Q):
    qlist[question[i][0]-1] += question[i][1]
    
cnt = [-1]*N
q = [[0, qlist[0]]]
cnt[0] = qlist[0]
while q:
    temp = q.pop(0)
    v = temp[0]
    c = temp[1]
    for i in L[v]:
        if cnt[i] < 0:
            q.append([i, c+qlist[i]])
            cnt[i] = c+qlist[i]
            
for i in range(N):
    cnt[i] = str(cnt[i])
print(" ".join(cnt))

Submission status: Runtime Error

Solution code:
import numpy as np

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

e = np.eye(n + 1, dtype=int)
for i in range(n - 1):
    a, b = map(int, input().split())
    e[a][b] = 1

for i in range(1, n):
    for j in range(i+1,n):
        if e[i][j] == 1:
            e[i][j+1:] += e[j][j + 1:]
        else:
            continue

point = np.zeros(n, dtype=int)
for i in range(q):
    p, x = map(int, input().split())
    point[p - 1] += x
ans = np.dot(point, e[1:, 1:])
print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

e = np.eye(n + 1, dtype=int)
for i in range(n - 1):
    a, b = map(int, input().split())
    e[a][b] = 1

for i in reversed(range(2, n)):
    for j in range(1, i):
        if e[i - j][i] == 1:
            e[i - j][i + 1:] += e[i][i + 1:]
        else:
            continue

point = np.zeros(n, dtype=int)
for i in range(q):
    p, x = map(int, input().split())
    point[p - 1] += x
print(e[1:, 1:])
ans = np.dot(point, e[1:, 1:])
print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, q = map(int, input().split())

e = np.eye(n+1, dtype=int)
for i in range(n-1):
    a, b = map(int, input().split())
    e[a][b] = 1

for i in reversed(range(1, n+1)):
    for j in range(1, i):
        if e[i-j][i] == 1:
            e[i-j][i+1:] += e[i][i+1:]
        else:
            continue


point = np.zeros(n, dtype=int)
for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x
print(e[1:, 1:])
ans = np.dot(point, e[1:, 1:])
print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, q = map(int, input().split())

e = np.eye(n+1, dtype=int)
for i in range(n-1):
    a, b = map(int, input().split())
    e[a][b] = 1
print(reversed(range(2, n+1)))
for i in reversed(range(2, n+1)):
    for j in range(1, i-1):
        if e[i-j][i] == 1:
            e[i-j][i+1:] += e[i][i+1:]
        else:
            continue


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

ans = np.dot(point, e[1:, 1:])
print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, q = map(int, input().split())

e = np.eye(n+1, dtype=int)
for i in range(n-1):
    a, b = map(int, input().split())
    e[a][b] = 1

for i in reversed(range(2, n+1)):
    if e[i-1][i] == 1:
        e[i-1][i+1:] += e[i][i+1:]
    else:
        continue


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

ans = np.dot(point, e[1:, 1:])
print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, q = map(int, input().split())

e = np.eye(n+1, dtype=int)
for i in range(n-1):
    a, b = map(int, input().split())
    e[a][b] = 1

for i in reversed(range(1, n+1)):
    if e[i-1][i] == 1:
        e[i-1][i+1:] += e[i][i+1:]
    else:
        continue


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

ans = np.dot(point, e[1:, 1:])
print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, q = map(int, input().split())

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

for i in reversed(range(1, n+1)):
    if e[i-1][i] == 1:
        e[i-1][i+1:] += e[i][i+1:]
    else:
        continue


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

ans = np.dot(point, e[1:, 1:])
print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, q = map(int, input().split())

e = np.eye(n+1)

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

for i in reversed(range(1, n+1)):
    if e[i-1][i] == 1:
        e[i-1][i+1:] += e[i][i+1:]
        print(e[1:, 1:])
    else:
        continue


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

ans = np.dot(point, e[1:, 1:])
print(*ans)

Submission status: Runtime Error

Solution code:
a, b = map(int,(input().split()))

num_list = [0] * a

def add_num(li1, num, add): #li1はその数字のnet_list その数字とたす数
    num_list[num] += add
    for i in li1:
        if i >= num:
            add_num(net_list[i], i, add)


net_list = [[] for i in range(a)]
for i in range(a-1):
    x, y = map(int,(input().split()))
    net_list[x-1].append(y-1)
    net_list[y-1].append(x-1)

t = []
for _ in range(b):
    c = list(map(int,(input().split())))
    t.append(c)

for i in range(b):
    x, y = t[i]
    add_num(net_list[x-1], x-1, y)

for s in num_list:
    print(s, end=' ')

Submission status: Runtime Error

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

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

j_list = [list(map(int,input().split())) for _ in range(q)]
count_list = [0 for _ in range(n)]

class Queue:
    def __init__(self):
        self.queue = []
    # 先頭にデータを追加
    def add(self,x):
        self.queue.append(x)
    # 最後のデータを削除
    def remove(self):
        del self.queue[0]
    # 最後のデータを返す
    def peek(self):
        return self.queue[0]
    # 空かどうか確認
    def is_empty(self):
        return len(self.queue) == 0

def add(graph,count_list,queue,num):
    if queue.is_empty():
        pass
        # print(count_list)
    else:
        target = queue.peek()
        queue.remove()
        count_list[target-1] += num
        if target in graph:
            for node in graph[target]:
                queue.add(node)
        add(graph,count_list,queue,num)        

for elem in j_list:
    queue = Queue()
    queue.add(elem[0])
    add(graph,count_list,queue,elem[1])

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

Submission status: Runtime Error

Solution code:
def PX(T, P, X):
    if not P:
        return 0
    for p in P:
        ans[p] += X
        PX(p, memo[p], ans[p])
    return 0


N, Q = map(int, input().split())
memo = [[] for _ in range(N + 1)]
ans = [0 for _ in range(N + 1)]
for i in range(1, N):
    a, b = map(int, input().split())
    memo[a] += [b]
for j in range(Q):
    p, x = map(int, input().split())
    ans[p] += x
PX(1, memo[1], ans[1])
ans.pop(0)
print(*ans)

Submission status: Runtime Error

Solution code:
def PX(P, X):
    if not P:
        return 0
    for p in P:
        ans[p] += X
        PX(memo[p], X)
    return 0


N, Q = map(int, input().split())
memo = [[] for _ in range(N + 1)]
ans = [0 for _ in range(N + 1)]
for i in range(1, N):
    a, b = map(int, input().split())
    memo[a] += [b]
for j in range(Q):
    p, x = map(int, input().split())
    PX([p], x)
ans.pop(0)
print(*ans)

Submission status: Runtime Error

Solution code:
class TreeNode(object):
    def __init__(self, val):
        self.container = []
        self.val = val
        self.counter = 0

    def concatenate(self, node):
        self.container.append(node)

    def getNodes(self):
        return self.container

def traverseAndIncrement(root, val):
    if root:
        root.counter += val
        for node in root.getNodes():
            traverseAndIncrement(node, val)

if __name__ == '__main__':
    N, Q = map(int, input().split())
    tree = {}
    for i in range(N):
        tree[i + 1] = TreeNode(i + 1)

    for _ in range(N - 1):
        parent, child = map(int, input().split())
        tree[parent].concatenate(tree[child])

    for _ in range(Q):
        root_idx, val = map(int, input().split())
        traverseAndIncrement(tree[root_idx], val)

    for idx in range(N):
        print(tree[idx + 1].counter, end=' ')

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
tree=[[] for _ in range(N)]
counter=[0]*N
for _ in range(N-1):
    a,b=map(int, input().split())
    tree[a-1].append(b-1)
for _ in range(Q):
    p,x=map(int, input().split())
    counter[p-1]+=x
def f(t,x):
    for i in t:
        counter[i]+=x
        f(tree[i],counter[i])
f(tree[0],counter[0])
counter=list(map(str, counter))
print(' '.join(counter))

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
s=[0]*N
tree=[[] for _ in range(N)]
counter=[0]*N
def pl(t,x):
    if t:
        for i in t:
            s[i]+=x
            pl(tree[i],x)
for _ in range(N-1):
    a,b=map(int, input().split())
    tree[a-1].append(b-1)
for _ in range(Q):
    p,x=map(int, input().split())
    s[p-1]+=x
    pl(tree[p-1],x)
s=list(map(str, s))
print(' '.join(s))

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
s=[0]*N
tree=[[] for _ in range(N)]
counter=[0]*N
def pl(t,x):
    if t:
        for i in t:
            s[i]+=x
            pl(tree[i],x)
for _ in range(N-1):
    a,b=map(int, input().split())
    tree[a-1].append(b-1)
for _ in range(Q):
    p,x=map(int, input().split())
    s[p-1]+=x
    pl(tree[p-1],x)
s=[str(i) for i in s]
print(' '.join(s))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# input & solve
N, Q = map(int, input().split())

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

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

def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

dfs(0)

# output
print(*ans)

Submission status: Runtime Error

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

        for next in graph[now]:
            # 次のノードが前に参照した値の時はcontinue
            if next == prev:
                continue

            # 現在の値を次のポイントに加算することで累積和をとる
            point[next] += point[now]

            # 次のノードと現在のノードを引数にdfsを継続する
            dfs(next , now)

dfs(0)
print(*point)

Submission status: Runtime Error

Solution code:
N , Q = map(int,input().split())
stack = []
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] += b

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

#print(point)
dfs(0)
print(*point)

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
k=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  k[a-1].append(b-1)
for i in range(q):
  p,x=map(int,input().split())
  s[p-1]+=x
from collections import deque
d=deque()
d.append(0)
v=[False]*n
v[0]=True
while d:
  g=d.popleft()
  for i in k[g]:
    if v[i]:
      continue
    d.append(i)
    v[i]=True
    s[i]+=s[g]
print(*s)