Problem:


Score : 400 points

Problem Statement

Given is a rooted tree with N vertices numbered 1 to N.
The root is Vertex 1, and the i-th edge (1 \leq i \leq N - 1) connects Vertex a_i and b_i.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0.

Now, the following Q operations will be performed:

Operation j (1 \leq j \leq Q): Increment by x_j the counter on every vertex contained in the subtree rooted at Vertex p_j.

Find the value of the counter on each vertex after all operations.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq Q \leq 2 \times 10^5

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

Sample Input 1

4 3
1 2
2 3
2 4
2 10
1 100
3 1

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:

Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.

Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.

Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Sample Input 2

6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10

Sample Output 2

20 20 20 20 20 20



Sample input:
4 3
1 2
2 3
2 4
2 10
1 100
3 1


Sample output:
100 110 111 110

Submission status: Runtime Error

Solution code:
def f_d():
    def count_c(i, t, o, x):
        m = t[i]

        if len(m) == 0:
            return o

        for j in m:
            o[j-1] += x
            o = count_c(j, t, o, x)

        return o

    n, q = map(int, input().split())
    t = [[] for _ in range(n+1)]
    o = [0 for _ in range(n)]

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

    for _ in range(q):
        p, x = map(int, input().split())
        o[p-1] += x
        o = count_c(p, t, o, x)

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

if __name__ == "__main__":
    f_d()

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, id, parent=None):
        self.id = id
        self.parent = parent
        self.children = []

    def add(self, n):
        counter[self.id] += n
        for child in self.children:
            child.add(n)

N, Q = map(int, input().split())
tree = [None] * N
counter = [0] * N
tree[0] = Node(0) # root (1)
for i in range(N-1):
    a, b = map(int, input().split())
    tree[b-1] = Node(b-1, a-1)
    tree[a-1].children.append(tree[b-1])

for i in range(Q):
    p, x = map(int, input().split())
    tree[p-1].add(x)
    
print(' '.join(list(map(str, counter))))

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 = {}
for i in range(n-1):
    tree.setdefault(ab[i][0], [])
    tree[ab[i][0]].append(ab[i][1])

def pt(node):
    part = []
    if node in tree:
        for i in range(len(tree[node])):
            part += pt(tree[node][i])
    return [node] + part

for i in range(q):
    for j in pt(px[i][0]):
        cnt[j-1] += px[i][1]
print(" ".join(map(str, cnt)))

Submission status: Runtime Error

Solution code:
class root():
    def __init__(self):
        self.origin=set()
        self.dist=set()
        self.count=0
    def alignment(self,orig):
        if orig in self.dist:
            self.dist.remove(orig)
            self.origin.add(orig)
        for roots in self.dist:
            roots.alignment(self)
    def operation(self,x):
        self.count+=x
        for roots in self.dist:
            roots.operation(x)
num,q=map(int,input().split())
roots=[root() for _ in range(num)]
for _ in range(num-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    roots[a].dist.add(roots[b])
    roots[b].dist.add(roots[a])
roots[0].alignment(None)
for i in range(q):
    p,x =map(int,input().split())
    roots[p-1].operation(x)
print(" ".join([str(roots[i].count) for i in range(num)]))

Submission status: Runtime Error

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


ptree_map = {}


def gen_subtree_nodes(node):
    res = [int(node)]
    for n in nodes.get(node, []):
        subtree_nodes = gen_subtree_nodes(n)
        ptree_map[n] = subtree_nodes
        res += subtree_nodes

    return res


ptree_map['1'] = gen_subtree_nodes('1')

node_cnts = [0] * (N+1)
for _ in range(Q):
    p, x_str = input().split()
    x = int(x_str)
    for n in ptree_map[p]:
        node_cnts[n] += x

print(*node_cnts[1:])

Submission status: Runtime Error

Solution code:

N, Q = map(int, input().split())
A = []
B = []

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

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

T = {}
for i in range(len(A)):
    a = A[i]
    b = B[i]
    if a in T:
        T[a].append(b)
    else:
        T[a] = [b]

d = [0] * N

def inctree(p, x):
    d[p - 1] += x
    if p in T:
        l = T[p]
        for p2 in l:
            inctree(p2, x)

for i in range(len(P)):
    p = P[i]

    x = X[i]
    inctree(p, x)


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

Submission status: Runtime Error

Solution code:
from sys import stdin,stdout
I = lambda : map(int,stdin.readline().split())

def bfs(s):
	q = []
	visited = [0]*(N+1)
	d = [0]*(N+1)
	p = [0]*(N+1)

	q.append(s)
	visited[s] = True
	p[s] = -1
	i = 0
	while (len(q)>i):
		v = q[i]
		i+=1
		for u in adj[v]:
			if (not visited[u]):
				counter[u] += counter[v];
				visited[u] = True;
				q.append(u);
				d[u] = d[v] + 1;
				p[u] = v;

N = 10**5 + 2;

adj = []
for i in range(N+1):
	adj.append([])
counter = [0]*(N+1)

n,q = I()
for i in range (n-1):
	u, v = I()
	adj[u].append(v)
	adj[v].append(u)
print q
while q>0:
	p,x = I()
	print counter[2]
	counter[p] += x
	q-=1
bfs(1);
for i in range(1,n+1):
	print counter[i],

Submission status: Runtime Error

Solution code:
def get_verteces_in_subtree(vertex):
    children = tree_dictionary[vertex]
    if len(children) == 0:
        return [vertex]
    return [vertex] + sum([get_verteces_in_subtree(child) for child in children], [])
  
N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

tree_dictionary = {i: [] for i in range(1, N+1)}
for edge in edges:
    tree_dictionary[edge[0]].append(edge[1])
    
counts = [0] * N
for op in operations:
    top_vertex, value = op
    added_verteces = get_verteces_in_subtree(top_vertex)
    print(added_verteces)
    for v in added_verteces:
        counts[v-1] += value
       
output = ""
for c in counts:
    output += (str(c) + " ")
output = output[:-1]
print(output)

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 get_children(self):
        return self.children

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


class Tree:
    @classmethod
    def find_node(cls, node, num):
        if node.num == num:
            return node
        for n in node.children:
            if n.num == num:
                return n
            else:
                node = cls.find_node(n, num)
                if node:
                    return node
        return None

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

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

root = Node(1)
for i in range(1, N):
    node = Tree.find_node(root, A[i])
    node.add_child(Node(B[i]))

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

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,Q = inputMap()
	ki = [[] for _ in range(N)]
	kiki = []
	ans = [0 for _ in range(N)]

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

	for i,val in enumerate(ki):
		if len(val) == 0:
			kiki.append([])
			continue
		addd = val
		'''
		for vol in val:
			tmp = ki[vol]
			addd.extend(tmp)
		kiki.append(addd)
		'''

	for i in range(Q):
		p,x = inputMap()
		ans[p-1] += x
		for vol in kiki[p-1]:
			ans[vol] += x

	print(*ans)

if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

tree = [[] for _ in range(n)]
ret=[0]*n

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

#print(tree)

def counter(target,num):
    global ret
    ret[target]+=num
    if not tree[target]:
        return
    for i in tree[target]:
        counter(i,num)
for _ in range(q):
    p,x=map(int,input().split())
    counter(p-1,x)

print(*ret)

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 n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    tree[a] = tree.setdefault(a, []) + [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 n in tree:
        for num in tree[n]:
            f(num, res[n-1])

f(1, 0)
print(*res)

Submission status: Runtime Error

Solution code:

n,q = (int(i) for i in input().split())
hen = []
value = [0] * n
for _ in range(0,n):
    hen.append([])
for i in range(0,n-1):
    a,b = (int(i) for i in input().split())
    hen[a-1].append(b)
#print(hen)
def add(p,x,hen,value):
    value[p-1] = value[p-1] + x
    for i in hen[p-1]:
        add(i,x,hen,value)
for i in range(0,q):
    p,q = (int(i) for i in input().split())
    add(p,q,hen,value)
print(' '.join(map(str,value)))

Submission status: Runtime Error

Solution code:
# A, B = [int(i) for i in input().split(" ")]
# A = int(input())
# As = [int(i) for i in input().split(" ")]
# Ss = ["".join(sorted(input())) for _ in range(N)]
# from math import factorial
# def nCr(n, r): return factorial(n) // factorial(r) // factorial(n - r)
from collections import defaultdict 

N, Q = [int(i) for i in input().split(" ")]
edges = defaultdict(list)
for _ in range(N - 1):
    a, b = [int(i) for i in input().split(" ")]
    edges[a-1].append(b-1)
PX = defaultdict(int)
for _ in range(Q):
    p, x = [int(i) for i in input().split(" ")]
    PX[p-1] += x

ans = [0 for _ in range(N)]
def dfs(i, v):
    ans[i] += v
    for j in edges[i]:
        dfs(j, v + PX[j])
dfs(0, PX[0])
for a in ans:
    print(a, end=" ")

Submission status: Runtime Error

Solution code:
import math

node_len, ope_count = [int(x) for x in input().split()]

node_path = {}
node_weight = {}

if node_len == 1:
    parent= input()
    node_path[parent] = [parent]
    node_weight[parent] = 0

for i in range(node_len-1):
    parent, child = input().split()

    if i == 0:
        node_path[parent] = [parent]
        node_weight[parent] = 0

    if child not in node_path:
        node_path[child] = []
        node_weight[child] = 0
        if parent in node_path:
            node_path[child] = node_path[parent] + [child]

for i in range(ope_count):
    node_id, weight = input().split()
    node_weight[node_id] += int(weight)

for i in range(node_len):
    node_id = str(i + 1)
    value = sum([node_weight[id] for id in node_path[node_id]])
    print(value)
# print(node_path)
# print(node_weight)

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))
for i in range(N):
  matrix[i, i]=1

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

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

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(20000)

n, q = [int(x) for x in input().split()]

tree = [[] for _ in range(n + 1)]
cnt = [0] * (n + 1)

for _ in range(n - 1):
    a, b = [int(x) for x in stdin.readline().split()]
    tree[a].append(b)

def walk(p, x):
    cnt[p] += x
    for n in tree[p]:
        walk(n, x)

for _ in range(q):
    p, x = [int(x) for x in stdin.readline().split()]
    walk(p, x)

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

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
tree = {}
ans = {}


# p を頂点とする部分技にvを足す
def f(p, v):
    # print(tree)
    # print("p={}, v={}".format(p, v))
    ans[p] += v
    childs = tree.get(p)
    if not childs:
        return

    for c in childs:
        f(c, v)


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

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

# print(tree)

for _ in range(Q):
    p, x = map(int, input().split())
    # print('p x', p, x)
    f(p, x)

# print(ans)
for v in ans.values():
    print(v, end=" ")

Submission status: Runtime Error

Solution code:
n,q = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for _ in range(n-1)]
p = [[int(i) for i in input().split()] for _ in range(q)]

childs = collections.defaultdict(list)

for A,B in a:
    childs[A].append(B)

counter = collections.defaultdict(int)
affections = collections.defaultdict(list)

for A,B in p:
    if affections.get(A):
        for i in affections.get(A):
            counter[i] += B
    else:
        current = A
        aff = []
        tosee = [current]
        while len(tosee) != 0:
            temp = tosee.pop()
            aff.append(temp)
            for z in childs[temp]:
                tosee.append(z)
        affections[A] = aff
        for i in affections[A]:
            counter[i] += B
ans = ""
for i in range(1,n+1):
    ans += str(counter[i]) + " "
print(ans)

Submission status: Runtime Error

Solution code:
def add_node(tree, counter, value, node):
    counter[node - 1] += value
    if node in tree:
        for i in tree[node]:
            add_node(tree, counter, value, i)


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

tree = {}

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

ope = {}
for j in range(q):
    p, x = map(int, input().split())
    if p not in ope:
        ope[p] = x
    else:
        ope[p] += x

counter = [0] * n

for k in ope:
    add_node(tree, counter, ope[k], k)

print(*counter)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

res = [0]*(n+1)

def add_x(p, x):
    res[p] += x
    for child in tree[p]:
        add_x(child, x)

for i in range(1, n+1):
    add_x(i, adds[i])

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

Submission status: Runtime Error

Solution code:
import numpy as np

n, q = map(int, input().split())
g = np.zeros((n+1,n+1))

ans = np.zeros((n)) #Do not Foget -1


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

#for i in range(n+1):
#    print(g[0])


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

    stack = []
    ans[q-1] += x
    for i in range(n+1):
        if g[q][i] == 1:
            stack.append(i)

    while True:
        if len(stack) <= 0:
            break
        p = stack.pop(-1)
        #print(p)
        ans[p-1] += x
        for i in range(n+1):
            if g[p][i] == 1:
                stack.append(i)

ans_str = str(ans.astype(int))
ans_str = ans_str.replace('[','').replace(']','')
print(ans_str)

Submission status: Runtime Error

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

tree = [[] for _ in range(n)]
ret=[0]*n

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

#print(tree)

def counter(target,num):
    global ret
    ret[target]+=num
    if not tree[target]:
        return
    for i in tree[target]:
        counter(i,num)
for _ in range(q):
    p,x=map(int,input().split())
    counter(p-1,x)

print(ret)

Submission status: Runtime Error

Solution code:
node_len, ope_count = [int(x) for x in input().split()]

node_path = {}
node_weight = {}

if node_len == 1:
    parent, child = input().split()
    node_path[parent] = [parent]
    node_path[child] = [parent, child]
    node_weight[parent] = 0
    node_weight[child] = 0

for i in range(node_len-1):
    parent, child = input().split()

    if i == 0:
        node_path[parent] = [parent]
        node_weight[parent] = 0

    if child not in node_path:
        node_path[child] = []
        node_weight[child] = 0
        if parent in node_path:
            node_path[child] = node_path[parent] + [child]

for i in range(ope_count):
    node_id, weight = input().split()
    node_weight[node_id] += int(weight)

for i in range(node_len):
    node_id = str(i + 1)
    value = sum([node_weight[id] for id in node_path[node_id]])
    print(value)

Submission status: Runtime Error

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

for n in range(N-1):
    a,b = map(int, input().split())
    chi[a-1,b-1] = 1
    for i in range(N):
        if chi[i,a-1] > 0:
            chi[i] += chi[a-1] 
            
cnt = [0]*N   
for q in range(Q):
   p,x = map(int, input().split())
   cnt[p-1] += x
   for i in range(N):
       if chi[p-1,i] > 0:
           cnt[i] += x

for n in range(N):
    print(cnt[n], end=" ")

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, idx):
        self.idx = idx
        self.v = 0
        self.parent = None
        self.children = []
        self.connections = []
        self.level = -1

    def set_children(self):
        self.children = self.connections
        for node in self.connections:
            if self in node.connections:
                node.connections.remove(self)
            node.set_children()

    def add(self, x):
        self.v += x
        for c in self.children:
            c.add(x)

    def __str__(self):
        return str(self.v)


N, Q = [int(_) for _ in input().split()]
nodes = [Node(i) for i in range(1, N + 1)]

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

nodes[0].set_children()

# for n in nodes:
#     print(n.v, [str(c) for c in n.children])
for i in range(Q):
    p, x = [int(_) for _ in input().split()]
    nodes[p - 1].add(x)

print(*[n.v for n in nodes])

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, data):  # コンストラクタ
        self.data = data  # ノードがもつ数値
        self.child = []


def Plus(value, index, n):
    n[index].data += value
    if len(n[index].child) == 0:
        return
    for c in n[index].child:
        Plus(value, c, n)


N, Q = map(int, input().split())
n = [Node(0) for _ in range(N+1)]
for i in range(1, N):
    a, b = map(int, input().split())
    n[a].child.append(b)

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

for i in range(1, N+1):
    print(n[i].data)

Submission status: Runtime Error

Solution code:
import collections
N,Q=map(int,input().split())
A,B=[],[]
for i in range(N-1):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
P,X=[],[]
qy=collections.defaultdict(int)
for j in range(Q):
    p,x = map(int,input().split())
    P.append(p)
    X.append(x)
    qy[p]+=x



#print(list(zip(A,B)))
#print(list(zip(P,X)))


fts=collections.defaultdict(set)

#make links
for a, b in zip(A,B):
    fts[a].add(b)


counters = [0] * N

def add_points(p,x):
#    print(str(p)+','+str(x))
    if len(fts[p])==0:
        counters[p-1] += x
    else:
        counters[p-1] += x
        for a in fts[p]:
            add_points(a,x)

#calc points
for p,x in qy.items():
    add_points(p,x)
#    print(counters)

for c in counters:
    print(str(c)+' ',end='')
print()

Submission status: Runtime Error

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

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


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


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

    #A, B = [], []
    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)
        X.append(x)

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

    print(counter)

Submission status: Runtime Error

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

    stack = []
    ans[q-1] += x
    for i in range(n+1):
        if g[q][i] == 1:
            stack.append(i)

    while len(stack) > 0:
        #if len(stack) <= 0:
            #break
        p = stack.pop(-1)
        #print(p)
        ans[p-1] += x
        for i in range(n+1):
            if g[p][i] == 1:
                stack.append(i)

ans_str = str(ans.astype(int))
ans_str = ans_str.replace('[','').replace(']','')
print(ans_str)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
n, q = list(map(int, input().split()))
tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b= list(map(int, input().split()))
    tree[a-1].append(b-1)
s = [0] * n
for i in range(q):
    p, x = list(map(int, input().split()))
    s[p-1] += x


def f(n):
    global s
    for i in range(len(tree[n])):
        s[tree[n][i]] += s[n]
        f(tree[n][i])



f(0)

print(" ".join(list(map(str, s))))

Submission status: Runtime Error

Solution code:
N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
child_rel={}
parent_rel={}
for l in node_lst:
    src, dst = l[0], l[1]
    if src not in child_rel.keys():
        child_rel[src]=[dst]
    else:
        child_rel[src].append(dst)
    if src in parent_rel.keys():
        for e in parent_rel[src]:
            child_rel[e].append(dst)
    if dst not in parent_rel.keys():
        parent_rel[dst]=[src]
    else:
        parent_rel[dst].append(src)
print(child_rel)
print(parent_rel)
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
    if p in node_rel.keys():
        for e in node_rel[p]:
            cnt_lst[e-1]+=x
print(" ".join([str(c) for c in cnt_lst]))

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
link = dict()
counter = list([0]*n)
for i in range(n-1):
  a, b = map(int, input().split())
  if a in link:
    link[a].append(b)
  else:
    link[a] = [b]
def open(ps, x):
  if len(ps) > 0:
    for i in ps:
      counter[i-1] += x
      if i in link:
        open(link[i],x)
        
for i in range(q):
  p,pp = map(int, input().split())
  open([p], pp)

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

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-1]:
        c[a-1] += x
        add(a, x)

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

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.child = []
        self.point = 0

n, q = map(int, input().split())
#a, b, p, x = [], [], [], []
a, b = [None] * n, [None] * n
p, x = [None] * q, [None] * q

nodes = []
nodes.append(None)
ans = []

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

for i in range(q):
    temp1, temp2 = map(int, input().split())
    # p.append(temp1)
    # x.append(temp2)
    p[i] = temp1
    x[i] = temp2

# Make node list
for i in range(1, n+1):
    node = Node(i)
    nodes.append(node)

for i in range(n-1):
    nodeParent = nodes[a[i]]
    nodeChild = nodes[b[i]]
    nodeParent.child.append(nodeChild)

def printNode(node):
#    print(node.point)
    ans.append(node.point)
    for child in node.child:
        printNode(child)

def addCount(node, point):
    node.point += point
    for child in node.child:
        addCount(child, point)

for i in range(q):
    node = nodes[p[i]]
    addCount(node, x[i])

printNode(nodes[1])

print(' '.join([str(i) for i in ans]))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n,q=map(int,input().split())
Edges=defaultdict(list)
for _ in range(n-1):
    a,b=map(int,input().split())
    Edges[a-1].append(b-1)
Nodes = [0]*n
for _ in range(q):
    p,x=map(int,input().split())
    Nodes[p-1] += x

# A function used by DFS 
def dfs(v,preval,Edges,Nodes,visited): 
    # Mark the current node as visited and print it 
    visited[v]= True
    if v!=0:
        Nodes[v] += preval
    preval = Nodes[v]

    # Recur for all the vertices adjacent to this vertex 
    for i in Edges[v]: 
        if visited[i] == False: 
            dfs(i,preval,Edges,Nodes,visited) 
    return Nodes

visited = [False]*(len(Nodes)) 
Nodes = dfs(0,Nodes[0],Edges,Nodes,visited) 

print(" ".join(list(map(str,Nodes))))

Submission status: Runtime Error

Solution code:


def acinput():
    return list(map(int, input().split(" ")))


def search(n):
    global P
    for l in L[n]:
        res[l]=res[n]+P[l]
        search(l)

N,Q=acinput()

L=[[]for i in range(N+1)]
for i in range(N-1):
    tmp=acinput()
    L[tmp[0]].append(tmp[1])

P=[0]*(N+1)
for i in range(Q):
    tmp=acinput()
    P[tmp[0]]+=tmp[1]

res=[0]*(N+1)
res[1]=P[1]
search(1)

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

Submission status: Runtime Error

Solution code:
def adx(p,oya,tox,total):
  tox[p] += total
  total = tox[p]
  if(len(oya[p]) == 0):
    return 0

  else:
    for i in oya[p]:
      adx(i,oya,tox,total)

  return 0

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

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

hit = list(range(1,n+1))

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

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


adx(1,oya,tox,0)

tox.pop(0)

print(*tox)

Submission status: Runtime Error

Solution code:
n, q = [int(i) for i in input().split()]
a1 = {}
a2 = {}
for _ in range(n - 1):
    x, y = [int(i) - 1 for i in input().split()]
    if x in a1:
        a1[x].append(y)
    else:
        a1[x] = [y]
    if y in a2:
        a2[y].append(x)
    else:
        a2[y] = [x]
root = [-1] * n

def c(ind=0, ro=-1):
    global root
    if root[ind] != -1:
        return 0
    root[ind] = ro
    if ind in a1:
        for i in a1[ind]:
            if i!=0:
                c(i, ind)
    if ind in a2:
        for i in a2[ind]:
            if i!=0:
                c(i, ind)


c()
p = [0] * n
for _ in range(q):
    x, y = [int(i) for i in input().split()]
    p[x - 1] += y
r = []
for i in range(n):
    j = i
    k = 0
    while True:
        k += p[j]
        if j == -1:
            break
        j = root[j]
    r.append(str(k))
print(" ".join(r))

Submission status: Runtime Error

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

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

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

# print(edge)
# print(counter)

visited = [False] * (N + 1)
ans = [0] * (N + 1)

def dfs(fro, p):
    visited[fro] = True
    now = counter[fro] + p
    for to in edge[fro]:
        if not visited[to]:
            dfs(to, now)
    ans[fro] = now

dfs(1, 0)

print(*ans[1:])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n, q = map(int, input().split())
child_dict = defaultdict(set([]))
value_dict = defaultdict(lambda: 0)
for _ in range(n - 1):
    a, b = map(int, input().split())
    child_dict[a].add(b)
import copy
for _ in range(q):
    c, d = map(int, input().split())
    value_dict[c] += d
    child = child_dict[c]
    while len(child) > 0:
        k = []
        for i in child:
            value_dict[i] += d
            k.extend(child_dict[i])
        child = copy.deepcopy(k)
ans = [value_dict[i] for i in range(1 ,n+1)]
print(*ans)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
tree = [[] for i in range(N)]
for i in range(N-1):
    ai, bi = map(int, input().split())
    ai -= 1
    bi -= 1
    tree[ai].append(bi)
point = [0] * N
for j in range(Q):
    pi, xi = map(int, input().split())
    pi -= 1
    point[pi] = point[pi] + xi

# print(tree)
# print(point)

answer = [0] * N
def dfs(node, p):
    answer[node] = p + point[node]
    for t in tree[node]:
        dfs(t, answer[node])
    return None

dfs(0, 0)
print(' '.join(map(str,answer)))