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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
N, Q = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
C = {i: 0 for i in range(1,N+1)}
 
for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x
 
 
def propagate(u, p):
    C[u] += C[p]
    for v in V[u]:
        if v == p:
            continue
        propagate(v, u)

propagate(1, 0)
 
print(' '.join(str(C[i]) for i in range(1,N+1)))

Submission status: Runtime Error

Solution code:
import sys
N, Q = [int(i) for i in input().split()]
tree = {i:[] for i in range(1,N+1)}
cost_ls = {i:0 for i in range(1,N+1)}
for i in range(N-1):
    a, b = [int(j) for j in sys.stdin.readline().split()]
    tree[a].append(b)
    tree[b].append(a)

yet = set()
def plus(node, num):
    yet.add(node)
    cost_ls[node] += num
    if len(tree[node]) > 0:
        for child in tree[node]:
            if child in yet:
                continue
            plus(child, cost_ls[node])

for i in range(Q):
    p, x = [int(j) for j in sys.stdin.readline().split()]
    cost_ls[p] += x

plus(1, 0)

print(" ".join([str(cost) for cost in cost_ls.values()]))

Submission status: Runtime Error

Solution code:
import sys
N, Q = [int(i) for i in input().split()]
tree = {i:[] for i in range(N+1)}
cost_ls = {i:0 for i in range(N)}
for i in range(N-1):
    a, b = [int(j) for j in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

yet = set()
def plus(node, num):
    yet.add(node)
    cost_ls[node] += num
    if len(tree[node]) > 0:
        for child in tree[node]:
            if child in yet:
                continue
            plus(child, cost_ls[node])

for i in range(Q):
    p, x = [int(j) for j in sys.stdin.readline().split()]
    cost_ls[p-1] += x

plus(0, 0)

print(" ".join([str(cost) for cost in cost_ls]))

Submission status: Runtime Error

Solution code:
import sys
N, Q = [int(i) for i in input().split()]
tree = {i:[] for i in range(N)}
cost_ls = {i:0 for i in range(N)}
for i in range(N-1):
    a, b = [int(j) for j in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

yet = set()
def plus(node, num):
    yet.add(node)
    cost_ls[0] += num
    if len(tree[node]) > 0:
        for child in tree[node]:
            if child in yet:
                continue
            plus(child, cost_ls[0])

for i in range(Q):
    p, x = [int(j) for j in sys.stdin.readline().split()]
    cost_ls[p-1] += x

plus(0, 0)

print(" ".join([str(cost) for cost in cost_ls]))

Submission status: Runtime Error

Solution code:
import sys
N, Q = [int(i) for i in input().split()]
tree = {i:[] for i in range(N)}
cost_ls = [0 for i in range(N)]
for i in range(N-1):
    a, b = [int(j) for j in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

yet = set()
def plus(node, num):
    yet.add(node)
    cost_ls[node] += num
    if len(tree[node]) > 0:
        for child in tree[node]:
            if child in yet:
                continue
            plus(child, cost_ls[node])

for i in range(Q):
    p, x = [int(j) for j in sys.stdin.readline().split()]
    cost_ls[p-1] += x

plus(0, 0)

print(" ".join([str(cost) for cost in cost_ls]))

Submission status: Runtime Error

Solution code:
import sys
N, Q = [int(i) for i in input().split()]
tree = [[] for i in range(N)]
cost_ls = [0 for i in range(N)]
for i in range(N-1):
    a, b = [int(j) for j in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

yet = set()
def plus(node, num):
    yet.add(node)
    cost_ls[node] += num
    if len(tree[node]) > 0:
        for child in tree[node]:
            if child in yet:
                continue
            plus(child, cost_ls[node])

for i in range(Q):
    p, x = [int(j) for j in sys.stdin.readline().split()]
    cost_ls[p-1] += x

plus(0, 0)

print(" ".join([str(cost) for cost in cost_ls]))

Submission status: Runtime Error

Solution code:
import sys
N, Q = [int(i) for i in input().split()]
tree = [[] for i in range(N)]
cost_ls = [0 for i in range(N)]
for i in range(N-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

yet = set()
def plus(node, num):
    yet.add(node)
    cost_ls[node] += num
    if len(tree[node]) > 0:
        for child in tree[node]:
            if child in yet:
                continue
            plus(child, cost_ls[node])

for i in range(Q):
    p, x = [int(i) for i in sys.stdin.readline().split()]
    cost_ls[p-1] += x

plus(0, 0)

print(" ".join([str(cost) for cost in cost_ls]))

Submission status: Runtime Error

Solution code:
import sys
N, Q = [int(i) for i in input().split()]
tree = [[] for i in range(N)]
cost_ls = [0 for i in range(N)]
for i in range(N-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

yet = set()
def plus(node, num):
    yet.add(node)
    cost_ls[node] += num
    if len(tree[node]) == 0:
        return
    else:
        for child in tree[node]:
            if child in yet:
                continue
            plus(child, cost_ls[node])

for i in range(Q):
    p, x = [int(i) for i in sys.stdin.readline().split()]
    cost_ls[p-1] += x

plus(0, 0)

print(" ".join([str(cost) for cost in cost_ls]))

Submission status: Runtime Error

Solution code:
import sys
N, Q = [int(i) for i in input().split()]
tree = [[] for i in range(N)]
cost_ls = [0 for i in range(N)]
for i in range(N-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

yet = set()
def plus(node, num):
    yet.add(node)
    cost_ls[node] += num
    if len(tree[node]) == 0:
        return
    for child in tree[node]:
        if child in yet:
            continue
        plus(child, cost_ls[node])

for i in range(Q):
    p, x = [int(i) for i in sys.stdin.readline().split()]
    cost_ls[p-1] += x

plus(0, 0)

print(" ".join([str(cost) for cost in cost_ls]))

Submission status: Runtime Error

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

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

counts = [0] * (n+1)
adjs = {a: [] for a in range(1,n+1)}

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

costs = [[int(x) for x in input().split()] for i in range(q)]

for cost in costs:
    counts[cost[0]] += cost[1]

def visit(v: int, parent: int):
    counts[v] += counts[parent]
    for child in adjs[v]:
        if child == parent:
            continue
        visit(child, v)

visit(1, 0)

print(' '.join(list(map(lambda x: str(x), counts[1:]))))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
# from functools import reduce
from collections import defaultdict

sys.setrecursionlimit(1000000)


def main():
    # n, q
    n, q = map(int, input().split())

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

    values = [0 for i in range(n+1)]
    # p, x
    for _ in range(0, q):
        p, x = map(int, input().split())
        values[p] += x
    process(1, -1, trees, values)
    print(*values[1:])


def process(i, parent, trees, values):
    for j in trees[i]:
        if j == parent:
            continue
        values[j] += values[i]
        process(j, i, trees, values)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
# from functools import reduce
from collections import defaultdict


def main():
    # n, q
    n, q = map(int, input().split())

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

    values = [0 for i in range(n+1)]
    # p, x
    for _ in range(0, q):
        p, x = map(int, input().split())
        values[p] += x
    process(1, -1, trees, values)
    print(*values[1:])


def process(i, parent, trees, values):
    for j in trees[i]:
        if j == parent:
            continue
        values[j] += values[i]
        process(j, i, trees, values)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
# from functools import reduce
from collections import defaultdict


def main():
    # n, q
    n, q = map(int, input().split())

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

    values = [0 for i in range(n+1)]
    # p, x
    for _ in range(0, q):
        p, x = map(int, input().split())
        values[p] += x
    print(trees)
    process(1, -1, trees, values)
    print(*values[1:])


def process(i, parent, trees, values):
    for j in trees[i]:
        if j == parent:
            continue
        values[j] += values[i]
        process(j, i, trees, values)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

boss = {}
point = {}
point[n] = 0
for i in range(1,n):
    a,b = map(int, input().split())
    boss[b] = a
    point[i] = 0

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

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

print(ans)

Submission status: Runtime Error

Solution code:
import sys
N, Q = [int(i) for i in input().split()]
tree = [[] for i in range(N)]
cost_ls = [0 for i in range(N)]
for i in range(N-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    tree[a].append(b)

def plus(node, num):
    cost_ls[node] += num
    if len(tree[node]) == 0:
        return
    for child in tree[node]:
        plus(child, num)

for i in range(Q):
    p, x = [int(i) for i in sys.stdin.readline().split()]
    plus(p-1, x)

print(" ".join([str(cost) for cost in cost_ls]))

Submission status: Runtime Error

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

class Tree:
    def __init__(self, v):
        self.v = 0
        self.counter = 0
        self.leaves = []
        self.offspring = []

[n, q] = [int(x) for x in sys.stdin.readline().rstrip().split()]

a = [0] * (n-1)
b = [0] * (n-1)
for i in range(n-1):
    [a[i], b[i]] = [int(x) for x in sys.stdin.readline().rstrip().split()]
p = [0] * q
x = [0] * q
for i in range(q):
    [p[i], x[i]] = [int(x) for x in sys.stdin.readline().rstrip().split()]

trees = [Tree(0)]
tree_dict = {}

for i in range(1,n+1):
    tree = Tree(i)
    trees.append(tree)
    tree_dict[i] = tree
    
root = tree_dict[1]
        
for i in range(n-1):
    tree_dict[a[i]].leaves.append(tree_dict[b[i]])

def rec_offspring(t: Tree):
    for c in t.leaves:
        rec_offspring(c)
    for c in t.leaves:
        t.offspring.extend(c.offspring)
    t.offspring.extend(t.leaves)

rec_offspring(trees[1])

for i in range(q):
    t = tree_dict[p[i]]
    t.counter += x[i]
    for c in t.offspring:
        c.counter += x[i]

print(' '.join(list(map(lambda x: str(x.counter), trees[1:]))))

Submission status: Runtime Error

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

class Tree:
    def __init__(self, v):
        self.v = 0
        self.counter = 0
        self.leaves = []

[n, q] = [int(x) for x in sys.stdin.readline().rstrip().split()]

a = [0] * (n-1)
b = [0] * (n-1)
for i in range(n-1):
    [a[i], b[i]] = [int(x) for x in sys.stdin.readline().rstrip().split()]
p = [0] * q
x = [0] * q
for i in range(q):
    [p[i], x[i]] = [int(x) for x in sys.stdin.readline().rstrip().split()]

trees = [Tree(0)]
tree_dict = {}

for i in range(1,n+1):
    tree = Tree(i)
    trees.append(tree)
    tree_dict[i] = tree
    
root = tree_dict[1]
        
for i in range(n-1):
    tree_dict[a[i]].leaves.append(tree_dict[b[i]])

def rec_add(t: Tree, x: int):
    t.counter += x
    for child in t.leaves:
        rec_add(child, x)

for i in range(q):
    rec_add(tree_dict[p[i]], x[i])

print(' '.join(list(map(lambda x: str(x.counter), trees[1:]))))

Submission status: Runtime Error

Solution code:
N, Q = list(map(int, input().split()))
brunch = [[] for _ in range(N)]
value = [0 for _ in range(N)]
for _ in range(N-1):
  a, b = list(map(int, input().split()))
  brunch[a-1].append(b-1)

def flow(fr, v, brunch, v_list):
  v_list[fr] += v
  for to in brunch[fr]:
    v_list = flow(to, v, brunch, v_list)
  return v_list

for _ in range(Q):
  frr, val = list(map(int, input().split()))
  value = flow(frr-1, val, brunch, value)
print(' '.join(map(str, value)))

Submission status: Runtime Error

Solution code:
n,q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1)]
pq = [list(map(int,input().split())) for i in range(q)]
ab.sort()
c = [0]*n
for i in range(q):
  c[pq[i][0]-1] += pq[i][1]
start = 1
lst = []
count = 0
while count < n-1:
  if ab[0][0] == start:
    lst.append(ab[0][1])
    c[ab[0][1]-1] += c[ab[0][0]-1]
    lst.sort()
    ab.pop(0)
    count += 1
  else:
    start = lst.pop(0)
for i in c:
  print(i,end= " ")

Submission status: Runtime Error

Solution code:
P, n = map(int, input().split())
struct = [list(map(int, input().split())) for x in range(P-1)]
act = [list(map(int, input().split())) for y in range(n)]

A = []


def add_val(action):
    idx = action[0]
    val = action[1]

    A[idx][0] += val

    if A[idx][1]:
        for r in A[idx][1]:
            add_val([r, val])


for a in range(P + 1):
    A.append(list([0, []]))

for z in struct:
    p = z[0]
    p_ = z[1]
    A[p][1].append(p_)

for _ in act:
    add_val(_)


As = []
for _ in range(1, len(A)):
    As.append(A[_][0])

print(*As, sep=' ')

Submission status: Runtime Error

Solution code:
P, n = map(int, input().split())
struct = [list(map(int, input().split())) for x in range(P-1)]
act = [list(map(int, input().split())) for y in range(n)]

A = []


def add_val(action):
    idx = action[0]
    val = action[1]

    A[idx][0] += val

    if A[idx][1]:
        for r in A[idx][1]:
            add_val([r, val])


for a in range(P + 1):
    A.append(list([0, []]))

for z in struct:
    p = z[0]
    p_ = z[1]
    A[p][1].append(p_)

for _ in act:
    add_val(_)


As = []
for _ in range(1, len(A)):
    As.append(A[_][0])

print(*As, sep=' ')

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
tree = [[] for n in range(n)]
score = [0]*n
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
for _ in range(q):
    p, x = map(int, input().split())
    score[p-1] += x
arr = tree[0]
while len(arr) != 0:
    i = arr.pop()
    for i in tree[i]:
        score[i] += score[k]
    arr += tree[i]
        

score_str=[str(s) for s in score]
print(" ".join(score_str))

Submission status: Runtime Error

Solution code:
mport sys
from collections import deque

stack = deque()
input = sys.stdin.readline

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

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

check = [0] * N
stack.append(1)
check[0] = 1
while stack:
    node = stack.pop()
    for next_node in link[node - 1]:
        if check[next_node - 1]:
            continue
        states[next_node - 1] += states[node - 1]
        check[next_node - 1] = 1
        stack.append(next_node)

# Output
print(*states)

Submission status: Runtime Error

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

C = {i: 0 for i in range(1,N+1)}

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


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)

propagate(1, 0)

print(' '.join(str(C[i]) for i in range(1,N+1)))

Submission status: Runtime Error

Solution code:
def dfs(v,p):
    for i in tree[v]:
        if i==p:
            continue
        res[i]+=res[v]
        dfs(i,v)

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

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

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

Submission status: Runtime Error

Solution code:
def dfs(v,p):
    for i in tree[v]:
        if i==p:
            continue
        res[i]+=res[v]
        dfs(i,v)

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

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

dfs(0,0)
print(*res)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

ans = []
v = []

# def rec(i, p):
# 	global ans, v
# 	if p != -1:
# 		ans[i] += ans[p]
# 	for node in v[i]:
# 		if node != p:
# 			rec(node, i)

def rec(i, p):
	global ans, v
	for node in v[i]:
		if node != p:
			ans[node] += ans[i]
			rec(node, i)

def main():
	global v, ans
	n, q = map(int, input().strip().split())
	v = [[] for _ in range(n)]
	ans = [0] * n
	for i in range(n-1):
		a, b = map(int, input().strip().split())
		a -= 1
		b -= 1
		v[a].append(b)
		v[b].append(a)
	
	for i in range(q):
		a, b = map(int, input().strip().split())
		a -= 1
		ans[a] += b
	
	rec(0, -1)
	for e in ans:
		print(e)

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

ans = []
v = []

def rec(i, p):
	global ans, v
	if p != -1:
		ans[i] += ans[p]
	for node in v[i]:
		if node != p:
			rec(node, i)

def main():
	global v, ans
	n, q = map(int, input().strip().split())
	v = [[] for _ in range(n)]
	ans = [0] * n
	for i in range(n-1):
		a, b = map(int, input().strip().split())
		a -= 1
		b -= 1
		v[a].append(b)
		v[b].append(a)
	
	for i in range(q):
		a, b = map(int, input().strip().split())
		a -= 1
		ans[a] += b
	
	rec(0, -1)
	for e in ans:
		print(e)

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
def dfs(tree,node,x,ans):
    ans[node-1]+=x
    if node in tree:
        for i in tree[node]:
            dfs(tree,i,x,ans)


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

ans = [0]*n
for i in range(q):
    p,x = map(int,input().split())
    dfs(tree,p,x,ans)

print(*ans)

Submission status: Runtime Error

Solution code:
# ABC138D - Ki
import sys

input = sys.stdin.readline
sys.setrecursionlimit(2 * 10 ** 5 + 2)


def dfs(v: int, p: int) -> None:
    x = cnt[v]
    for u in T[v]:
        if u != p:  # p: parent -> skip
            cnt[u] += x  # cumulative sum
            dfs(u, v)


def main():
    # Ai (A[i][0]) may be not a parent of Bi (A[i][1])
    global T, cnt
    N, Q = tuple(map(int, input().split()))  # vertices and queues
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    P = tuple(tuple(map(int, input().split())) for _ in range(Q))
    T = [[] for _ in range(N + 1)]  # tree, N+1: 1-idx
    for a, b in E:
        T[a] += [b]
        T[b] += [a]
    cnt = [0] * (N + 1)
    for p, x in P:
        cnt[p] += x  # increase vertex p by x
    dfs(1, -1)
    print(*cnt[1:])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# ABC138D - Ki
import sys

input = sys.stdin.readline
sys.setrecursionlimit(2 * 10 ** 5 + 1)


def dfs(v: int, p: int) -> None:
    x = cnt[v]
    for u in T[v]:
        if u != p:  # p: parent -> skip
            cnt[u] += x  # cumulative sum
            dfs(u, v)


def main():
    # Ai (A[i][0]) may be not a parent of Bi (A[i][1])
    global T, cnt
    N, Q = tuple(map(int, input().split()))  # vertices and queues
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    P = tuple(tuple(map(int, input().split())) for _ in range(Q))
    T = [[] for _ in range(N + 1)]  # tree, N+1: 1-idx
    for a, b in E:
        T[a] += [b]
        T[b] += [a]
    cnt = [0] * (N + 1)
    for p, x in P:
        cnt[p] += x  # increase vertex p by x
    dfs(1, -1)
    print(*cnt[1:])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# ABC138D - Ki
import sys

input = sys.stdin.readline
sys.setrecursionlimit(2 * 10 ** 5)


def dfs(v: int, p: int) -> None:
    x = cnt[v]
    for u in T[v]:
        if u != p:  # p: parent -> skip
            cnt[u] += x  # cumulative sum
            dfs(u, v)


def main():
    # Ai (A[i][0]) may be not a parent of Bi (A[i][1])
    global T, cnt
    N, Q = tuple(map(int, input().split()))  # vertices and queues
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    P = tuple(tuple(map(int, input().split())) for _ in range(Q))
    T = [[] for _ in range(N + 1)]  # tree, N+1: 1-idx
    for a, b in E:
        T[a] += [b]
        T[b] += [a]
    cnt = [0] * (N + 1)
    for p, x in P:
        cnt[p] += x  # increase vertex p by x
    dfs(1, -1)
    print(*cnt[1:])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n,q = list(map(int,input().split()))
    link = []
    operation = []
    for i in range(n-1):
        link.append([int(s) for s in input().split()])
    for i in range(q):
        operation.append([int(s) for s in input().split()])
    query = [0] * n
    ans = [0] * n

    for i in range(q):
        query[operation[i][0]-1] = query[operation[i][0]-1] + operation[i][1]
    linking = [[] for _ in range(n)]
    for i in range(n-1):
        linking[link[i][0] - 1].append(link[i][1]-1)
        linking[link[i][1] - 1].append(link[i][0]-1)
    flag = [True] * n
    def dfs(v,val):
        child = linking[v]
        flag[v] = False
        val += query[v]
        ans[v] = val
        for s in child:
            if flag[s]:
                dfs(s,val)
        return
    dfs(0,0)
    print(*ans)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def dfs(tree,node,x,ans):
    ans[node-1]+=x
    if node in tree:
        for i in tree[node]:
            dfs(tree,i,x,ans)


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

ans = [0]*n
for i in range(q):
    p,x = map(int,input().split())
    dfs(tree,p,x,ans)

print(*ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
	sys.setrecursionlimit(700000)
	N, Q = map(int, input().split())
	d = [[] for i in range(N)]

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

	ans = [0]*N

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

	def dfs(cur, parent):
    	for child in d[cur]:
        	if child != parent:
            	ans[child] += ans[cur]
            	dfs(child,cur)
	dfs(0,-1) 

	print(*ans)
    
main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

class Node:
	def __init__(self, id):
		self.id = id
	parent = None
	x = 0
	w = 0

v = []
nodes = []

def dfs(node):
	global v, nodes
	nodes[node].w = nodes[nodes[node].parent].w + nodes[node].x
	if v[node] == []:
		return
	for k in v[node]:
		if k != nodes[node].parent:
			dfs(k)

def main():
	global v, nodes
	n, q = map(int, input().strip().split())
	v = [[] for _ in range(n)]
	for i in range(n-1):
		a, b = map(int, input().strip().split())
		a -= 1
		b -= 1
		v[a].append(b)
	nodes = [Node(i) for i  in range(n)]
	nodes[0].parent = 0
	for i in range(n-1):
		for j in v[i]:
			# if j != nodes[i].parent:
			nodes[j].parent = i

	for i in range(q):
		a, b = map(int, input().strip().split())
		a -= 1
		nodes[a].x += b

	dfs(0)


	for i in range(n):
		# print(v[i])
		print(nodes[i].w)

if __name__ == '__main__':
	main()

Submission status: Runtime Error

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

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

ans = [0 for i in range(N)]

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

def dfs(cur, parent):
    for child in d[cur]:
        if child != parent
            ans[child] += ans[cur]
            dfs(child,car)
dfs(0,-1) 

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

class Node:
	def __init__(self, id):
		self.id = id
	parent = None
	x = 0
	w = 0

v = []
nodes = []

def dfs(node):
	global v, nodes
	nodes[node].w = nodes[nodes[node].parent].w + nodes[node].x
	if v[node] == []:
		return
	for k in v[node]:
		if k != nodes[node].parent:
			dfs(k)

def main():
	global v, nodes
	n, q = map(int, input().strip().split())
	v = [[] for _ in range(n)]
	for i in range(n-1):
		a, b = map(int, input().strip().split())
		a -= 1
		b -= 1
		v[a].append(b)
	nodes = [Node(i) for i  in range(n)]
	nodes[0].parent = 0
	for i in range(n-1):
		for j in v[i]:
			if j != nodes[i].parent:
				nodes[j].parent = i

	for i in range(q):
		a, b = map(int, input().strip().split())
		a -= 1
		nodes[a].x += b

	dfs(0)


	for i in range(n):
		# print(v[i])
		print(nodes[i].w)

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import bisect

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n-1):a[i+1]+= a[i]
  
cnt = 0
for i in range(n)[::-1]:
  if a[i]<k:
    break
  t = bisect.bisect_right(a,a[i]-k)
  print(t)
  cnt+=t+1
print(cnt)

Submission status: Runtime Error

Solution code:
# グラフの実装 -> 隣接リスト表現, 隣接行列表現
# 隣接リスト表現：各頂点に対して隣接頂点を連結リストで管理する

import collections

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

# 隣接リストの作成
for _ in range(N - 1):
    pare, kid = map(int, input().split())
    G[pare].add(kid)

# 各頂点についてxの合計を計算
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x

# BFSの実装
qu = collections.deque()
qu.append(1)#親の初期値
checked = [0] * (N+1)
while qu:
    v = qu.popright()
    checked[v] = 1
    for u in G[v]:
        if checked[u] == 1:
            continue
        cnt[u] += cnt[v]
        qu.append(u)
print(*cnt[1:])

Submission status: Runtime Error

Solution code:
while True:
    try:
        N, Q = map(int, input().split())
        verts = [None] * N
        results = [0] * N
        for i in range(N - 1):
            a, b = map(int, input().split())
            a -= 1
            b -= 1
            if verts[a] is None:
                verts[a] = list()
            verts[a].append(b)

        maxmap = [None] * N
        map_a = [None] * N
        map_b = [None] * N
        def trav(a, x):
            map_a[a] = x
            map_b[x] = a
            if verts[a] is None:
                return x
            for i in verts[a]:
                maxmap[i] = x = trav(i, x + 1)
            return x

        maxmap[0] = trav(0, 0)

        for i in range(Q):
            q, x = map(int, input().split())
            q-= 1
            if q == 0:
                for i in range(N):
                    results[i] += x
            elif verts[q] is not None:
                for i in range(map_a[q], maxmap[q] + 1):
                    results[i] += x
            else:
                results[q] += x
        print(" ".join(map(str, results)))
    except EOFError:
        break

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.sstrecursionlimit(2*10**5)
n,q=map(int,input().split())
graph=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
counter=[0]*n
for _ in range(q):
  p,x=map(int,input().split())
  counter[p-1]+=x
score=[0]*(n+1)
stack=[(0,-1)]
while stack!=[]:
  node,prev=stack.pop()
  score[node]=score[prev]+counter[node]
  for i in graph[node]:
    if i!=prev:
      stack.append((i,node))
print(*score[:-1])

Submission status: Runtime Error

Solution code:
# ABC138D - Ki (entirely global namespace)
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(v: int, p: int) -> None:
    for u in T[v]:
        if u != p:  # p: parent -> skip
            cnt[u] += cnt[v]  # cumulative sum
            dfs(u, v)


# Ai (A[i][0]) may be not a parent of Bi (A[i][1])
N, Q = tuple(map(int, input().split()))  # vertices and queues
E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
P = tuple(tuple(map(int, input().split())) for _ in range(Q))
T = [[] for _ in range(N + 1)]  # tree, (N+1: 1-idx -> 0-idx)
for a, b in E:
    T[a] += [b]
    T[b] += [a]
cnt = [0] * (N + 1)
for p, x in P:
    cnt[p] += x  # increase vertex p by x
dfs(1, -1)
print(*cnt[1:])


if __name__ == "__main__":
    main()