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:
#!/usr/bin/env python3
import sys
# import math
# import numpy as np
# from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

# sys.setrecursionlimit(10000)


input = sys.stdin.readline
#### input
N, Q = list(map(int, input().split()))
ABs = []
for i in range(0, N-1):
  ABs.append(list(map(int, input().split())))

ABs = sorted(ABs, key=lambda x:x[1])

PXs = []
for i in range(0, Q):
  PXs.append(list(map(int, input().split())))
# a = list(map(int, input().split()))
# required_list = list(map(lambda x: int(x)*(-1), target_list))  # 各要素を-1倍


# n = int(input())
# t = [int(input()) for i in range(n)]
if em: sys.stdin = open('/dev/tty')
#### class
# class Node:
#   def __init__(self, data):
#     self.data = data
#     self.child= []
#     self.below = []

#### function
# @lru_cache(maxsize=10000)

#### process
scores = [0] * N
above_nodes  = [[x+1] for x in range(0, N)]

for i in range(0, len(ABs)):
  above_nodes[ABs[i][1]-1].extend(above_nodes[ABs[i][0]-1])

for i in range(0, len(PXs)):
  scores[PXs[i][0]-1] = scores[PXs[i][0]-1] + PXs[i][1]

for i in range(0, N):
  node_score = 0
  for above_node in above_nodes[i]:
    node_score = node_score + scores[above_node-1]
  print(node_score, end = ' ')
print("")

# if em: embed()
## heapsort, O(NlogN)
# import heapq
# As = [0,1,2,3]
# heapq.heapify(As)
# min = heapq.heappop(As)
# heapq.heappush(As, inserted_element)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
# import math
# import numpy as np
# from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

# sys.setrecursionlimit(10000)

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

ABs = sorted(ABs, key=lambda x:x[1])

PXs = []
for i in range(0, Q):
  PXs.append(list(map(int, input().split())))
# a = list(map(int, input().split()))
# required_list = list(map(lambda x: int(x)*(-1), target_list))  # 各要素を-1倍


# n = int(input())
# t = [int(input()) for i in range(n)]
if em: sys.stdin = open('/dev/tty')
#### class
# class Node:
#   def __init__(self, data):
#     self.data = data
#     self.child= []
#     self.below = []

#### function
# @lru_cache(maxsize=10000)

#### process
scores = [0] * N
above_nodes  = [[x+1] for x in range(0, N)]

for i in range(0, len(ABs)):
  above_nodes[ABs[i][1]-1].extend(above_nodes[ABs[i][0]-1])

for i in range(0, len(PXs)):
  scores[PXs[i][0]-1] = scores[PXs[i][0]-1] + PXs[i][1]

for i in range(0, N):
  node_score = 0
  for above_node in above_nodes[i]:
    node_score = node_score + scores[above_node-1]
  print(node_score, end = ' ')
print("")

# if em: embed()
## heapsort, O(NlogN)
# import heapq
# As = [0,1,2,3]
# heapq.heapify(As)
# min = heapq.heappop(As)
# heapq.heappush(As, inserted_element)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
# import math
# import numpy as np
# from functools import lru_cache
 
args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False
 
# sys.setrecursionlimit(10000)
 
#### input
N, Q = list(map(int, input().split()))
ABs = []
for i in range(0, N-1):
  ABs.append(list(map(int, input().split())))
 
PXs = []
for i in range(0, Q):
  PXs.append(list(map(int, input().split())))
# a = list(map(int, input().split()))
# required_list = list(map(lambda x: int(x)*(-1), target_list))  # 各要素を-1倍
 
 
# n = int(input())
# t = [int(input()) for i in range(n)]
if em: sys.stdin = open('/dev/tty')
#### class
# class Node:
#   def __init__(self, data):
#     self.data = data
#     self.child= []
#     self.below = []
 
#### function
# @lru_cache(maxsize=10000)
 
#### process
scores = [0] * N
above_nodes  = [[x+1] for x in range(0, N)]
 
for i in range(0, len(ABs)):
  above_nodes[ABs[i][1]-1].extend(above_nodes[ABs[i][0]-1])
 
for i in range(0, len(PXs)):
  scores[PXs[i][0]-1] = scores[PXs[i][0]-1] + PXs[i][1]
 
for i in range(0, N):
  node_score = 0
  for above_node in above_nodes[i]:
    node_score = node_score + scores[above_node-1]
  print(node_score, end = ' ')
print("")
 
# if em: embed()
## heapsort, O(NlogN)
# import heapq
# As = [0,1,2,3]
# heapq.heapify(As)
# min = heapq.heappop(As)
# heapq.heappush(As, inserted_element)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
# import math
# import numpy as np
# from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

# sys.setrecursionlimit(10000)

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

PXs = []
for i in range(0, Q):
  PXs.append(list(map(int, input().split())))
# a = list(map(int, input().split()))
# required_list = list(map(lambda x: int(x)*(-1), target_list))  # 各要素を-1倍


# n = int(input())
# t = [int(input()) for i in range(n)]
if em: sys.stdin = open('/dev/tty')
#### class
# class Node:
#   def __init__(self, data):
#     self.data = data
#     self.child= []
#     self.below = []

#### function
# @lru_cache(maxsize=10000)

#### process
scores = [0] * N
above_nodes  = [[x+1] for x in range(0, N)]

for i in range(0, len(ABs)):
  above_nodes[ABs[i][1]-1].extend(above_nodes[ABs[i][0]-1])

for i in range(0, len(PXs)):
  scores[PXs[i][0]-1] = scores[PXs[i][0]-1] + PXs[i][1]

for i in range(0, N):
  node_score = 0
  for above_node in above_nodes[i]:
    node_score = node_score + scores[above_node-1]
  print(node_score, end = ' ')
print("")

# if em: embed()
## heapsort, O(NlogN)
# import heapq
# As = [0,1,2,3]
# heapq.heapify(As)
# min = heapq.heappop(As)
# heapq.heappush(As, inserted_element)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, Q = map(int, input().split())

tree = [[] for _ in range(N+1)]

answer = [0] * (N + 1)

for i in range(N-1):
    parent, child = map(int, input().split())
    tree[parent].append(child)

for _ in range(Q):
    anker, point = map(int, input().split())
    q = deque([])  # キュー
    q.append(tree[anker])
    answer[anker] += point

    while len(q) > 0:
        p = q.popleft()  # キュー取りだし（先頭）
        for child in p:
            answer[child] += point
            if tree[child]:
                q.append(tree[child])  # キュー追加

Submission status: Wrong Answer

Solution code:
from collections import deque
N, Q = map(int, input().split())

tree = [[] for _ in range(N+1)]

answer = [0] * (N + 1)

def bfs(anker, point):
    q = deque([])  # キュー
    q.append(tree[anker])
    answer[anker] += point

    while len(q) > 0:
        p = q.popleft()  # キュー取りだし（先頭）
        for child in p:
            answer[child] += point
            if child < N:
                q.append(tree[child])  # キュー追加

for i in range(N-1):
    parent, child = map(int, input().split())
    tree[parent].append(child)

for _ in range(Q):
    anker, point = map(int, input().split())
    q = deque([])  # キュー
    q.append(tree[anker])
    answer[anker] += point

    while len(q) > 0:
        p = q.popleft()  # キュー取りだし（先頭）
        for child in p:
            answer[child] += point
            if child < N:
                q.append(tree[child])  # キュー追加

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

Submission status: Wrong Answer

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

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

ans = [0] * N
for i in range(N):
	ans[i] += point[i]
	for child in tree[i]:
		ans[child] += ans[i]

output=[]
for i in range(N):
	output.append(ans[i])
print(' '.join(map(str, output)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, Q = map(int, input().split())
tree = [[] for i in range(N)]
point = {}
for i in range(N-1):
	a, b = map(int, input().split())
	a -= 1
	b -= 1
	tree[a].append(b)

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

ans = {}
def dfs(cur_pos, cur_point):
	next_point = cur_point + point.get(cur_pos, 0)
	ans[cur_pos] = next_point
	if(cur_pos >= len(tree)):
		exit(0)
	for next_pos in tree[cur_pos]:
		dfs(next_pos, next_point)

dfs(0, 0)
output=[]
for i in range(N):
	output.append(ans.get(i, 0))
print(' '.join(map(str, output)))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, Q = map(int, input().split())

tree = [[] for _ in range(N+1)]
tree[0].append(1)

answer = [0] * N

def bfs(anker, point):
    q = deque([])  # キュー
    q.append(tree[anker])
    answer[anker - 1] += point

    while len(q) > 0:
        p = q.popleft()  # キュー取りだし（先頭）
        for child in p:
            answer[child-1] += point
            if child < N:
                q.append(tree[child])  # キュー追加

for i in range(N-1):
    parent, child = map(int, input().split())
    tree[parent].append(child)
for q in range(Q):
    anker, point = map(int, input().split())
    bfs(anker, point)

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

Submission status: Wrong Answer

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

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

ans = {}
def dfs(cur_pos, cur_point):
	next_point = cur_point + point.get(cur_pos, 0)
	ans[cur_pos] = next_point
	#for next_pos in tree[cur_pos]:
	#	dfs(next_pos, next_point)

dfs(0, 0)
output=[]
for i in range(N):
	output.append(ans.get(i, 0))
print(' '.join(map(str, output)))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, Q = map(int, input().split())

tree = [[] for _ in range(N+1)]
tree[0].append(1)

answer = [0] * N

def bfs(anker, point):
    q = deque([])  # キュー
    q.append(tree[anker])
    answer[anker - 1] += point

    while len(q) > 0:
        p = q.popleft()  # キュー取りだし（先頭）
        for child in p:
            answer[child-1] += point
            if child:
                q.append(tree[child])  # キュー追加

for i in range(N-1):
    parent, child = map(int, input().split())
    tree[parent].append(child)
for q in range(Q):
    anker, point = map(int, input().split())
    bfs(anker, point)

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

Submission status: Wrong Answer

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

tree = [[] for _ in range(N+1)]

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

c = [0] * (N+1)

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


ans = [0] * (N+1)

go = [1]
ans[1] = c[1]
while len(go) > 0:
    now = go.pop(0)
    for child in tree[now]:
        go.append(child)
        ans[child] = ans[now] + c[child]

print(*ans[1:])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

tmp = list(map(int, (input().split())))
n = tmp[0]
q = tmp[1]

edge = defaultdict(list)
fixed = [False] * (n + 1)
fixed[1] = True
point = [0] * (n + 1)

for i in range(1, n):
  tmp = list(map(int, (input().split())))
  edge[tmp[0]].append(tmp[1])
  edge[tmp[1]].append(tmp[0])

for i in range(1, q+1):
  tmp = list(map(int, (input().split())))
  point[tmp[0]] += tmp[1]

que = []
que += edge[1]
frm = 1

while len(que) != 0:
  cur = que.pop()
  if fixed[cur] == False:
    que += edge[cur]
    point[cur] += point[frm]
    fixed[cur] = True
    frm = cur

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

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)]
cnt = [0]*(n)
ab.sort()
for p,x in px:
    cnt[p-1] += x
for a,b in ab:
    cnt[b-1] += cnt[a-1]

print(*cnt)

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)]
cnt = [0]*(n)

for p,x in px:
    cnt[p-1] += x
for a,b in ab:
    cnt[b-1] += cnt[a-1]

print(*cnt)

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()
cnt = [0]*(n+1)

for i in px:
    cnt[i[0]] += i[1]
for j in ab:
    cnt[j[1]] += cnt[j[0]]

print(*cnt[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()
cnt = [0]*n

for i in px:
    cnt[i[0] - 1] += i[1]
for j in ab:
    cnt[j[1]-1] += cnt[j[0]-1]

print(*cnt)

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)]
cnt = [0]*n

for i in px:
    cnt[i[0] - 1] += i[1]
for j in ab:
    cnt[j[1]-1] += cnt[j[0]-1]

print(*cnt)

Submission status: Wrong Answer

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

def treetrace(i):
  score = [-1] * (n + 1)
  if src[i] == 0:
    return point[i]
  elif score[i] != -1:
    return score[i]
  else:
    score[i] = point[i] + treetrace(src[i])
    return score[i]
  
tmp = list(map(int, (input().split())))
n = tmp[0]
q = tmp[1]

src = [0] * (n + 1)
for i in range(1, n):
  tmp = list(map(int, (input().split())))
  src[tmp[1]] = tmp[0]

point = [0] * (n + 1)
for i in range(1, q+1):
  tmp = list(map(int, (input().split())))
  point[tmp[0]] += tmp[1]
  
for i in range(1, n + 1):
  print(treetrace(i), end=" ")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
    
def treetrace(i):
  score = [-1] * (n + 1)
  if src[i] == 0:
    return point[i]
  elif score[i] != -1:
    return score[i]
  else:
    score[i] = point[i] + treetrace(src[i])
    return score[i]
  
tmp = list(map(int, (input().split())))
n = tmp[0]
q = tmp[1]

src = [0] * (n + 1)
for i in range(1, n):
  tmp = list(map(int, (input().split())))
  src[tmp[1]] = tmp[0]

point = [0] * (n + 1)
for i in range(1, q+1):
  tmp = list(map(int, (input().split())))
  point[tmp[0]] += tmp[1]
  
for i in range(1, n + 1):
  print(treetrace(i), end=" ")

Submission status: Wrong Answer

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

def treetrace(i):
  score = [0] * (n + 1)
  if src[i] == 0:
    return point[i]
  elif score[i] != 0:
    return score[i]
  else:
    score[i] = point[i] + treetrace(src[i])
    return score[i]
  
tmp = list(map(int, (input().split())))
n = tmp[0]
q = tmp[1]

src = [0] * (n + 1)
for i in range(1, n):
  tmp = list(map(int, (input().split())))
  src[tmp[1]] = tmp[0]

point = [0] * (n + 1)
for i in range(1, q+1):
  tmp = list(map(int, (input().split())))
  point[tmp[0]] += tmp[1]
  
for i in range(1, n + 1):
  print(treetrace(i), end=" ")

Submission status: Wrong Answer

Solution code:
def treetrace(i):
  score = [0] * (n + 1)
  if src[i] == 0:
    return point[i]
  elif score[i] != 0:
    return score[i]
  else:
    return point[i] + treetrace(src[i])
  
tmp = list(map(int, (input().split())))
n = tmp[0]
q = tmp[1]

src = [0] * (n + 1)
for i in range(1, n):
  tmp = list(map(int, (input().split())))
  src[tmp[1]] = tmp[0]

point = [0] * (n + 1)
for i in range(1, q+1):
  tmp = list(map(int, (input().split())))
  point[tmp[0]] += tmp[1]
  
for i in range(1, n + 1):
  print(treetrace(i), end=" ")

Submission status: Wrong Answer

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

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

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

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

def dsf(ci,pi):
  for i in t[ci]:
    if i == pi:
      continue
    c[i] += c[ci]
    dsf(i, ci)

dsf(0,-1)

print(*c)

Submission status: Wrong Answer

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

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

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

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

def spread(pi):
  for i in t[pi]:
    c[i] += c[pi]
    spread(i)

spread(0)

print(*c)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
t=list()
c=[0 for _ in range(n)]

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

t.sort()
for i in range(n-1):
  c[t[i][1]] += c[t[i][0]]

print(*c)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
t=list()
c=[0 for _ in range(n)]

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

for i in range(n-1):
  c[t[i][1]] += c[t[i][0]]

print(*c)

Submission status: Wrong Answer

Solution code:
from collections import*
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,q=map(int,input().split())
    d=defaultdict(list)
    cost=defaultdict(int)
    for i in range(n-1):
        a,b=sorted(map(int,input().split()))
        d[a].append(b)
#        d[b].append(a)
#    print(d)
    for i in range(q):
        a,b=map(int,input().split())
        cost[a]+=b
    
    def dfs(cost,point):
        if len(d[point])==0:
            return 0
        for i in d[point]:
            cost[i]+=cost[point]
            dfs(cost,i)
    dfs(cost,1)
    print(*[t for s,t in sorted(cost.items())])
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    n,q=map(int,input().split())
    d=defaultdict(list)
    cost=defaultdict(int)
    for i in range(n-1):
        a,b=sorted(map(int,input().split()))
        d[a].append(b)
#        d[b].append(a)
#    print(d)
    for i in range(q):
        a,b=map(int,input().split())
        cost[a]+=b
    
    def dfs(cost,point):
        if len(d[point])==0:
            return 0
        for i in d[point]:
            cost[i]+=cost[point]
            dfs(cost,i)
    dfs(cost,1)
    print(*[t for s,t in sorted(cost.items())])
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    n,q=map(int,input().split())
    d=defaultdict(list)
    cost=defaultdict(int)
    for i in range(n-1):
        a,b=map(int,input().split())
        d[a].append(b)
#    print(d)
    for i in range(q):
        a,b=map(int,input().split())
        cost[a]+=b
    
    def dfs(cost,point):
        if len(d[point])==0:
            return 0
        for i in d[point]:
            cost[i]+=cost[point]
            dfs(cost,i)
    dfs(cost,1)
    print(*[t for s,t in sorted(cost.items())])
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def incrSubtree(graph, stack, val):
    x = stack.pop(0)
    for i in range(x, len(graph)):
        if (graph[x][i] != -1):
            graph[x][i] += val
            if (x != i):
                stack.append(i)


if __name__ == "__main__":
    n, q = map(int, input().split())
    incidenceGraph = [[-1 for i in range(0, n)] for j in range(0, n)]
    incidenceGraph[0][0] = 0
    for i in range(0, n - 1):
        a, b = map((lambda x: int(x) - 1), input().split())
        incidenceGraph[a][b] = 0

    operationTuples = []
    for i in range(0, q):
        operationTuples.append(tuple(map(int, input().split())))

    stack = []
    for op in operationTuples:
        stack.append(op[0] - 1)
        if (op[0] - 1 > 0):
            incidenceGraph[op[0] - 2][op[0] - 1] += op[1]
        while (len(stack) > 0):
            incrSubtree(incidenceGraph, stack, op[1])

    print(*[int(x) for line in incidenceGraph for x in line if x != -1])

Submission status: Wrong Answer

Solution code:

def incrSubtree(graph, stack, val):
    x = stack.pop(0)
    for i in range(0, len(graph)):
        if (graph[x][i] != -1):
            graph[x][i] += val
            if (x != i):
                stack.append(i)


if __name__ == "__main__":
    n, q = map(int, input().split())
    incidenceGraph = [[-1 for i in range(0, n)] for j in range(0, n)]
    incidenceGraph[0][0] = 0
    for i in range(0, n - 1):
        a, b = map((lambda x: int(x) - 1), input().split())
        incidenceGraph[a][b] = 0

    operationTuples = []
    for i in range(0, q):
        operationTuples.append(tuple(map(int, input().split())))

    stack = []
    for op in operationTuples:
        stack.append(op[0] - 1)
        if (op[0] - 1 > 0):
            incidenceGraph[op[0] - 2][op[0] - 1] += op[1]
        while (len(stack) > 0):
            incrSubtree(incidenceGraph, stack, op[1])

    print(*[int(x) for line in incidenceGraph for x in line if x != -1])

Submission status: Wrong Answer

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

point={}

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

ans=[0]*N
stack=[]
stack.append([0,0])
while len(stack)>0:
  nodes=stack.pop()
  node=nodes[0]
  sump=nodes[1]
  if node in point:
    sump=sump+point[node]
  ans[node]=sump
  if node in tree:
      childs=tree[node]
      for child in childs:
        stack.append([child,sump])

print(*ans)

Submission status: Wrong Answer

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

A=[]
P=[]

ans=[0]*N

def func(base,A,add):
    pass
    ans[base-1]+=add
    for i in range(N-1):
       if A[i][0] == base:
          func(A[i][1],A,add)
          
    return(ans)
    


for i in range(N-1):
    A +=[[int(x) for x in input().split()]]

for i in range(Q):
    P +=[[int(x) for x in input().split()]]

for p in P:
    func(p[0],A,p[1])

print(*ans)

Submission status: Wrong Answer

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

A=[]
P=[]

ans=[0]*N

def func(base,A,add):
    pass
    ans[base-1]+=add
    for i in range(N-1):
       if A[i][0] == base:
          func(A[i][1],A,add)
          
    return(ans)
    


for i in range(N-1):
    A +=[[int(x) for x in input().split()]]

for i in range(Q):
    P +=[[int(x) for x in input().split()]]

for p in P:
    func(p[0],A,p[1])

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def show(V):
    for v in V:
        print(v.value,end=' ')
    print()

def root(V):
    for v in V:
        if v.isRoot:
            return v
    return None

class Vertex:
    def __init__(self):
        self.value=0
        self.next=[]
        self.isRoot=True
        self.isReached=False

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

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

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

r=root(V)

q=deque()
q.append(root(V))

while q:
    v=q.popleft()
    v.isReached=True
    for u in v.next:
        if not u.isReached:
            u.value+=v.value
            q.append(u)

for v in V:
    print(v.value,end=' ')

Submission status: Wrong Answer

Solution code:
from collections import deque

def show(V):
    for v in V:
        print(v.value,end=' ')
    print()

def root(V):
    for v in V:
        if v.isRoot:
            return v
    return None

class Vertex:
    def __init__(self):
        self.value=0
        self.next=[]
        self.isRoot=True
        self.isReached=False

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

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

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

r=root(V)

q=deque()
q.append(root(V))
show(q)

while q:
    v=q.popleft()
    v.isReached=True
    for u in v.next:
        if not u.isReached:
            u.value+=v.value
            q.append(u)

for v in V:
    print(v.value,end=' ')

Submission status: Wrong Answer

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

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

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

for e in E:
    val[e[1]]+=val[e[0]]

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

Submission status: Wrong Answer

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

# print(E)

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

# print(c)

for e in E:
    c[e[1]]+=c[e[0]]

# print(c)
for ci in c:
    print(ci,end=' ')

Submission status: Wrong Answer

Solution code:
"""
testing code here
 
https://codeforces.com/blog/entry/70304
"""
 
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
  
# 'global' variables
n,m = map(int, input().split())
d = [[]] * (n + 1)
l = [0]*(n+1)
visted = [False]*(n+1)
  
def dfs(u,v):
    visted[v] = True
    l[v] += l[u]
    for i in d[v]:
        if visted[i] == False:
            dfs(v,i)
    return 
            
for i in range(n-1):
    a,b = map(int, input().split())
    d[a].append(b);d[b].append(a)
 
for i in range(m):
    a,b = map(int,input().split())
    l[a] += b
dfs(0,1)
print(*l[1:])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)
N,Q=map(int, input().split())
#AB=[list(map(int, input().split())) for i in range(N)]
tree_dist={}
for i in range(N):
    tree_dist[i+1] = set()
for i in range(N-1):
    a,b = map(int, input().split())
    tree_dist[a].add(b)
    tree_dist[b].add(a)
    
PX=[list(map(int, input().split())) for i in range(Q)]
z=[0]*N
for p,x in PX:
    z[p-1] += x

def saiki(i,p):
    print(i)
    L = list(tree_dist[i])
    for l in L:
        if l == p:
            continue
        z[l-1] += z[i-1]
        saiki(l,i)
saiki(1,0)
print(*z)

Submission status: Wrong Answer

Solution code:
from collections import deque

n, q = map(int, input().split( ))
Edg=[[] for i in range(n+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)]
Pls = [0 for i in range(n+1)]


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

root=1

Task=deque()

Task.append(root)

while len(Task)>0:
    p_=Task.popleft()
    tmp = Pls[p_]
    Ans[p_]+=tmp
    for child in Edg[p_]:
        Task.append(child)
        Pls[child]+=tmp


print(*Ans[1:])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,Q=map(int,input().split())
ko=[[] for _ in range(N)]
par=[-1]*N
for i in range(N-1):
  a,b=map(int,input().split())
  ko[a-1].append(b)
  par[b-1]=a

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


def dfs(p):
  P[p-1]+=P[par[p-1]-1]
  for i in ko[p-1]:
    dfs(i)

    
for i in ko[0]:
  dfs(i)
print(" ".join(map(str,P)))

Submission status: Wrong Answer

Solution code:
N, Q = [int(nq) for nq in input().split()]
AB = []
for i in range(N - 1):
  ab = [int(ab) for ab in input().split()]
  AB.append(ab)
AB.sort()
P, X = [], []
for j in range(Q):
  p, x = [int(px) for px in input().split()]
  P.append(p)
  X.append(x)

Score = [0] * N
for j in range(Q):
  Score[P[j] - 1] += X[j]

for i in range(N - 1):
  a, b = AB[i]
  Score[b - 1] += Score[a - 1]

ans = ""
for k in range(N):
  ans += str(Score[k]) + " "

print(ans)

Submission status: Wrong Answer

Solution code:
N, Q = [int(nq) for nq in input().split()]
AB = []
for i in range(N - 1):
  ab = [int(ab) for ab in input().split()]
  AB.append(ab)
AB.sort()
P, X = [], []
for j in range(Q):
  p, x = [int(px) for px in input().split()]
  P.append(p)
  X.append(x)

Score = [0] * N
for j in range(Q):
  Score[P[j] - 1] += X[j]

for i in range(N - 1):
  a, b = AB[i]
  Score[b - 1] += Score[a - 1]

ans = ""
for k in range(N):
  ans += str(Score[i]) + " "

print(ans)