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 = [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
    for j in list(tree[p-1]):
        ans[j-1]+=x
print(*ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

n,q=map(int, input().split())
ab=[]
for _ in range(n):
    ab.append([])
for _ in range(n-1):
    a,b=map(int, input().split())
    ab[a-1].append(b)
px=[0]*n
for _ in range(q):
    p,x=map(int, input().split())    
    px[p-1]+=x

def func(p, now):
    global res
    res[p-1]+=px[p-1]+now
    for i in ab[p-1]:
        func(i, res[p-1])

res=[0]*n

func(1, 0)

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

Submission status: Runtime Error

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

# pt, oya, ko
ki = [[0, 0, []] for i in range(N)]

def dfs(target, p, x):
  if len(ki[p-1][2]) != 0 :
  	target.extend(ki[p-1][2])
  ki[p-1][0] += x
  target.pop(0)
  
  if len(target) == 0:
    return
  else:
  	dfs(target, target[0], x)

for i in range(N-1):
  a, b = map(int, input().split())
  ki[a-1][2].append(b)
  ki[b-1][1] = a
  
for i in range(Q):
  p, x = map(int, input().split())
  
  target = [p]
  dfs(target, p, x)
  
print(ki[0][0], end="")
for i in ki[1:]:
  print(" " + str(i[0]), end="")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
class AdjacencyList(object):
    def __init__(self):
        self.List = {}

    def addEdge(self, fromVertex, toVertex):
        # check if vertex is already present
        if fromVertex in self.List.keys():
            self.List[fromVertex].append(toVertex)
        else:
            self.List[fromVertex] = [toVertex]


if __name__ == '__main__':
    #al = AdjacencyList()
    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())
        #al.addEdge(num1,num2)
        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:
#             for j in al.List.keys():
#                 if(i in al.List[j]):
#                     break
            ans = dp[parent[i]]+sum(counter[i])
            print(ans,end=" ")
            dp.append(ans)

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
Ki_p = [0 for i in range(N+1)]
Ki_c = [[] for i in range(N+1)]
Ki_co = [0 for i in range(N+1)]

def answer(vi,ans):
    ans[vi] = Ki_co[vi] + ans[Ki_p[vi]]
    for v in Ki_c[vi]:
        answer(v,ans)    

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

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

ans = [0 for i in range(N+1)]
answer(1,ans)

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

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

connections = [[] for i in range(N+1)]

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

add_list = [0]*(N+1)

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

ans = [0]*(N+1)
checked = [False]*(N+1)
def add(point,num):
    ans[point] += num
    checked[point] = True
    for c in connections[point]:
        if checked[c]:
            continue
        else:
            add(c,num+add_list[c])
        
add(1,add_list[1])

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, Q = map(int, input().split())
#a = [0] * (N - 1)
#b = [0] * (N - 1)
p = [0] * Q
x = [0] * Q
link = [[] for _ in range(N)]
children = [[i] for i in range(N)]
arrived = [0] * N

def dps(v):
	arrived[v] = 1
	tmp_list = []
	
	for i in link[v]:
		if arrived[i] == 0:
			tmp_list.append(dps(i))
			
	for j in tmp_list:
		for k in j:
			children[v].append(k)
		
	return children[v]

for i in range(N - 1):
	#a[i], b[i] = map(int, input().split())
	a, b = map(int, input().split())
	a -= 1
	b -= 1
	link[a].append(b)
	link[b].append(a)
	
for i in range(Q):
	tmp_p, x[i] = map(int, input().split())
	p[i] = tmp_p - 1
	
dps(0)
ans = [0] * N

for i in range(Q):
	for j in children[p[i]]:
		ans[j] += x[i]
		
for i in range(N):
	print(ans[i], end=' ')

Submission status: Runtime Error

Solution code:
import sys

MAX = 100002

sys.setrecursionlimit(MAX)

def add_num(nn, x):
    #print(nn)
    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:
class node:
    def __init__(self, num):
        self.num = num
        self.count = 0
        self.connect = []

def add_conect(a, b):
    a.connect.append(b)

def child_node_plus(node,x):
    node.count += x
    for n in node.connect:
        child_node_plus(n,x)


def print_tree(node):
    print(node.count,end=" ")
    for n in node.connect:
        print_tree(n)


all_node = {}
N,Q = map(int,input().split())
for i in range(1,N):
    a,b = map(int,input().split())
    if not a in all_node:
        all_node[a] = node(a)
    if not b in all_node:
        all_node[b] = node(b)
    add_conect(all_node[a],all_node[b])

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

print_tree(all_node[1])
print()

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())
    #hen[a-1].append(b)
    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 sys
input = sys.stdin.readline

N, Q = [int(x) for x in input().strip().split()]
res = [0 for _ in range(N)]
tree = [[] for _ in range(N)]
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    tree[a-1].append(b)

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

def f(n, c):
    res[n-1] += c
    if len(tree[n-1])!=0:
        for num in tree[n-1]:
            f(num, res[n-1])

f(1, 0)
print(*res)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
ans = [0] * n
ki = {1 : [1]}
for _ in range(n - 1):
  a, b = map(int, input().split())
  ki[b] = ki[a] + [b]
ki = ki.values()

for _ in range(q):
  c, d = map(int, input().split())
  for n, k in enumerate(ki):
    if c in k:
      ans[n] += d
ans2 = ''
for e in ans:
  ans2 += str(e) + ' '
print(ans2[:-1])

Submission status: Runtime Error

Solution code:
from sys import stdin


class Node:
    def __init__(self, num):
        self.num = num
        self.children = []
        self.value = 0

    def append(self, child):
        self.children.append(child)

    def add_value(self, value):
        self.value += value


def spam(nodes, dic1, dic2, flags, num):
    index = num - 1
    flags[index] = True
    node = nodes[index]
    nums = dic1.get(num, []) + dic2.get(num, [])
    nums = [x for x in nums if not flags[x - 1]]
    for n in nums:
        node.append(nodes[n - 1])
        spam(nodes, dic1, dic2, flags, n)


def ham(nodes, num, value):
    index = num - 1
    node = nodes[index]
    node.add_value(value)
    for n in node.children:
        ham(nodes, n.num, value)


def main():
    N, Q = [int(x) for x in stdin.readline().rstrip().split()]
    ab = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N - 1)]
    px = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(Q)]
    dic1 = {}
    dic2 = {}
    flags = [False for _ in range(N)]
    for a, b in ab:
        if a in dic1:
            dic1[a].append(b)
        else:
            dic1[a] = [b]
        if b in dic2:
            dic2[b].append(a)
        else:
            dic2[b] = [a]
    nodes = [Node(i + 1) for i in range(N)]
    spam(nodes, dic1, dic2, flags, 1)
    for p, x in px:
        ham(nodes, p, x)
    for n in nodes:
        print(n.value, end=' ')
    print('')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,q = map(int,input().split())
c = [list(input().split()) for i in range(n-1)]
y = [list(input().split()) for i in range(q)]
a = list(c[j][0] for j in range(n-1))
b = list(c[j][1] for j in range(n-1))
p = list(y[j][0] for j in range(q))
x = list(y[j][1] for j in range(q))
count = [0 for i in range(n)]
for i in range(q):
    count[int(p[i])-1]+=int(x[i])
for i in range(n-1):
    count[int(b[i])-1]+=count[int(a[i])-1]
print(*count,' ')

Submission status: Runtime Error

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

PX = {str(i): 0 for i in range(1, N+1)}
for _ in range(Q):
    p, x_str = input().split()
    PX[p] += int(x_str)


node_cnts = [0] * (N+1)


def gen_subtree_nodes(node, count):
    node_cnts[int(node)] = count
    for n in nodes.get(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:
N,Q = map(int,input().split())
children_list = [0]*N
values = [0]*N
def dfs(children_list,values,p,x):
    values[p] += x
    if children_list[p] == 0:
        return
    else:
        for child in children_list[p]:
            dfs(children_list,values,child,x)

for _ in range(N-1):
    a,b = map(int,input().split())
    if children_list[a-1]==0:
        children_list[a-1] = [b-1]
    else:
        children_list[a-1].append(b-1)
for _ in range(Q):
    p,x = map(int,input().split())
    dfs(children_list,values,p-1,x)
print(*values,sep=" ")

Submission status: Runtime Error

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

ab=[[] for _ in range(n)]
arr=[0 for _ in range(n)]
cache=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  ab[a-1].append(b-1)

px=[list(map(int,input().split())) for _ in range(q)]
  
  
def search(tree, root):
  arr=[]
  children=tree[root]
  if children == []:
    return None
  else:
    arr.extend(children)
    for child in children:
      ret=search(tree, child)
      if ret is not None:
        arr.extend(ret)    
  return arr


for p,x in px:
  if cache[p-1] == []:
    children=search(ab,p-1)
    if children is not None:
      children=[p-1]+children
    else:
      children=[p-1]
    cache[p-1]=children
    for child in children:
      arr[child]+=x
  else:
    for child in cache[p-1]:
      arr[child]+=x    
print(*arr)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

n, q = map(int, input().split())
dic = {}
dic2 = {}

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

for _ in range(q):
    a, b = map(int, input().split())
    if not (a in dic2):
        dic2[a] = 0
    dic2[a] = dic2[a]+b

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


def add_v(num, value):
    v_list[num - 1] = v_list[num - 1] + value
    if num in dic:
        for root in dic[num]:
            add_v(root, value)


for i in dic2:
    add_v(i, dic2[i])


print(*v_list)

Submission status: Runtime Error

Solution code:
np = input().split()
N = int(np[0])
Q = int(np[1])


class Node:

    def __init__(self, number_id):
        self.number_id = number_id  # int
        self.connection_list = []  # つながりのあるNodeのリスト
        # self.parent_id = None
        # self.children_list = []
        self.add_number = 0

    def add_add_number(self, add_n):
        self.add_number += add_n

    def add_connection(self, connect_node):
        self.connection_list.append(connect_node)

    def set_tree(self, parent_id, add_n):
        # self.parent_id = parent_id
        self.add_number += add_n
        for child_node in self.connection_list:
            if child_node.number_id != parent_id:
                # self.children_list.append(child_d)
                child_node.set_tree(self.number_id, self.add_number)
        # self.connection_list = []
        # return self.children_list


# 読み込んでグラフを作成
# ノード間のつながりができてから，親と子を決定する
node_list = [Node(i+1) for i in range(N)]
for _ in range(N-1):
    ab = input().split()
    a = int(ab[0])
    b = int(ab[1])
    a_node = node_list[a-1]
    b_node = node_list[b-1]
    a_node.add_connection(b_node)
    b_node.add_connection(a_node)

# ノードごとに足される数を保存する
for _ in range(Q):
    px = input().split()
    p = int(px[0])
    x = int(px[1])
    p_node = node_list[p-1]
    p_node.add_add_number(x)
# のーど1からノードにあるadd numberを足していく
# node 1 から親子関係を決定する
node_one = node_list[0]
node_one.set_tree(0, 0)
# children_dictionary = {}  # key:parent id, value: children list
# key_list = [1]
# child_l = node_one.set_tree(0, 0)
# children_dictionary[1] = child_l
# counter = 0
# while len(children_dictionary) != 0:
#     # key = sorted(children_dictionary.keys())[0]
#     key = key_list.pop(0)
#     parent_add_n = node_list[key-1].add_number
#     children_l = children_dictionary.pop(key)
#     for child in children_l:
#         counter += 1
#         if counter > N:
#             exit()
#         new_children = node_list[child-1].set_tree(key, parent_add_n)
#         children_dictionary[child] = new_children
#         key_list.append(child)

# 出力
for node in node_list:
    print(node.add_number, end=" ")
print("")

Submission status: Runtime Error

Solution code:
def stdin():
    return map(int, input().split())

N, Q = stdin()

# vertexes list contained in the ith subtree root
tree = [[] for _ in range(N)]

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

counter = [0 for _ in range(N)]

def dfs(p: int, x: int):
    counter[p] += x

    vertexes = tree[p]
    for v in vertexes:
        dfs(v, x)

for i in range(Q):
    _p, _x = stdin()
    dfs(_p-1, _x)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

N,Q = map(int,input().split())
ab_list = [tuple(map(int,input().split())) for _ in range(N-1)]
px_list = [tuple(map(int,input().split())) for _ in range(Q)]

px_dict = {}
for p, x in px_list:
    if p in px_dict:
        px_dict[p] += x
    else:
        px_dict[p] = x

ab_dict = {}
for a,b in ab_list:
    if a in ab_dict:
        ab_dict[a].append(b)
    else:
        ab_dict[a] = [b]

scores = [0 for _ in range(N+1)] # 1子おおい

def add_cnt(v, score):
    # pxdictから持ってきてスコアを足す
    if v in px_dict:
        score += px_dict[v]
    # スコアを足さないこともある
    
    #今いる頂点に現在のスコアをめも
    scores[v] = score
    
    # 繋がっている頂点に今のスコアを投げる
    if v in ab_dict:
        for b in ab_dict[v]:
            add_cnt(b,score)

add_cnt(1,0)

print(" ".join(list(map(str,scores[1:]))))

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())
    ab.append([a,b])
    con[b-1] = a

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

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


for i in qx:
    dfs(i[0], i[1])

print(*ans)

Submission status: Runtime Error

Solution code:
def add_num(nn, x):
    #print(nn)
    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])

MAX = 100002

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)

"""
    print(Tree)
    print(a)
    print(b)
    print(Tree[a])
    print(Tree[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 = map(int, input().split())
tree = [list(map(int, input().split())) for i in range(N-1)]
counter = [list(map(int, input().split())) for i in range(Q)]
dic = {}
for i in tree:
  try:
    dic[i[0]].append(i[1])
  except KeyError:
    dic[i[0]] = [i[1]]
keys = dic.keys()
for i in tree:
  if i[1] not in keys:
    dic[i[1]] = []
q = {i: 0 for i in dic.keys()}
 
def child_sum(q,v, child):
  if child == []:
    #print('test', q, v, child)
    return q
  else:
    for j in child:
      
      q[j] += v
      child = dic[j]
      #print('test2', j, v, child)
      q = child_sum(q, v, child)
  return q
    
for i, v in counter:
  q[i] += v
  child = dic[i]
  #print(q, i, child)
  q = child_sum(q, v, child)
print(' '.join([str(i) for i in q.values()]))

Submission status: Runtime Error

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

    def add_child(self, node):
        self.children.append(node)

    def add_score(self, score):
        self.score += score


class Tree:
    def __init__(self):
        self.root = Node(1)
        self.nodes = { 1: self.root }

    def add_node(self, parent_num, num):
        parent = self.nodes[parent_num]
        child = Node(num)
        parent.add_child(child)
        self.nodes[num] = child

    def find_node(self, num):
        return self.nodes[num]

    @classmethod
    def add_score(cls, node, score):
        node.add_score(score)
        for n in node.children:
            cls.add_score(n, score)

import sys
sys.setrecursionlimit(4100000)
N, Q = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(1, N):
    A[i], B[i] = map(int, input().split())

P = [0] * (Q+1)
X = [0] * (Q+1)
for i in range(1, Q+1):
    P[i], X[i] = map(int, input().split())

tree = Tree()
for i in range(1, N):
    tree.add_node(A[i], B[i])

for i in range(1, Q+1):
    node = tree.find_node(P[i])
    Tree.add_score(node, X[i])

for i in range(1, N+1):
    node = tree.find_node(i)
    print(node.score, end=' ')

Submission status: Runtime Error

Solution code:
def h(p,x):
    c[p]+=x
    if t[p]!=[]:
        for i in t[p]:
            h(i,x)

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

for i in range(q):
    p,x=map(int,input().split())
    h(p,x)

print(*c[1:])

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 = {
    1: Node(None)
}

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

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


arr = [None] * n
for k, v in nodes.items():
    arr[int(k) - 1] = v

res = []
for item in arr:
    res.append(item.val)
print(" ".join(list(map(str, res))))

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
edges = [[] for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p - 1] += x

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

def rec(pos, val):
    val += cnt[pos]
    ans[pos] = val
    for to in edges[pos]:
        if not visit[to]:
            visit[to] = True
            rec(to, val)

visit[0] = True
rec(0, 0)
for x in ans[:-1]:
    print(x, end=' ')
print(ans[-1])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, Q = map(int, input().split())
#a = [0] * (N - 1)
#b = [0] * (N - 1)
p = [0] * Q
x = [0] * Q
link = [[] for _ in range(N)]
children = [[i] for i in range(N)]
arrived = [0] * N

def dps(v):
	arrived[v] = 1
	tmp_list = []
	
	for i in link[v]:
		if arrived[i] == 0:
			tmp_list.append(dps(i))
			
	for j in tmp_list:
		for k in j:
			children[v].append(k)
		
	return children[v]

for i in range(N - 1):
	#a[i], b[i] = map(int, input().split())
	a, b = map(int, input().split())
	a -= 1
	b -= 1
	link[a].append(b)
	link[b].append(a)
	
for i in range(Q):
	tmp_p, x[i] = map(int, input().split())
	p[i] = tmp_p - 1
	
dps(0)
ans = [0] * N

for i in range(Q):
	for j in children[p[i]]:
		ans[j] += x[i]
		
for i in range(N):
	print(ans[i], end=' ')

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):
    if not tree[x-1]:
        return
    else:
        for i in list(tree[x-1]):
            if not tree[i-1]:
                continue
            tree[x-1] |= (tree[i-1])
            add_l(i)
            
add_l(1)
#print(tree)

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

Submission status: Runtime Error

Solution code:
def add_value(tree, p, x):
    tree[p]["value"] += x
    if len(tree[p]["node"]) == 0:
        return 0
    for next_node_index in tree[p]["node"]:
        add_value(tree, next_node_index, x)

N, Q = map(int, input().split(" "))
tree = {}
for _ in range(N-1):
    a, b = map(int, input().split(" "))
    if not a in tree:
        tree[a] = {"value": 0, "node":[]}
    tree[a]["node"].append(b)

    if not b in tree:
        tree[b] = {"value": 0, "node":[]}

for _ in range(Q):
    p, x = map(int, input().split(" "))
    add_value(tree, p, x)

for i in range(1, N):
    print(tree[i]["value"], end=" ")
print(tree[N]["value"])

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 dfs(G, v=0, d=0):
#     G[v].depth = d
#     for child in G[v].children:
#         dfs(G, child, d+1)

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

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
    add_count(G, p, x)

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

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())
    #hen[a-1].append(b)
    if a in hen:
        hen[a].append(b)
    else:
        hen[a] = [b]
#print(hen)

def add(p,x,hen,value):
    #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,hen,value)

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

#for i in range(0,N):
#    if value[N-i-1] != 0:
#        add(N-i,value[N-i-1],hen,value)
add(1,value[0],hen,value)
print(' '.join(map(str,value)))

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 10)

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

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)

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


# make a function
def add(lst, p, x):
    if child[p] == []:
        lst[p] += x
    else:
        lst[p] += x
        for v in child[p]:
            add(lst, v, x)

## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    add(count, p, x)
    
print(' '.join(map(str, count)))

Submission status: Runtime Error

Solution code:
def repeat(index, cost):
    if index in dict_tree:
        for k in dict_tree[index]:
            cost.append(k)
                
            repeat(k, cost)
    else:
        return

n, q = map(int, input().split())
dict_tree = {}
for i in range(n-1):
    a, b = map(int, input().split())
    if a in dict_tree:
        dict_tree[a].append(b)
    else:
        dict_tree[a] = [b]
point = [0] * n

for j in range(q):
    p, x = map(int, input().split())
    cost = []
    cost.append(p)
    repeat(p, cost)
    cost = set(cost)
    for l in cost:
        point[l-1] += x
for m in point:
    print(m)

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)

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

add_lis = [0] * N
ans_lis = [0] * N
v_lis = [None] * N
ab_lis = []

for i in range(N-1):
	a = []
	v_lis[i] = a

for i in range(N-1):
	ai,bi = map(int, input().split())
	ab_lis.append((ai,bi))
	v_lis[ai-1].append(bi-1)

for i in range(Q):
	pi,xi = map(int, input().split())
	add_lis[pi-1] += xi

def traverse(i, add_v):
	ans_lis[i] = add_lis[i] + add_v
	if v_lis[i] != None:
		for n in v_lis[i]:
			traverse(n, ans_lis[i])
	return

traverse(0, 0)

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

Submission status: Runtime Error

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

cnt = [0] * n
tree = {}
subt = {}
for i in range(n-1):
    tree.setdefault(ab[i][0], []).append(ab[i][1])

def adder(node, value):
    cnt[node-1] += value
    if node in tree:
        for i in tree[node]:
            adder(i, value)
for i in range(q):
    adder(px[i][0], px[i][1])
print(" ".join(map(str, cnt)))

Submission status: Runtime Error

Solution code:
import numpy as np

temp=list(map(int, input().split()))
N=temp[0]
Q=temp[1]

matrix=np.zeros((N, N), dtype=int)
for i in range(N):
  matrix[i, i]=1

for i in range(N-1):
  temp=list(map(int, input().split()))
  matrix[int(temp[0]-0.5), int(temp[1]-0.5)]=1
  
index=int(N-0.5)
while index>0:
  matrix[index, :]+=np.sum(matrix*matrix[index, :].reshape(-1, 1), axis=0)
  index=int(index-0.5)
  
matrix[0, :]+=np.sum(matrix*matrix[0, :].reshape(-1, 1), axis=0)

matrix[matrix>0]=1

counter=np.zeros(N, dtype=int)
for i in range(Q):
  temp=list(map(int, input().split()))
  counter+=matrix[int(temp[0]-0.5), :]*temp[1]
  
print(' '.join(map(str, map(int, counter.tolist()))))