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: Wrong Answer

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(reversed(ki)):
		if len(val) == 0:
			kiki.append([])
			continue
		addd = val
		'''
		for vol in val:
			tmp = ki[vol]
			addd.extend(tmp)
		kiki.append(addd)
		'''

	#print(ki)
	for i in range(Q):
		p,x = inputMap()
		if p == 1:
			for i in range(N):
				ans[i] += x
		else:
			ans[p-1] += x
			for vol in ki[p-1]:
				ans[vol] += x

	print(*ans)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from collections import defaultdict
import sys

d = defaultdict(list)
ans = defaultdict(int)

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

for _ in range(n-1):
    a,b = map(int, input().split())
    d[a].append(b)
    
#print(ans, d)

for i in range(q):
    p, x = map(int, input().split())
    #print(p, x)
    queue = [p]
    while True:
        #print("queue", queue)
        index = queue.pop(0)
        ans[index] += x
        tmp_list = d[index]
        if len(tmp_list) != 0:
            #print("tmp_list", tmp_list)
            #print("ans", ans)
            for tmp_d in tmp_list:
                queue.append(tmp_d)
                #print(ans)
        if len(queue) == 0:
            break
        #print(ans)
ans = sorted(ans.items(), key=lambda x:x[0])
ans = [tmp[1] for tmp in ans]
print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC138 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
g = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    g[b-1].append(a-1)
g[0].append(0)
x = [LI() for _ in range(q)]
x.sort()
ans = [0]*n
for i,j in x:
    ans[i-1] = ans[g[i-1][0]] + j
for i in range(n):
    if ans[i] == 0:
        ans[i] = ans[g[i-1][0]]
print(*ans)

Submission status: Wrong Answer

Solution code:
import collections

n,q=map(int,input().split())
a=list(list(map(int,input().split())) for i in range(n-1))
p=collections.defaultdict(int)
for i in range(q):
  k,v=map(int,input().split())
  p[k]+=v

li=[0]*n
li[0]+=p[1]
for i in range(0,n-1):
  li[a[i][1]-1]+=li[a[i][0]-1]+p[a[i][1]]
print(*li)

Submission status: Wrong Answer

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

parent={}

for i in range(n-1):
    a, b = map(int,input().split( ))
    parent[b]=[a]
    if a in parent:
        parent[b]+=parent[a]
# print(parent)

top_counter=[0 for i in range(n)]

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

# print(top_counter)

counter=[0 for i in range(n)]
for i in range(n):
    if i==0:
        counter[i]=top_counter[i]
    else:
        counter[i]=top_counter[i]
        check=parent[i+1]
        # print(check)
        for j in check:
            counter[i]+=top_counter[j-1]

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

Submission status: Wrong Answer

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)
    ki[b].append(a)

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

ed=[]

Submission status: Wrong Answer

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

	#print(ki)
	for i in range(Q):
		p,x = inputMap()
		ans[p-1] += x
		for vol in ki[p-1]:
			ans[vol] += x
			if len(ki[vol]) != 0:
				for v in ki[vol]:
					ans[v] += x
					if len(ki[v]) != 0:
						for vv in ki[v]:
							ans[vv] += x
							if len(ki[vv]) != 0:
								for vvv in ki[vv]:
									ans[vvv] += x
									if len(ki[vvv]) != 0:
										for vvvv in ki[vvv]:
											ans[vvvv] += x
											if len(ki[vvvv]) != 0:
												for vvvvv in ki[vvvv]:
													ans[vvvvv] += x

	print(*ans)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
side=[[0 for i in range(2)]for j in range(N-1)]
yobun=[[0 for i in range(2)]for j in range(Q)]

l=[0]*N


for i in range(N-1):
    side[i][0],side[i][1]=map(int,input().split())
    
for i in range(Q):
    yobun[i][0],yobun[i][1]=map(int,input().split())


def kyusyu(p,x):
    l[p-1]+=x
    for i in range(N-1):
        if p==side[i][0]:
            kyusyu(side[i][1],x)
            
for i in range(Q):
    kyusyu(yobun[i][0],yobun[i][1])
    
    
print(l)

Submission status: Wrong Answer

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

	#print(ki)
	for i in range(Q):
		p,x = inputMap()
		ans[p-1] += x
		for vol in ki[p-1]:
			ans[vol] += x
			if len(ki[vol]) != 0:
				for v in ki[vol]:
					ans[v] += x
					if len(ki[v]) != 0:
						for vv in ki[v]:
							ans[vv] += x
							if len(ki[vv]) != 0:
								for vvv in ki[vv]:
									ans[vvv] += x
									if len(ki[vvv]) != 0:
										for vvvv in ki[vvv]:
											ans[vvvv] += x

	print(*ans)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

st = [1]
while len(st) != 0:
    v = st.pop()
    cd[v-1] = list(set(ed[v-1]) & set(r))
    for item in list(set([i+1 for i in range(n)]) - set(r)):
        cd[item-1] += cd[v-1]
    r.remove(v)
    st += cd[v-1]

for i in range(q):
    p, x = map(int, input().split())       
    cnt[p-1] += x
    for item in cd[p-1]:
        cnt[item-1] += x
ans = ""
for c in cnt:
    ans += (str(c) + " ")

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10000*10000)

from collections import defaultdict, Counter
from queue import deque

def increment(key, count, adj_list, inc_num, visited):
    if key in visited:
        return
    que = deque()
    que.append(key)

    while que:
        for _ in range(len(que)):
            node = que.popleft()
            if node in visited:
                continue
            count[node] += inc_num
            visited.add(node)
            for num in adj_list[node]:
                que.append(num)

N, Q = map(int, input().split())
adj_list = defaultdict(list)
count = Counter()

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

for i in range(Q):
    c, d = map(int, input().split())
    increment(c, count, adj_list, d, set([]))

print(' '.join([str(num) for num in count.values()]))

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
nodes = [[-1, set()] for _ in range(N + 1)]  # (親node、set(子nodes))
nodes[1][0] = 1  # 1の親は1
ans = [0] * (N + 1)
for _ in range(N - 1):
    a, b = map(int, input().split())  # 接続ノード
    nodes[a][1].add(b)  # aの子にb

searchTargets = []
for childIdx in nodes[1][1]:
    searchTargets.append((1, childIdx))  # 親ノード番号, 探索先ノード番号

while searchTargets:
    parentIdx, targetIdx = searchTargets.pop()
    nodes[targetIdx][0] = parentIdx
    nodes[nodes[parentIdx][0]][1].add(targetIdx)
    for childIdx in nodes[targetIdx][1]:
        searchTargets.append((targetIdx, childIdx))

for _ in range(Q):
    p, x = map(int, input().split())
    ans[p] += x
    for descendant in nodes[p][1]:
        ans[descendant] += x
ans.pop(0)
print(" ".join(map(str, ans)))

Submission status: Wrong Answer

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

	#print(ki)
	for i in range(Q):
		p,x = inputMap()
		ans[p-1] += x
		for vol in ki[p-1]:
			ans[vol] += x
			if len(ki[vol]) != 0:
				for v in ki[vol]:
					ans[v] += x
					if len(ki[v]) != 0:
						for vv in ki[v]:
							ans[vv] += x
							if len(ki[vv]) != 0:
								for vvv in ki[vv]:
									ans[vvv] += x

	print(*ans)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, Q = LI()
    A, B, P, X = [], [], [], []
    memo = [0 for _ in range(N)]
    ans = [0 for _ in range(N)]
    for _ in range(N-1):
        _a, _b = LI()
        A.append(_a-1)
        B.append(_b-1)
    for _ in range(Q):
        _p, _x = LI()
        # memo[_p-1] += _x
        ans[_p-1] += _x
        #P.append(_p-1)
        #X.append(_x)
    ans[0] += memo[0]
    for i in range(N-1):
        a_nodenum = A[i]
        b_nodenum = B[i]
        # ans[b_nodenum] += (ans[a_nodenum] + memo[b_nodenum])
        ans[b_nodenum] += ans[a_nodenum]
    for i in ans:
        print(i, end=" ")
    print()
main()

Submission status: Wrong Answer

Solution code:
N, Q = (int(v) for v in input().split())
edge_dict = {}
for i in range(1, N):
    a, b = (int(v) for v in input().split())
    edge_dict.setdefault(a, []).append(b)
p_list, x_list = [0], [0]
for i in range(1, Q + 1):
    p, x = (int(v) for v in input().split())
    p_list.append(p)
    x_list.append(x)

cnt_dict = {}
for p in range(1, N):
    print(cnt_dict.get(p, 0), end=' ')
print(cnt_dict.get(N, 0))

Submission status: Wrong Answer

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

	#print(ki)
	for i in range(Q):
		p,x = inputMap()
		ans[p-1] += x
		for vol in ki[p-1]:
			ans[vol] += x
			if len(ki[vol]) != 0:
				for v in ki[vol]:
					ans[v] += x
					if len(ki[v]) != 0:
						for vv in ki[v]:
							ans[vv] += x

	print(*ans)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:

class Node:
	def __init__(self, parentNode, _id):
		self.id = _id
		self.counter = 0
		self.parentNode = parentNode
		self.childs = []
	
	def addCounter(self, p, x, flag):
		if p == self.id or flag == True:
			flag = True
			self.counter += x

		for c in self.childs:
			c.addCounter(p, x, flag)
	
	def appendChild(self, parent_id, _id):
		if parent_id == self.id:
			self.childs.append(Node(self, _id))
			return True
		else:
			for c in self.childs:
				if c.appendChild(parent_id, _id) == True:
					return True
	
	def getAllCounter(self):
		dic = {self.id: self.counter}
		for c in self.childs:
			dic.update(c.getAllCounter())
		return dic

	def printMe(self):
		for c in self.childs:
			c.printMe()
		if not self.parentNode is None:
			print(self.parentNode.id, self.id, self.counter)
		else:
			print(self.id, self.counter)

def main():
	N, Q = [int(f) for f in input().split()]
	
	root = Node(None, 1)
	for _ in range(N-1):
		a, b = [int(f) for f in input().split()]
		root.appendChild(a, b)

	for _ in range(Q):
		p, x = [int(f) for f in input().split()]
		root.addCounter(p, x, False)
	
	#print("---")
	for t in sorted(root.getAllCounter().items()):
		print(t[1], end=" ")
	print("")

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

n, q = map(int, input().split())
edge = defaultdict(list)

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

ops = []
for i in range(q):
    pp, xx = map(int, input().split())
    ops.append((pp, xx))


if __name__ == '__main__':
    children = defaultdict(set)
    dq = deque()
    dq.append(1)
    found = set()
    while True:
        if len(dq) == 0:
            break
        p = dq.popleft()
        found.add(p)
        for c in edge[p]:
            if c in found:
                continue
            children[p].add(c)
            dq.append(c)

    counter = defaultdict(int)
    for p, x in ops:
        q = deque()
        dq.append(p)
        while True:
            if len(dq) == 0:
                break
            i = dq.popleft()
            counter[i] += x
            for c in children[i]:
                dq.append(c)
    print(' '.join([str(counter[i]) for i in sorted(counter.keys())]))

Submission status: Wrong Answer

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 = 2*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: Wrong Answer

Solution code:
from collections import defaultdict

N,Q=map(int,input().split())
l=[ tuple( map(int,input().split()) ) for i in range(N-1) ]
p=[ tuple( map(int,input().split()) ) for i in range(Q) ]
d=defaultdict(list)
for vert,childs in l:
    d[vert].append(childs)

for i in range(N,0,-1):
    for j in d[i]:
        if j in d.keys():
            for x in d[j]:
                d[i].append(x)

d_2=defaultdict(int)
for p,x in p:
    d_2[p]+=x
    for o in d[p]:
        d_2[o]+=x

ans=d_2.values()
print(*ans)

Submission status: Wrong Answer

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

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

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

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


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

Submission status: Wrong Answer

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

	#print(ki)
	for i in range(Q):
		p,x = inputMap()
		ans[p-1] += x
		for vol in ki[p-1]:
			ans[vol] += x
			if len(ki[vol]) != 0:
				for v in ki[vol]:
					ans[v] += x

	print(*ans)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]
dp = [0] * n
ls = [[] for i in range(n)]
for i in ab:
    ls[i[0]-1].append(i[1]-1)
for i in px:
    dp[i[0]-1] += i[1]
    qq = []
    for z in ls[i[0]-1]:
        qq.append(z)
    while True:
        if len(qq) == 0:
            break
        else:
            qn = qq.pop()
            dp[qn] += i[1]
            if len(ls[qn]) != 0:
                for k in ls[qn]:
                    qq.append(k)
print(dp)

Submission status: Wrong Answer

Solution code:
from collections import deque

n, q = map(int, input().split( ))
Edg={}
for i in range(n-1):
    Edg[i+1]=[]
for i in range(n-1):
    a, b = map(int, input().split( ))
    Edg[a].append(b)
Ans=[0 for i in range(n+1)]
P = []
X = []
for i in range(q):
    p, x = map(int, input().split( ))
    P.append(p)
    X.append(x)

Task=deque()
for i in range(q):
    Task.append(P[i])
    tmp=X[i]
    while True:
        try:
            p=Task.popleft()
            Ans[p]+=tmp
            for child in Edg[p]:
                Task.append(child)
        except:
            break
print(*Ans[1:])

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
ko=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int, input().split())
    ko[a-1].append(b-1)
ans=[0]*n
for i in range(q):
    a,b=map(int, input().split())
    ans[a-1]+=b
nex=[0]
while nex:
    p=nex.pop()
    print(nex)
    for i in ko[p]:
        ans[i]+=ans[p]
    nex+=ko[p]
print(*ans)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
l=[[1]]
ans=[0]*n
ba=sorted([list(map(int,input().split()))[::-1] for i in range(n-1)])
for j in range(n-1):
  a=ba[j][1]
  l.append(l[a-1]+[j+2])
for k in range(q):
  p,x=map(int,input().split())
  for t in range(n):
    if p in l[t]:
      ans[t]+=x
print(l)
print(*ans,sep=" ")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline

dic = defaultdict(list)
n, q = map(int, input().split())

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

tree = [0]*(n+1)

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

todo = deque([1])
while todo:
    root = todo.popleft()
    count = tree[root]
    children = dic[root]
    for to in children:
        tree[to] += count
    todo += children

print(' '.join(map(str, tree)).lstrip(' 0 '))

Submission status: Wrong Answer

Solution code:
N, Q = map(int,input().split()) # 複数の数字を変数に格納
List_ab = [list(map(int,input().split())) for i in range(N-1)] # [[1,2],[3,4],[5,6]]
List_px = [list(map(int,input().split())) for i in range(Q)] # [[1,2],[3,4],[5,6]]

count_list = [0]*N

List_px.sort()

for i in range(Q):
    p = List_px[i][0]
    x = List_px[i][1]
    count_list[p-1] += x
        
for i in range(N-1):
    a = List_ab[i][0]
    b = List_ab[i][1]
    count_list[b-1] += count_list[a-1]
    
print(*count_list)

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
y=[]
for i in range(a-1):
    v=list(map(int,input().split()))
    y.append(v)
ans=[0]*a
for j in range(b):
    c,d=map(int,input().split())
    ans[c-1]=ans[c-1]+d
for k in range(a-1):
    yy=y[k][0]-1
    zz=y[k][1]-1
    ans[zz]=ans[zz]+ans[yy]
print(*ans,sep=" ")

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
side=[[0 for i in range(2)]for j in range(N-1)]
yobun=[[0 for i in range(2)]for j in range(Q)]

l=[0]*N


for i in range(N-1):
    side[i][0],side[i][1]=map(int,input().split())
    
for i in range(Q):
    yobun[i][0],yobun[i][1]=map(int,input().split())


def kyusyu(p,x):
    l[p-1]+=x
    for i in range(N-1):
        if p==side[i][0]:
            kyusyu(side[i][1],x)
            
for i in range(Q):
    kyusyu(yobun[i][0],yobun[i][1])
    
    
print(l)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict
from bisect import bisect_left


class Solution:
    def main(self):
        path = defaultdict(list)
        N, Q = map(int, input().split())
        freq = [0] * N
        for i in range(N-1):
            ai, bi = map(int, input().split())
            path[ai-1].append(bi-1)
            path[bi-1].append(ai-1)

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

        stack = [(0, 0)]
        seen = set()
        res = [0] * N
        while stack:
            node, cum = stack.pop(0)
            seen.add(node)
            val = freq[node] + cum
            res[node] = val
            for other in path[node]:
                if other not in seen:
                    stack.append((other, val))
        print(' '.join(map(str, res)))

if __name__ == '__main__':
    Solution().main()

Submission status: Wrong Answer

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

Tree = dict()
for _ in range(1, N):
    a, b = map(int, input().split())
    if not a in Tree.keys():
        Tree[a] = [b]
    else:
        Tree[a].append(b)

for key in Tree.keys():
    points = Tree[key].copy()
    for point in points:
        if point in Tree.keys():
            Tree[key].extend(Tree[point])

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

scores = [0 for _ in range(N)]
for i in range(Q):
    p = P[i]
    x = X[i]
    scores[p - 1] += x
    if p in Tree.keys():
        for point in Tree[p]:
            scores[point - 1] += x

for score in scores:
    print(score, end=' ')

Submission status: Wrong Answer

Solution code:
N,Q= list(map(int, input().split()))
li1=[list(map(int,input().split())) for _ in range(N-1)]
li2=[list(map(int,input().split())) for _ in range(Q)]
lis=[[i] for i in range(N)]
ans=[0 for _ in range(N)]
li1=sorted(li1,reverse=True)
for i in li1:
    for j in lis[i[1]-1]:
        lis[i[0]-1].append(j)
for i in li2:
    for j in lis[i[0]-1]:
            ans[j]+=i[1]
print(ans)