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:
#-*- coding: utf-8
#  -*-
"""
oj dl https://atcoder.jp/contests/abc116/tasks/abc116_d -d test-d
oj test -d test-d -c "python abc116d.py"
oj test -d test-d -c "python abc116d.py" test-d/sample-3.in
"""
from collections import defaultdict
import sys
import math
from datetime import datetime
from typing import List


class TreeNode:
    def __init__(self):
        self.val = 0
        self.vertex = []

def make_trees(n, A, B):
    trees = []
    for i in range(n):
        trees.append(TreeNode())
    for i in range(len(A)):
        a = A[i]-1
        b = B[i]-1
        trees[a].vertex.append(b)
    return trees

def dfs(node: TreeNode, x: int, trees):
    if node:
        node.val += x
        for i in node.vertex:
            dfs(trees[i], x, trees)


def sol(n, q, A, B, P, X):
    trees = make_trees(n, A, B)
    for i in range(len(P)):
        p = P[i]-1
        x = X[i]
        t = trees[p]
        # dfs, give point x
        dfs(t, x, trees)
    #
    return [t.val  for t in trees]
    #return n, q, A, B, P, X



do_submit = True
#do_submit = False

def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(map(str, line.split())) for line in lines]
    print(parsed_lines)
    n = int(parsed_lines[0][0])
    q = int(parsed_lines[0][1])
    A = []
    B = []
    P = []
    X = []
    for i in range(1, n-1+1):
        a = int(parsed_lines[i][0])
        b = int(parsed_lines[i][1])
        A.append(a)
        B.append(b)
    for i in range(n, 1+n+q-1):
        p = int(parsed_lines[i][0])
        x = int(parsed_lines[i][1])
        P.append(p)
        X.append(x)

    # S = parsed_lines[1][0]
    # return n, k, S
    return n, q, A, B, P, X


if not do_submit:
    n, q, A, B, P, X = input_parse("""
    4 3
    1 2
    2 3
    2 4
    2 10
    1 100
    3 1
    """)
    print(sol(n, q, A, B, P, X))

else:
    # n = int(input().strip())
    # q = int(input().strip())
    n, q = list(map(int, input().split()))
    A = []
    B = []
    P = []
    X = []
    for i in range(n-1):
        a, b = list(map(int, input().split()))
        # a = int(input().strip())
        # b = int(input().strip())
        A.append(a)
        B.append(b)
    for i in range(q):
        p, x = list(map(int, input().split()))
        # p = int(input().strip())
        # x = int(input().strip())
        P.append(p)
        X.append(x)
    print(sol(n, q, A, B, P, X))

Submission status: Runtime Error

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

def add(p, x):
    c[p] += x
    for i in E[p]:
        c[i] += x
        for j in E[i]:
            add(j, x)


N, Q = map(int, input().split())
E = [[] for i in range(N+1)]
c = [0 for i in range(N+1)]

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

for i in range(1, Q+1):
    p, x = map(int, input().split())
    add(p, x)

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

Submission status: Runtime Error

Solution code:

N, Q = map(int, input().split())
A = [[] for i in range(N)]
P = []
X = []
c = [0]*N
def add(p, x):
    for a in A[p]:
        c[a] += x
        add(a, x)

for i in range(N-1):
    a, b = map(int, input().split())
    A[a-1].append(b-1)
for i in range(Q):
    p, x = map(int, input().split())
    P.append(p-1)
    X.append(x)
for i in range(Q):
    p = P[i]
    x = X[i]
    if p == 0:
        c = list(map(lambda a: a+x, c))
    else:
        c[p] += x
        add(p, x)
print(' '.join(map(str,c)))

Submission status: Runtime Error

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

def dfs(G,v):
    seen[v]=True
    for next_v in G[v]:
        if G[next_v]==True:
            continue
        else:
            counter[next_v]+=counter[v]
            dfs(G,next_v)

seen=[False for _ in range(N+1)]
dfs(graph,1)
ans=''
for i in range(N):
    ans+=str(counter[i+1])+' '
print(ans)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
E = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    # E[b-1].append(a-1)
P = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    P[p-1] += x
result = [0] * n
E2 = [[i] for i in range(n)]
 
def r(current, point):
    result[current] += point
    while True:
        try:
            ee = E[current].pop()
            # E[ee].remove(current)
        except IndexError:
            break
        r(ee, point+P[ee]) 
 
r(0, P[0])

print(*result)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
E = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
P = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    P[p-1] += x
result = [0] * n
E2 = [[i] for i in range(n)]
 
def r(current, point):
    result[current] += point
    while True:
        try:
            ee = E[current].pop()
            E[ee].remove(current)
        except IndexError:
            break
        r(ee, point+P[ee]) 
 
r(0, P[0])

print(*result)

Submission status: Runtime Error

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

childs = [[] for _ in range(n+1)]
parent = [-1 if i == 1 else None for i in range(n+1)]
nodes_in_level = [[] for _ in range(n+1)]
level_of_node = [0 if i == 1 else None for i in range(n+1)]

level_of_node[0].append(1)

for _ in range(n-1):
  a, b = map(int, input().split())
  childs[a].append(b)
  parent[b] = a
  level_of_node[b] = level_of_node[a] + 1
  nodes_in_level[level_of_node[b]].append(b)

ans = 0
nodes_under_level = [0 for i in range(n+1)]
for i in list(range(n))[::-1]:
  nodes_under_level[i] = nodes_under_level[i+1] + len(nodes_in_level[i])

for _ in range(q):
  p, x = map(int, input().split())
  ans += nodes_under_level[level_of_node[p]] * x
  
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys

sys.setrecursionlimit(10000)

def forward(matrix, plus, pos, counter):
    for i in range(pos+1,N):
        val = matrix[pos,i]
        if val == 1:
            counter[i] += plus
            save = pos
            forward(matrix, plus, i, counter)

if __name__ == '__main__':
    N, Q = map(int, input().split())

    matrix = np.zeros((N,N))
    counter = []
    for i in range(N):
        counter.append(0)

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

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

    for p, x in zip(P,X):
        counter[p] += x
        forward(matrix, x, p, counter)

    out = str(counter[0])
    for i in range(len(counter)-1):
        out = out + ' ' + str(counter[i+1])

    print(out)

Submission status: Runtime Error

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

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


node_cnts = [0] * (N+1)


def gen_subtree_nodes(node, count):
    node_cnts[node] = count
    for n in nodes[node]:
        subtree_nodes = gen_subtree_nodes(n, count + PX[n])


gen_subtree_nodes(1, PX[1])

print(*node_cnts[1:])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
if __name__ == '__main__':
    n,q = (int(i) for i in input().split())
    parent = [0 for i in range(2*10**5)]
    for i in range(n-1):
        num1,num2 = (int(i) for i in input().split())
        parent[num2] = num1
    
    counter = defaultdict(list)
    for i in range(q):
        num1,num2 = (int(i) for i in input().split())
        counter[num1].append(num2)

    dp = [0,sum(counter[1])]
    for i in range(1,n+1):
        ans=0
        if(i==1):
            print(sum(counter[i]),end=" ")
        else:
            ans = dp[parent[i]]+sum(counter[i])
            print(ans,end=" ")
            dp.append(ans)

Submission status: Runtime Error

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

MAX = 100002

def add_num(nn, x):
    if nn == -1:
        return
    Tree[nn][0] += x
    for ni in Tree[nn][1]:
        add_num(ni, x)


ipt = input().split()
N = int(ipt[0])
Q = int(ipt[1])



Tree = []
for m in range(MAX):
    Tree.append([-1, [-1]])

nodes = set()
nodes.add(1)

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

    Tree[a][0] = 0
    Tree[a][1].insert(0, b)
    Tree[b][0] = 0

    nodes.add(b)



for i in range(Q):
    ipti = input().split()
    p = int(ipti[0])
    x = int(ipti[1])
    add_num(p, x)


for n in nodes:
    print(Tree[n][0])

Submission status: Runtime Error

Solution code:
N,Q = list(map(int, input().split(" ")))
v_list = [0 for _ in range(N)] # n-1でやること注意
dic_tree = {}
for i in range(N):
    dic_tree[i+1] = [] 

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

# make tree
for k in reversed(range(N)):
    if len(dic_tree) == 0:
        continue
    
    for node in dic_tree[k+1]:
        dic_tree[k+1].extend(dic_tree[node])
        
# add 1 
dic_tree[1].append(1)
    
for i in range(Q):
    p, x = list(map(int, input().split(" ")))
    
    for i in dic_tree[p]:
        v_list[i-1] += x

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

class Node():
    def __init__(self):
        self.parent = -1
        self.children = []
        self.count = 0

# def add_count(G, v, x):
#     G[v].count += x
#     for child in G[v].children:
#         add_count(G, child, x)

def add_count(G, v=0):
    for child in G[v].children:
        G[child].count += G[v].count
        add_count(G, child)

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


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

add_count(G)



counts = [node.count for node in G]
print(*counts)

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
tree = [set() for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    tree[a-1].add(b)
ans=[0]*n
def add_l(x):    
    for i in list(tree[x-1]):
        add_l(i)
        tree[x-1] |= (tree[i-1])

add_l(1)
#print(tree)

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

        for j in list(tree[p-1]):
            ans[j-1]+=x
print(*ans)

Submission status: Runtime Error

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

ki = [[] for i in range(n+1)]
for i in range(n-1):
    hida,migi = list(map(int, input().split()))
    ki[hida].append(migi)

p = [0] * (n+1)
for i in range(q):
    pp,xx = list(map(int, input().split()))
    p[pp] += xx

# print("p",p)
# print("ki",ki)

list_n = [0] * (n+1)
list_s = [0] * (n+1)
ind = 0

def adddd(num):
    global ki
    global list_n
    global list_s
    global ind

    list_n[ind] = num
    list_s[ind] += p[num]

    if ( len(ki[num]) > 0):
        for ko in ki[num]:
            ind += 1
            adddd(ko)
    list_s[ind+1] -= p[num]

adddd(1)

# print("n",list_n)
# print("s",list_s)

tmp = 0
list_ss = [0] * (n+1)
for i,si in enumerate(list_s):
    tmp += si
    list_ss[i] = tmp

# print("ss",list_ss)

list_rtn = [0] * n
for i in range(n):
    list_rtn[list_n[i] - 1] = list_ss[i]

print(*list_rtn)

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, id):
        self.id = id
        self.node1 = 0
        self.node2 = 0
        self.val = 0

    def set_node(self, node):
        if self.node1 == 0:
            self.node1 = node
        else:
            self.node2 = node


def add_val(node, val):
    global tree
    if node.id == 0:
        return
    node.val += val
    add_val(tree[node.node1], val)
    add_val(tree[node.node2], val)


n, q = map(int, input().split())
tree = [Node(id) for id in range(n + 1)]

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

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

for i in range(1, n + 1):
    if i != 1:
        print(" ", end="")
    print(tree[i].val, end="")
print("")

Submission status: Runtime Error

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

chil = [[] for _ in range(N+1)]
count = [0]*(N+1)

for ab in AB:
    chil[ab[0]].append(ab[1])
    chil[ab[1]].append(ab[0])

def cleanse(fromN, toN):
    chil[toN].remove(fromN)
    if len(chil[toN])==0:  # leaf
        return
    for node in chil[toN]:
        cleanse(toN, node)

for node in chil[1]:
    cleanse(1, node)

def addition(fromN, toN, value):
    count[toN] += value
    if len(chil[toN])==0:
        return
    for node in chil[toN]:
        addition(toN, node, value)

for px in PX:
    count[px[0]] += px[1]
    for node in chil[px[0]]:
        addition(px[0], node, px[1])

print(*count[1:])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
#ABC138D
import copy
import sys
import math

tmp = input().split()
n,q = list(map(lambda a: int(a), tmp))

a=[]
b=[]
apex=[]
node=[]

apex.append(0)

node=[]
for i in range(0,n+2):
	node.append([])

for i in range(1,n):
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))
	apex.append(0)
	node[hoge[0]].append(hoge[1])
apex.append(0)

for i in range(1,q+1):
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))
	apex[hoge[0]]+=hoge[1]

#print(node)
#print(apex)

def calc(j):
	for i in node[j]:
		apex[i]+=apex[j]
		calc(i)

calc(1)

#print(apex)


ans=str(apex[1])
for i in range(2,n+1):
	ans += " " + str(apex[i])
print(ans)

Submission status: Runtime Error

Solution code:
n,q = map(int, input().split())
ab = [list(map(int,input().split())) for _ in range(n-1)]
pq = [list(map(int,input().split())) for _ in range(q)]

graph = {}
ans_list = [0]*n

for a,b in ab:
    if not a in graph:
        graph[a] = [a]

    graph[a].append(b)
    
    if not b in graph:
        graph[b] = [b]
    
    for i in range(1,a):
        if a in graph[i]:
            graph[i].append(b)
        
for p,q in pq:
    for i in set(graph[p]):
        ans_list[i-1] += q

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

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
ans=[0]*N;con=[0]*N;ab=[]
for i in range(N-1):
    a, b = map(int, input().split())
    con[b-1] = a

def dfs(Q, X):
    ans[Q-1] += X
    for n in range(len(con))[Q:]:
        if con[n] == Q:
            dfs(n+1,X)

qx = []
for i in range(Q):
    q, x = map(int, input().split())
    dfs(q, x)

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
n,q=map(int,input().strip().split())
d=[[] for _ in range(n)]

for _ in range(n-1):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)
l=[0]*n
for _ in range(q):
    a,b=map(int,input().split())
    l[a-1]+=b
rs=[0]*n

def rr(pa,s,dd,d):
    for c in d[s]:
        if c == pa:
            continue
        rs[c]=l[c]+dd
#        print(c,rs[c],dd)
        rr(s,c,dd+l[c],d)

s,dd=0,l[0]
rs[0] = l[0]
rr(None,s,dd,d)
for r in rs:
    print(r)

Submission status: Runtime Error

Solution code:
#-*- coding: utf-8
#  -*-
"""
oj dl https://atcoder.jp/contests/abc116/tasks/abc116_d -d test-d
oj test -d test-d -c "python abc116d.py"
oj test -d test-d -c "python abc116d.py" test-d/sample-3.in
"""
from collections import defaultdict
import sys
import math
from datetime import datetime
from typing import List


class TreeNode:
    def __init__(self):
        self.val = 0
        self.vertex = []

def make_trees(n, A, B):
    trees = []
    for i in range(n):
        trees.append(TreeNode())
    for i in range(len(A)):
        a = A[i]-1
        b = B[i]-1
        trees[a].vertex.append(b)
    return trees

def dfs(node: TreeNode, x: int, trees):
    if node:
        node.val += x
        for i in node.vertex:
            dfs(trees[i], x, trees)


def sol(n, q, A, B, P, X):
    trees = make_trees(n, A, B)
    for i in range(len(P)):
        p = P[i]-1
        x = X[i]
        t = trees[p]
        # dfs, give point x
        dfs(t, x, trees)
    #
    return [t.val  for t in trees]
    #return n, q, A, B, P, X



do_submit = True
#do_submit = False

def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(map(str, line.split())) for line in lines]
    print(parsed_lines)
    n = int(parsed_lines[0][0])
    q = int(parsed_lines[0][1])
    A = []
    B = []
    P = []
    X = []
    for i in range(1, n-1+1):
        a = int(parsed_lines[i][0])
        b = int(parsed_lines[i][1])
        A.append(a)
        B.append(b)
    for i in range(n, 1+n+q-1):
        p = int(parsed_lines[i][0])
        x = int(parsed_lines[i][1])
        P.append(p)
        X.append(x)

    # S = parsed_lines[1][0]
    # return n, k, S
    return n, q, A, B, P, X


if not do_submit:
    n, q, A, B, P, X = input_parse("""
    4 3
    1 2
    2 3
    2 4
    2 10
    1 100
    3 1
    """)
    print(sol(n, q, A, B, P, X))

else:
    n = int(input().strip())
    S = list(map(int, input().split()))
    #S = input().split()
    # print(sol(n, k, S))

    #s = input().strip()
    # S = input().strip()
    print(sol(n, S))

Submission status: Runtime Error

Solution code:
    class Node:
        def __init__(self, index):
            self.count = 0
            self.fr = -1
            self.index = index
     
     
    N, Q = map(int, input().split())
    node = [Node(i) for i in range(N)]
    for i in range(N - 1):
        fr, to = map(int, input().split())
        node[to - 1].fr = fr - 1
     
    for i in range(Q):
        fr, c = map(int, input().split())
        node[fr- 1].count += c
     
    for i in range(N):
        x = node[i].count
        next = node[i].fr
        while next != -1:
            x += node[next].count
            next = node[next].fr
        if not i == N:
            print(x, end=' ')
        else:
            print(x)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**6)

n, q = map(int, sys.stdin.readline().strip())

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

plus = [0] * (n + 1)

for _ in range(q):
  p, x = map(int, sys.stdin.readline().strip())
  plus[p] += x

def calc(num, path, plus, parent):
  for i in path[num]:
    if i == parent:
      continue

    plus[i] += plus[num]
    calc(i, path, plus, num)

calc(1, path, plus, 0)

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

Submission status: Runtime Error

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

#a=[0]*n
#b=[0]*n
tree = {}
for i in range(1,n+1):
  tree[i] = []

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

  
####################################
def cout(*args):
  arglist = []
  for arg in args:
    if hasattr(arg, "__iter__"):
      arglist.extend(arg)
    else:
      arglist.append(arg)
      
  arglist = list(map(str, arglist))
  print(" ".join(arglist))
  
def all_idx(tree, i):
  ret = []
  
  tmp = tree[i]
  if tmp==[]:
    return ret
  else:
    for t in tmp:
      ret = ret + [t] + all_idx(tree, t)
    return ret

######################################

ret = [0 for i in range(n+1)]

for i in range(q):
  p,x = map(int, input().split())
  tmp_idx = [p] + all_idx(tree, p)
  ret = [ret[i]+x if (i in tmp_idx) else ret[i] for i in range(n+1)]

cout(ret[1:])

Submission status: Runtime Error

Solution code:
t = {}

def dp(tt, i):
    global t
    tt[1] = tt[1] + i
    for a in tt[0]:
        dp(t[a], i)

n, q = map(int, input().split())
for i in range(n - 1):
    a, b = map(int, input().split())
    if a in t:  t[a][0].append(b)
    else:       t[a] = [[b], 0]
    if b not in t: t[b] = [[], 0]

p = []
for i in range(q):
    a, b = map(int, input().split())
    p.append([a, b])


for i in p:
    dp(t[i[0]], i[1])

l = []
for i in sorted(t):
    l.append(t[i][1])
print(" ".join(map(str, l)))

Submission status: Runtime Error

Solution code:

N,Q = (int(i) for i in input().split())
hen = {}
value = [0] * N
for i in range(0,N-1):
    a,b = (int(i) for i in input().split())
    if a in hen:
        hen[a].append(b)
    else:
        hen[a] = [b]
#print(hen)

def add(p,x):
    #value[p-1] = value[p-1] + x
    if p in hen:
        for i in hen[p]:
            value[i-1] = value[i-1] + x
            add(i,x)

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


add(1,value[0])
print(' '.join(map(str,value)))

Submission status: Runtime Error

Solution code:
import numpy as np
N,Q = map(int,input().split())
ans = np.array([0]*N)
test = np.array([1]*N)
test = np.diag(test)
for i in range(1,N):
    ai,bi = map(int,input().split())
    test[ai-1,bi-1]+=1

for k in reversed(range(N)):
    check = np.where(test[k] > 0)
    test[k]+=np.sum(test[check],axis=0)
test = np.where(test > 0,1,0)

for j in range(Q):
    pj,xj = map(int,input().split())
    ans += test[pj-1]*xj

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

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self):
        self.num = 0
        self.node_list = []

    def add(self, add_num):
        self.num += add_num
        for node in self.node_list:
            node.add(add_num)

setting_str = input()
setting_str_list = setting_str.split(" ")
N = int(setting_str_list[0])
Q = int(setting_str_list[1])
node_dict = {}
for i in range(1, N+1):
    node_dict[i] = Node()

for i in range(N-1):
    num_str  = input()
    num_str_list = num_str.split(" ")
    a = int(num_str_list[0])
    b = int(num_str_list[1])
    node_dict[a].node_list.append(node_dict[b])

for i in range(Q):
    num_str = input()
    num_str_list = num_str.split(" ")
    a = int(num_str_list[0])
    b = int(num_str_list[1])
    node_dict[a].add(b)

result = ""
for node in node_dict.values():
    result += str(node.num) + " "
result = result[:-1]
print(result)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def search(tree, target):
    subs = [target]
    for node in tree[target]:
        subs += search(tree, node)
    return subs
N, Q = map(int, input().split())

tree = defaultdict(list)
parent = [None] * N
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a] += [b]

subs =[None] * (N + 1)
for i in range(1, N + 1):
    subs[i] = search(tree, i)

values = [0] * (N + 1)
for i in range(Q):
    p, q = map(int, input().split())
    for j in subs[p]:
        values[j] += q

values = map(str, values[1:])
print(" ".join(values))

Submission status: Runtime Error

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

def find(nodes, dp, key):
  if len(nodes[key]) == 1:
    return [key]
  else:
    x = [key]
    for node in nodes[key]:
      if key != node:
        if node in dp:
          x.extend(dp[node])
        else:
          x.extend(find(nodes, dp, node))
    return x

nodes = {}
nodes_p = {}
for _ in range(N-1):
  a,b = map(int, input().split())
  if a in nodes:
    nodes[a].append(b)
  else:
    nodes_p[a] = 0
    nodes[a] = [a]
    nodes[a].append(b)

  if b not in nodes:
    nodes_p[b] = 0
    nodes[b] = [b]

dp = {}
for _ in range(Q):
  p, x = map(int, input().split())
  if p in dp:
    for key in dp[p]:
      nodes_p[key] += x
  else:
    dp[p] = find(nodes, dp, p)
    for key in dp[p]:
      nodes_p[key] += x

print(" ".join(map(str, [ v for v in nodes_p.values()])))

Submission status: Runtime Error

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

T = dict()
V = np.zeros(N+1)

a, b = map(int, input().split())
T[a] = []
T[a].append(b)

for i in range(N-2):
	a, b = map(int, input().split())
	if a not in T.keys():
		T[a] = []
	T[a].append(b)

def change(a, v):
	V[a] += v
	temp = T.get(a)
	if(temp==None):
		return
	else:
		for x in temp:
			change(x, v)
		

for i in range(Q):
	a, v = map(int, input().split())
	change(a, v)

print(' '.join([str(int(x)) for x in V[1:]]))

Submission status: Runtime Error

Solution code:
N,Q = map(int, input().split())
import copy
es = {}
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    if a in es:
        es[a].append(b)
    else:
        es[a] = [b]


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

ans = [0] * N
visited = [False] * N
ans[0] = point_root[0]
visited[0] = True
def solve(node, point):
    ans[node] = point
    visited[node] = True
    if all(visited) == True:
        print(*ans)
        exit()

    if es.get(node, None) != None:
        next_nodes = copy.deepcopy(es[node]) # これからポイントを足し行くやつら

        for i in next_nodes:
            solve(i, point+point_root[i])
solve(0, point_root[0])

Submission status: Runtime Error

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


class Graph:
    def __init__(self):
        """ ノードのつながりを辞書型で表現する """
        self.adjacency_dict = {}
        # 頂点カウンターを用意しておく
        self.node_counter = [0 for _ in range(N)]
        # ノードを初期化する
        for v in range(1, N + 1):
            self.adjacency_dict[v] = []

    def add_edge(self, v1, v2):
        """ ノード同士をつなぐ。"""
        # 無向グラフの場合は双方向。もし有向グラフなら片側のみ。
        self.adjacency_dict[v1].append(v2)

    def dfs_rec(self, start, visited=None):
        """再帰的に探索して自身と配下の頂点リストを返す"""
        if visited is None:
            visited = []
        visited.append(start)
        for v in self.adjacency_dict[start]:
            if v in visited:
                continue
            self.dfs_rec(v, visited)
        return visited

    def add_nodes_counter(self, start, x):
        """指定した頂点配下のカウンターをxだけ増やす"""
        vertexes = self.dfs_rec(start)
        # print(f"カウントアップ対象の頂点: {vertexes}")
        for n in vertexes:
            self.node_counter[n - 1] += x


# インスタンス生成
g = Graph()

# 辺のデータを取得
edges = [list(map(int, input().split())) for _ in range(N - 1)]
for a, b in edges:
    g.add_edge(a, b)

# print(f"グラフチェック: {g.adjacency_dict}")

# 操作のデータを取得
operations = [list(map(int, input().split())) for _ in range(Q)]
# print(f"操作チェック: {operations}")

for v, x in operations:
    # print(f"操作: {v, x}")
    g.add_nodes_counter(v, x)

print(" ".join(map(str, g.node_counter)))

Submission status: Runtime Error

Solution code:
def list_add_figure(num_list, focus_figure, add_figure):
  if num_list == []:
    #print("focus_figure",focus_figure)
    figure[focus_figure] += add_figure
    return
  else:
    for i in range(len(num_list)):
      list_add_figure(tree[num_list[i]], num_list[i], add_figure)
    figure[focus_figure] += add_figure
    return  

n, q = map(int, input().split())
tree = []
figure = [0]*n
#print(figure)
for i in range(n):
  tree.append([])
  
for i in range(n-1):
  in_a_b  = list(map(int, input().split()))
  tree[in_a_b[0] - 1].append(in_a_b[1] -1)
#print("tree")
#print(tree)
for i in range(q):
  in_p_x = list(map(int, input().split()))
  list_add_figure(tree[in_p_x[0] - 1], in_p_x[0] - 1, in_p_x[1])
  #もし見ているリストが空ならその頂点に値を代入して
    #breakそうでなければ一つ取り出してその頂点に飛ぶ
print(*figure)

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
ki=[[] for i in range(n+1)]
ki[0]="null"
 
for i in range(n-1):
    a,b=map(int,input().split())
    ki[a].append(b)
 
scores=[0 for i in range(n+1)]
scores[0]="null"
for i in range(q):
    p,x=map(int,input().split())
    scores[p]+=x
 
 
ans=[0 for i in range(n+1)]
ans[0]="null"
point=0
 
 
def tansa(n,point):
    point+=scores[n]
    for p in ki[n]:
        try:
            tansa(p,point)
        except:
            pass
    else:
        ans[n]=point
        
tansa(1,0)
 
ans=ans[1:]
ans=[str(i) for i in ans]
print(" ".join(ans))

Submission status: Runtime Error

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

class Node:
    def __init__(self, root):
        self.root = root
        self.children = []
        self.val = 0

    def add_child(self, child_node):
        self.children.append(child_node)
        if self.root is not None:
            self.root.add_child(child_node)

nodes = [None] * n
nodes[0] = Node(None)

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

for j in range(q):
    p, x = map(int, input().split())
    node = nodes[p - 1]
    node.val += x
    children = node.children
    for child in children:
        child.val += x

res = []
for node in nodes:
    res.append(str(node.val))
print(" ".join(res))

Submission status: Runtime Error

Solution code:
# D

def add_value(p, x):
    value[p-1]+=x
    if p in data:
        for key in data[p]:
            add_value(key, x)

N, Q = map(int, input().split())
a=[]
b=[]

data = {}
for i in range(N-1):
    a, b = map(int, input().split())
    if not (a in data):
        data[a] = []
    data[a].append(b)

value = [0]*N

p = []
x = []
for i in range(Q):
    p_tmp, x_tmp = map(int, input().split())
    add_value(p_tmp, x_tmp)

for i in value:
    print("{} ".format(i), end="")