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:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())

graph=[[]for i in range(n)]

for i in range(n-1):
    x,y=map(lambda x: int(x)-1,input().split())
    graph[x].append(y)

score=[0]*n

for i in range(q):
    x,y=map(int,input().split())
    score[x-1]+=y
    
from collections import deque
option=deque()
option.append(0)


while option:
    now=option.pop()
    for nex in graph[now]:
        score[nex]+=score[now]
        option.append(nex)

print(*score)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())

graph=[[]for i in range(n)]

for i in range(n-1):
    x,y=map(lambda x: int(x)-1,input().split())
    graph[x].append(y)

score=[0]*n

for i in range(q):
    x,y=map(int,input().split())
    score[x-1]+=y
    
from collections import deque
option=deque()
option.append(0)
total=[0]*n
total[0]=score[0]

while option:
    now=option.pop()
    for nex in graph[now]:
        if total[nex]==0:
            total[nex]=total[now]+score[nex]
            option.append(nex)

print(*total)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys


def traverse(v, x):
    counter[v - 1] += x
    if not g[v]:
        return
    for nv in g[v]:
        traverse(nv, x)


sys.setrecursionlimit(10 ** 6)
n, q = map(int, input().split())
g = defaultdict(set)
counter = [0] * n
for _ in range(n - 1):
    a, b = map(int, input().split())
    g[a].add(b)
for _ in range(q):
    traverse(*map(int, input().split()))
print(*counter)

Submission status: Wrong Answer

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

def input():
    return sys.stdin.readline()[:-1]

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

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

B=[]
for i in range(Q):
	b=list(map(int,input().split()))
	B.append(b)

    
def dfs(x,col):
    score[x-1]+=col[1]
    for j in A[x-1]:
       dfs(j,col)
        
for i in range(Q):
    dfs(B[i][0],B[i])

print(*score)

Submission status: Wrong Answer

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

import sys
input = sys.stdin.readline

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

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

B=[]
for i in range(Q):
	b=list(map(int,input().split()))
	B.append(b)

    
def dfs(x,col):
    score[x-1]+=col[1]
    for j in A[x-1]:
       dfs(j,col)
        
for i in range(Q):
    dfs(B[i][0],B[i])

print(*score)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


def main():
    n,q = na()
    roots = [i for i in range(n)]
    counter = [0 for _ in range(n)]
    for _ in range(n-1):
        a,b = na()
        a -= 1
        b -= 1
        roots[b] = a
    for _ in range(q):
        p,x = na()
        counter[p-1] += x
    for i in range(n):
        root = i
        cnt = counter[root]
        while roots[root] != root:
            root = roots[root]
            cnt += counter[root]
        print(cnt, end=' ')
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


def main():
    n,q = na()
    roots = [i for i in range(n)]
    counter = [0 for _ in range(n)]
    for _ in range(n-1):
        a,b = na()
        a -= 1
        b -= 1
        roots[b] = a
    for _ in range(q):
        p,x = na()
        counter[p-1] += x
    for i in range(n):
        root = i
        cnt = counter[root]
        while roots[root] != root:
            root = roots[root]
            cnt += counter[root]
        print(cnt, end=' ')
        counter[i] = cnt
        roots[i] = i
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

B=[]
for i in range(Q):
	b=list(map(int,input().split()))
	B.append(b)

    
def dfs(x,col):
    score[x-1]+=col[1]
    for j in A[x-1]:
       dfs(j,col)
        
for i in range(Q):
    dfs(B[i][0],B[i])

print(*score)

Submission status: Wrong Answer

Solution code:
def main():
    n,q = map(int,input().split())
    ki = {}
    for i in range(n):
        ki[i+1] = []
    for i in range(n-1):
        a,b = map(int,input().split())
        ki[a] += [b]

    ans = [0 for i in range(n)]
    for i in range(q):
        p,x = map(int,input().split())
        ans[p-1] += x
    for i in range(n):
        if len(ki[i+1])>0:
            for d in ki[i+1]:
                ans[d-1]+=ans[i]
    print(' '.join(map(str,ans)))
        


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n,q = map(int,input().split())
    ki = {}
    for i in range(n):
        ki[i+1] = []
    for i in range(n-1):
        a,b = map(int,input().split())
        ki[a] += [b]
    print(ki)
    ans = [0 for i in range(n)]
    for i in range(q):
        p,x = map(int,input().split())
        ans[p-1] += x
    for i in range(n):
        if len(ki[i+1])>0:
            for d in ki[i+1]:
                ans[d-1]+=ans[i]
    print(' '.join(map(str,ans)))
        


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

N, Q = map(int, input().split())
E = [list(map(int, input().split())) for _ in range(N-1)]
X = [list(map(int, input().split())) for _ in range(Q)]
C = [0 for _ in range(N)]


for x in X:
    # カウンタ加算
    C[x[0]-1] += x[1]

for e in E:
    C[e[1]-1] += C[e[0]-1]

print(*C, sep=' ')

Submission status: Wrong Answer

Solution code:
#Writer : Rute
N,Q = map(int,input().split())
ls1 = [0]*N
#Graph
for i in range(N-1):
    a,b = map(int,input().split())
for i in range(Q):
    p,x = map(int,input().split())
    ls1[p-1] += x
for j in range(1,len(ls1)):
    ls1[j] += ls1[j-1]
print(*ls1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, q = map(int, input().split())
cnt = [0] * n

a, b = [0] * (n - 1), [0] * (n - 1)

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

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

for i in range(n - 1):
    cnt[b[i] - 1] += cnt[a[i] - 1]

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n, q = map(int, input().split())
cnt = [0] * n

a, b = [0] * (n - 1), [0] * (n - 1)

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

def dfs(a, b, s, x):
    cnt[s - 1] += x
    if s not in a:
        return 
    for i in range(n - 1):
        if a[i] == s:
            dfs(a, b, b[i], x)


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

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

Submission status: Wrong Answer

Solution code:
n, q = map(int,input().split())
tree = [[] for i in range(n)]
v = [0]*n
for i in range(n-1):
    a1,b1 = [int(i) for i in input().split()]
    tree[a1-1].append(b1)
for i in range(q):
    p1,x1 = [int(i) for i in input().split()]
    v[p1 - 1] += x1
for i in range(n):
    for j in range(len(tree[i])):
        v[tree[i][j]-1] += v[i]
for i in range(n):
    print(str(v[i]) +" ",end="")

Submission status: Wrong Answer

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

N,Q=map(int,input().split())
a=[0]*(N-1)
b=[0]*(N-1)
p=[0]*Q
x=[0]*Q
c=[[] for _ in range(N)]  #接続リスト
cnt=[0]*N  #カウンター値

for i in range(N-1):
  a[i],b[i]=map(int,input().split())
  c[a[i]-1].append(b[i]-1)
  c[b[i]-1].append(a[i]-1)
for i in range(Q):
  p[i],x[i]=map(int,input().split())
  cnt[p[i]-1] += x[i]

def dfs(x,parent):
  if parent!=-1:
    cnt[x] += cnt[parent]
  for child in c[x]:
    if child!=parent:
      dfs(child,x)

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()
    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())
a=[0]*(N-1)
b=[0]*(N-1)
parent_list=[-1]+[0]*(N-1)
add_list=[0]*N
p=[0]*Q
x=[0]*Q

for i in range(N-1):
  a[i],b[i]=map(int,input().split())
  parent_list[b[i]-1]=a[i]-1
for i in range(Q):
  p[i],x[i]=map(int,input().split())
  add_list[p[i]-1] += x[i]
  
#print(parent_list)
#print(add_list)

ans_list=[add_list[0]]
for i in range(1,N):
  ans_list.append(ans_list[parent_list[i]]+add_list[i])
  #print(i,parent_list[i],add_list[parent_list[i]],add_list[i])
  
print(*ans_list)

Submission status: Wrong Answer

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

def main():
    N, Q = list(map(int, input().split()))
    graph = [[] for i in range(N)]
    # 最初にroot pointを定めて:
    # graph構造に大して点を与える...
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    
    points = [0] * N
    for _ in range(Q):
        p, x = list(map(int, input().split()))
        points[p-1] += x
    
    visited = [False] * N
    
    nodes = deque(graph[0])
    visited[0] = True

    while nodes:
        node = nodes.pop()
        visited[node] = True
        for _node in graph[node]:
            if visited[node]:
                continue
            points[_node] += points[node]
            nodes.append(_node)
    
    print(*points)
    
main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
sys.setrecursionlimit(1000000000)

N, Q = list(map(int, input().split()))
graph = [[] for i in range(N)]
# 最初にroot pointを定めて:
# graph構造に大して点を与える...
for i in range(N-1):
    a, b = list(map(int, input().split()))
    graph[a-1].append(b-1)

points = np.zeros(N, dtype=int)
for _ in range(Q):
    p, x = list(map(int, input().split()))
    points[p-1] += x

visited = np.zeros(N, dtype=bool)
tot_points = np.zeros(N, dtype=int)
tot_points[0] = points[0]
top_nodes = np.full(N, -1, dtype=int)

nodes = graph[0]
top_nodes[nodes] = 0
old_node = 0
visited[0] = True


def dfs(old_node, node):
    if visited[node]:
        return
    tot_points[node] = tot_points[old_node] + points[node]
    visited[node] = True
    nodes = graph[node]
    while len(nodes):
        dfs(node, nodes.pop())
while len(nodes):
    dfs(0, nodes.pop())
    

for x in tot_points.tolist():
    print(x, end=" ")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

N, Q = list(map(int, input().split()))
graph = [[] for i in range(N)]
# 最初にroot pointを定めて:
# graph構造に大して点を与える...
for i in range(N-1):
    a, b = list(map(int, input().split()))
    graph[a-1].append(b-1)

points = np.zeros(N, dtype=int)
for _ in range(Q):
    p, x = list(map(int, input().split()))
    points[p-1] += x

visited = np.zeros(N, dtype=bool)
tot_points = np.zeros(N, dtype=int)
tot_points[0] = points[0]
top_nodes = np.full(N, -1, dtype=int)

nodes = graph[0]
top_nodes[nodes] = 0
old_node = 0
while len(nodes):
    node = nodes.pop()
    if top_nodes[node] == -1:
        top_nodes[node] = old_node
    else:
        old_node = top_nodes[node]
    top_nodes[graph[node]] = node
    nodes.extend(graph[node])
    tot_points[node] = tot_points[old_node] + points[node]
    old_node = node

for x in tot_points.tolist():
    print(x, end=" ")

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(v):
    stack = deque([v])
    while stack:
        v = stack.popleft()
        c[v] += x
        for s in g[v]:
            stack.append(s)

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

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

c = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    dfs(p-1)

print(*c)

Submission status: Wrong Answer

Solution code:
def dfs(v):
    stack = [v]
    while stack:
        v = stack.pop()
        c[v] += x
        for s in g[v]:
            stack.append(s)

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

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

c = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    dfs(p-1)

print(*c)

Submission status: Wrong Answer

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

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

import sys
sys.setrecursionlimit(10**8)

def dfs(v):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        ans[u] += ans[v]
        dfs(u)
    return

dfs(0)

print(*ans, sep=' ')

Submission status: Wrong Answer

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

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

#print(From)

for i in range(1,N):
    points[i]+=points[From[i]]
    
print(*points)

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
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# 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の降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,Q = inputMap()

	ki = [[] for i in range(N)]
	vals = [0 for i in range(N)]
	QF = UnionFind(N)

	for i in range(N-1):
		a,b = inputMap()
		a -= 1
		b -= 1

		if i == 0:
			ki[a].append(b)
			QF.union(a,b)
		else:
			if QF.is_same(a,0) == True:
				ki[a].append(b)
				QF.union(a,b)
			else:
				ki[b].append(a)
				QF.union(a,b)

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

	counts = 0
	ko = []
	stk = Stack()
	#print(ki)
	kari = 0
	while True:
		if counts == 0:
			ko = ki[0]
			kari = vals[0]
		else:
			tmp = stk.pop()
			if tmp == None:
				break
			else:
				ko,kari = tmp

		counts += 1
		for i in ko:
			vals[i] += kari
			if len(ki[i]) >= 1:
				stk.push((ki[i],vals[i]))

	print(*vals)


class Stack:
    def __init__(self, stack = None):
        if type(stack) is type([]):
            self.stack = stack
        else:
            self.stack = []

    def push(self, e):
        self.stack.append(e)
        return self.stack

    def pop(self):
        try:
            sEl = self.stack.pop()
            return sEl
        except IndexError:
            return None


class UnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		self.size = [1 for _ in range(n)]

	# x が属するグループを探索
	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	# x と y のグループを結合
	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			# メンバ数の更新
			sum = self.size[x] + self.size[y]
			self.size[x] = sum
			self.size[y] = sum
			# 短いリストを長いリストのルートに繋ぎ直す
			if self.rank[x] < self.rank[y]:
				x, y = y, x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
			self.par[y] = x

	# x と y が同じグループがどうか
	def is_same(self, x, y):
		return self.find(x) == self.find(y)

	# x が属するグループのメンバ数を返却
	def getSize(self, x):
		par_x = self.find(x)
		return self.size[par_x]

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

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
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# 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の降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,Q = inputMap()

	ki = [[] for i in range(N)]
	vals = [0 for i in range(N)]

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

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

	for i in range(N):
		ko = ki[i]
		for j in ko:
			vals[j] += vals[i]

	print(*vals)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float('inf')
MOD=10**9+7
input=sys.stdin.readline

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

tree=[[] for _ in range(n)]

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

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

result=[0]*n

def counter(chouten,count):
    global result,point,tree
    count+=point[chouten]
    result[chouten]=count

    #print(chouten,result)

    for item in tree[chouten]:
        if result[item]==0:
            counter(item,count)

counter(0,0)

result=map(str,result)
print(" ".join(result))

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)]
ab.sort(key=lambda x:x[0])
d={}
ans=[0]*(n+1)
for p,x in px:
    ans[p]+=x
for a,b in ab:
    if (a,b) in d:
        continue
    ans[b]+=ans[a]
    d[(a,b)]=1
print(' '.join(map(str,ans[1:])))

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)]
d={}
ans=[0]*(n+1)
for p,x in px:
    ans[p]+=x
for a,b in ab:
    if (a,b)in d:
        continue
    ans[b]+=ans[a]
    d[(a,b)]=1
print(' '.join(map(str,ans[1:])))

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)]
ab.sort(key=lambda x:x[0])
ans=[0]*(n+1)
for [p,x] in px:
    ans[p]+=x
for [a,b] in ab:
    ans[b]+=ans[a]
print(' '.join(map(str,ans[1:])))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10 ** 9)
n,q=map(int,input().split())
ab=np.array([list(map(int,input().split())) for _ in range(n-1)])
px=np.array([list(map(int,input().split())) for _ in range(q)])
d={}
ans=np.zeros(n,np.int64)
def bbk(i):
    if i in d:
        return d[i]
    ret=[]
    ret.append(i)
    c=ab[ab[:,0]==i][:,1]
    for ci in c:
        ret[len(ret):len(ret)]=bbk(ci)
    d[i]=ret
    return ret
for pxi in px:
    l=np.array(bbk(pxi[0]))
    ans[l-1]+=pxi[1]
print(' '.join(map(str,ans)))

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)]
d={}
ans=[0]*n
def bbk(i):
    if i in d:
        return d[i]
    ret=[]
    ret.append(i)
    c=[x[1] for x in ab if x[0]==i]
    for ci in c:
        ret[len(ret):len(ret)]=bbk(ci)
    d[i]=ret
    return ret
for pxi in px:
    l=bbk(pxi[0])
    for li in l:
        ans[li-1]+=pxi[1]
print(' '.join(map(str,ans)))

Submission status: Wrong Answer

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

def dfs(v,s):
  #global dic_score
  #global tree_list
  #global ans_list  
  score=s
  if v in dic_score:
    score+=dic_score[v]
    
  ans_list[v]+=score
  for vv in tree_list[v]:
    dfs(vv,score)
    
  return s

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

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

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

ans_list=[0]*(N+1)
dfs(1,0)

#print(tree_list)
print(*ans_list[1:])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
node = [0] * n
par = [-1] * n
ans = [-1] * n
for _ in range(n-1):
    a, b = map(int, input().split())
    par[b-1] = a-1
for _ in range(q):
    p, x = map(int, input().split())
    node[p-1]+=x
def dfs(i, count=0):
    if ans[i] != -1:
        return count + ans[i]
    count+=node[i]
    if par[i] == -1:
        return count
    else:
        return dfs(par[i], count)
for i in range(n):
    ans[i] = dfs(i)
print(' '.join(list(map(str, ans))))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
node = [0] * n
par = [-1] * n
for _ in range(n-1):
    a, b = map(int, input().split())
    par[b-1] = a-1
for _ in range(q):
    p, x = map(int, input().split())
    node[p-1]+=x
def dfs(i, count=0):
    count+=node[i]
    if par[i] == -1:
        return count
    else:
        return dfs(par[i], count)
print(' '.join([str(dfs(i)) for i in range(n)]))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(n-1)]
t=[list(map(int,input().split())) for _ in range(m)]
s.sort()
list=[0]*n
for i in range(m):
  a=t[i][0]-1
  list[a]+=t[i][1]
for j in range(n-1):
  a=s[j][0]-1
  b=s[j][1]-1
  list[b]+=list[a]
print(*list)

Submission status: Wrong Answer

Solution code:
from collections import deque

n, q = map(int, input().split())
dist = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    dist[a - 1].append(b - 1)
    # aftercontest対策
    dist[b - 1].append(a - 1)
value = [0 for i in range(n)]

# 1つ目の[1, 10]と2つ目の[1, 10]混ぜても問題なし
for i in range(q):
    p, x = map(int, input().split())
    value[p - 1] += x
#  重複を防ぐ
ignore = [0] * n
ignore[0] = 1

print(dist)
pos = deque([0])
# 上から順に自身のvalueの値を子のvalueに加算していく
# value [100, 10, 1, 0]
# pos.popleft() = 1 → [100, 10 + 100, 1 + 100, 0 + 100]
# pos.popleft() = 2 → [100, 110, 101 + 10, 100 + 10]
while len(pos) > 0:
    u = pos.popleft()
    for i in dist[u]:
        if ignore[i] == 0:
            ignore[i] = 1
            value[i] += value[u]
            pos.append(i)
# 覚える
print(*value)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

# 1つ目の[1, 10]と2つ目の[1, 10]混ぜても問題なし
for i in range(q):
    p, x = map(int, input().split())
    value[p - 1] += x
#  重複を防ぐ
ignore = [0] * n
ignore[0] = 1

pos = deque([0])
# 上から順に自身のvalueの値を子のvalueに加算していく
# value [100, 10, 1, 0]
# pos.popleft() = 1 → [100, 10 + 100, 1 + 100, 0 + 100]
# pos.popleft() = 2 → [100, 110, 101 + 10, 100 + 10]
while len(pos) > 0:
    u = pos.popleft()
    for i in dist[u]:
        if ignore[i] == 0:
            ignore[i] = 1
            value[i] += value[u]
            pos.append(i)
# 覚える
print(*value)