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
sys.setrecursionlimit(10**6)


def main():
    def dfs(now, prev=-1):
        for next in edge[now]:
            if next == prev:
                continue
            score[next] += score[now]
            dfs(next, now)

    N, Q = map(int, input().split())
    edge = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        edge[u].append(v)
        edge[v].append(u)
    p = []
    x = []
    score = [0] * (N+1)
    for _ in range(Q):
        p, x = map(int, input().split())
        score[p] += x
    dfs(1)
    print(score[1:])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


def main():
    def dfs(now, prev=-1):
        for next in edge[now]:
            if next == prev:
                continue
            score[next] += score[now]
            dfs(next, now)

    N, Q = map(int, input().split())
    edge = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        edge[u].append(v)
        edge[v].append(u)
    p = []
    x = []
    score = [0] * (N+1)
    for _ in range(Q):
        p, x = map(int, input().split())
        score[p] += x
    dfs(1)
    print(score)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,q = map(int,stdin.readline().rstrip().split())
li = [[0 for i in range(n+1)]for j in range(n+1)]
for i in range(n-1):
    a,b = map(int,stdin.readline().rstrip().split())
    li[a][b] = 1
kotae = [0]*(n+1)
def depth_first_search(start, W):
    # リストをスタックとして利用する
    work_stack = []
    visited = set()
    work_stack.append(start)
    visited.add(start)
    while work_stack:
        #print(work_stack)  # work_stackの中身を表示する
        here = work_stack.pop()
        for i, node in enumerate(W[here]):
            if node == 0: continue
            if i not in visited:
                work_stack.append(i)
                visited.add(i)
    return visited
for i in range(q):
    p,x = map(int,stdin.readline().rstrip().split())
    lin = depth_first_search(p,li)
    for j in lin:
        kotae[j] += x
print(*kotae[1:])

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        
    ans = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1 
        ans[p] += x
    
    Q = deque()
    Q.append(0)
    while Q:
        v = Q.popleft()
        for d in edge[v]:
            Q.append(d)
            ans[d] += ans[v]

    print(*ans)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)

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

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

def kasan(now, plus):
    plus+=plist[now]
    answers[now]=plus
    ng=len(kolist[now])
    if ng!=0:
        for i in range(ng):
            kasan(kolist[now][i], plus)

kasan(0, 0)
for an in answers:
    print(an, end=" ")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)

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

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

def kasan(now, plus):
    plus+=plist[now]
    answers[now]=plus
    if len(kolist[now])!=0:
        for i in range(len(kolist[now])):
            kasan(kolist[now][i], plus)
    return kolist[now], plus

kasan(0, 0)
for an in answers:
    print(an, end=" ")

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
D = {}
A = [0 for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  if a-1 in D:
    D[a-1].append(b-1)
  else:
    D[a-1] = [b-1]
for i in range(Q):
  p, x = map(int, input().split())
  A[p-1] += x
for j in D:
  for m in D[j]:
    A[m] += A[j]
for k in range(N):
  if k == N - 1:
    print(A[k])
  else:
    print(A[k], end = ' ')

Submission status: Wrong Answer

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

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

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

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

for i in range(n-1):
  for leaf in tree[i]:
    ans[leaf]+=ans[i]

print(*ans)

Submission status: Wrong Answer

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

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,b=a-1,b-1
  tree[a].append(b)

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

for i in range(n):
  for leaf in tree[i]:
    ans[leaf]+=ans[i]

print(*ans)

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

nmax=2*10**5+10
graph=[[] for _ in range(nmax)]

def dfs(n,s,l):
  if len(graph[s])==0:
    return
  for e in graph[s]:
    l[e]+=l[s]
    dfs(n,e,l)

def main():
  n,q=LI()
  for _ in range(n-1):
    a,b=LI()
    graph[a-1].append(b-1)
  l=[0]*n
  for _ in range(q):
    a,b=LI()
    l[a-1]+=b

  dfs(n,0,l)

  return ' '.join([str(x) for x in l])

# main()
print(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)]
ab.sort(key=lambda x:(x[0], x[1]))
print(ab)
co=[0 for _ in range(N)]
for p, x in px:
    co[p-1]+=x
for a, b in ab:
    co[b-1]+=co[a-1]
print(*co)

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])
co=[0 for _ in range(N)]
for p, x in px:
    co[p-1]+=x
for a, b in ab:
    co[b-1]+=co[a-1]
print(*co)

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)]
px.sort(key=lambda x:x[0])
co=[0 for _ in range(N)]
for p, x in px:
    co[p-1]+=x
for a, b in ab:
    co[b-1]+=co[a-1]
print(*co)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
#a = [int(x) for x in input().split()]

NQ = str(input()).split()
N = int(NQ[0])
Q = int(NQ[1])
ab = []
px = []
ans = [0]*N
count = 1



for i in range(N-1):
  ab.append([int(x) for x in input().split()])
  if(i==0):
    i=i
  elif(ab[i][0] < ab[i-1][0]):
    temp = ab[i]
    ab[i] = ab[i-1]
    ab[i-1] = temp
#ab.sort()


for i in range(Q):
  px.append([int(x) for x in input().split()])
  ans[px[i][0]-1] += px[i][1]

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


ans_str =[str(a) for a in ans]
ans_str = ' '.join(ans_str)
print(ans_str)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
#a = [int(x) for x in input().split()]

NQ = str(input()).split()
N = int(NQ[0])
Q = int(NQ[1])
ab = []
px = []
ans = [0]*N
count = 1



for i in range(N-1):
  ab.append([int(x) for x in input().split()])
  if(i==0):
    i=i
  elif(ab[i][0] < ab[i-1][0]):
    temp = ab[i]
    ab[i] = ab[i-1]
    ab[i-1] = temp
#ab.sort()

for i in range(Q):
  px.append([int(x) for x in input().split()])
  ans[px[i][0]-1] += px[i][1]

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


ans_str =[str(a) for a in ans]
ans_str = ' '.join(ans_str)
print(ans_str)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
#a = [int(x) for x in input().split()]

NQ = str(input()).split()
N = int(NQ[0])
Q = int(NQ[1])
ab = []
px = []
ans = [0]*N
count = 1
temp = 0



for i in range(N-1):
  ab.append([int(x) for x in input().split()])
  if(i==0):
    i=i
  elif(ab[i][0] < ab[i-1][0]):
    temp = ab[i][0]
    ab[i][0] = ab[i-1][0]
    ab[i-1][0] = temp
#ab.sort()

for i in range(Q):
  px.append([int(x) for x in input().split()])
  ans[px[i][0]-1] += px[i][1]

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


ans_str =[str(a) for a in ans]
ans_str = ' '.join(ans_str)
print(ans_str)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
#a = [int(x) for x in input().split()]

NQ = str(input()).split()
N = int(NQ[0])
Q = int(NQ[1])
ab = []
px = []
ans = [0]*N
count = 1
temp = 0



for i in range(N-1):
  ab.append([int(x) for x in input().split()])
ab.sort()

for i in range(Q):
  px.append([int(x) for x in input().split()])
  ans[px[i][0]-1] += px[i][1]

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


ans_str =[str(a) for a in ans]
ans_str = ' '.join(ans_str)
print(ans_str)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
#a = [int(x) for x in input().split()]

NQ = str(input()).split()
N = int(NQ[0])
Q = int(NQ[1])
ab = []
px = []
ans = [0]*N
count = 1
temp = 0



for i in range(N-1):
  ab.append([int(x) for x in input().split()])
ab.sort()

for i in range(Q):
  px.append([int(x) for x in input().split()])
  ans[px[i][0]-1] += px[i][1]

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


ans_str =[str(a) for a in ans]
ans_str = ' '.join(ans_str)
print(ans_str)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
#a = [int(x) for x in input().split()]

NQ = str(input()).split()
N = int(NQ[0])
Q = int(NQ[1])
ab = []
px = []
ans = [0]*N
count = 1
temp = 0



for i in range(N-1):
  ab.append([int(x) for x in input().split()])
#ab.sort()

for i in range(Q):
  px.append([int(x) for x in input().split()])
  ans[px[i][0]-1] += px[i][1]

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


ans_str =[str(a) for a in ans]
ans_str = ' '.join(ans_str)
print(ans_str)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
#a = [int(x) for x in input().split()]

NQ = str(input()).split()
N = int(NQ[0])
Q = int(NQ[1])
ab = []
px = []
ans = [0]*N
count = 1
temp = 0

for i in range(N-1):
  ab.append([int(x) for x in input().split()])
  if(ab[i][0]>ab[i][1]):
    temp = ab[i][0]
    ab[i][0] = ab[i][1]
    ab[i][1] = temp

ab.sort()

for i in range(Q):
  px.append([int(x) for x in input().split()])
  ans[px[i][0]-1] += px[i][1]

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

ans_str =[str(a) for a in ans]
ans_str = ' '.join(ans_str)
print(ans_str)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
#a = [int(x) for x in input().split()]

NQ = str(input()).split()
N = int(NQ[0])
Q = int(NQ[1])
ab = []
px = []
ans = [0]*N
count = 1
temp = 0

for i in range(N-1):
  ab.append([int(x) for x in input().split()])
  if(ab[i][0]>ab[i][1]):
    temp = ab[i][0]
    ab[i][0] = ab[i][1]
    ab[i][1] = temp

ab.sort()

for i in range(Q):
  px.append([int(x) for x in input().split()])

px.sort()

for i in range(Q):
  ans[px[i][0]-1] += px[i][1]

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

ans_str =[str(a) for a in ans]
ans_str = ' '.join(ans_str)
print(ans_str)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
#a = [int(x) for x in input().split()]

NQ = str(input()).split()
N = int(NQ[0])
Q = int(NQ[1])
ab = []
px = []
ans = [0]*N
count = 1
temp = 0

for i in range(N-1):
  ab.append([int(x) for x in input().split()])
  if(ab[i][0]>ab[i][1]):
    temp = ab[i][0]
    ab[i][0] = ab[i][1]
    ab[i][1] = temp

ab.sort()

for i in range(Q):
  px.append([int(x) for x in input().split()])

px.sort()

for i in range(Q):
  ans[px[i][0]-1] += px[i][1]

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

print(ans)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
#a = [int(x) for x in input().split()]

NQ = str(input()).split()
N = int(NQ[0])
Q = int(NQ[1])
ab = []
px = []
ans = [0]*N
count = 1


for i in range(N-1):
  ab.append([int(x) for x in input().split()])

ab.sort()

for i in range(Q):
  px.append([int(x) for x in input().split()])

px.sort()

for i in range(Q):
  ans[px[i][0]-1] += px[i][1]

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

[n, q] = map(int, input().rstrip().split(" "))

tree = [{ "next": [], "point": 0 } for i in range(n + 1)]

def add_points(tree, key, point):
    params = tree[key]
    params["point"] = params["point"] + point
    for i in params["next"]:
        add_points(tree, i, point)

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

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

print(" ".join(map(str, [v["point"] for v in tree[1:]])))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

[n, q] = map(int, input().rstrip().split(" "))

tree = {}

def add_points(tree, key, point):
    params = tree[key]
    params["point"] = params["point"] + point
    for i in params["next"]:
        add_points(tree, i, point)

for i in range(n-1):
    [a, b] = map(int, input().rstrip().split(" "))
    if tree.get(a) is None:
        tree[a] = { "next": [b], "point": 0 } 
    else:
        tree[a]["next"].append(b)
    if tree.get(b) is None:
        tree[b] = { "next": [], "point": 0 }

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

print(" ".join(map(str, [v["point"] for v in tree.values()])))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

[n, q] = map(int, input().rstrip().split(" "))

tree = {}

def sum_params(params):
    return params["point"] + sum([ sum_params(params[i]) for i in params["next"] ])

def add_points(tree, key, point):
    params = tree[key]
    params["point"] = params["point"] + point
    for i in params["next"]:
        add_points(tree, i, point)

for i in range(n-1):
    [a, b] = map(int, input().rstrip().split(" "))
    if tree.get(a) is None:
        tree[a] = { "next": [b], "point": 0 } 
        tree[b] = { "next": [], "point": 0 }
    else:
        tree[a]["next"].append(b)
        tree[b] = { "next": [], "point": 0 }

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

print(" ".join(map(str, [v["point"] for v in tree.values()])))

Submission status: Wrong Answer

Solution code:
[n, q] = map(int, input().rstrip().split(" "))

tree = {}

def sum_params(params):
    return params["point"] + sum([ sum_params(params[i]) for i in params["next"] ])

def add_points(tree, key, point):
    params = tree[key]
    params["point"] = params["point"] + point
    for i in params["next"]:
        add_points(tree, i, point)

for i in range(n-1):
    [a, b] = map(int, input().rstrip().split(" "))
    if tree.get(a) is None:
        tree[a] = { "next": [b], "point": 0 } 
        tree[b] = { "next": [], "point": 0 }
    else:
        tree[a]["next"].append(b)
        tree[b] = { "next": [], "point": 0 }

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

print(" ".join(map(str, [v["point"] for v in tree.values()])))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9) # 再帰の上限
n, q = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n - 1)]
b = [list(map(int, input().split())) for _ in range(q)]
g = [[] for i in range(n + 1)]
counter = [0] * (n + 1)

for i, j in a:
    g[i].append(j)

def dfs(e,c,counter):
    counter[e]+=c
    for k in g[e]:
        dfs(k,c,counter)

for i,j in b:
    dfs(i,j,counter)
counter.pop(0)
print(*counter)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d
# 下に数を最初に合計してから深さ優先探索なり、幅優先探索なりで下にカウンターを伝播させていけば良い。
# 累積和の木構造バージョン


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


# 再帰の上限を緩和する(引数は適当)
import sys
sys.setrecursionlimit(1 << 25)
from collections import defaultdict

N, Q = read_ints()
child = defaultdict(lambda: [])  # ノード0は存在しない
score = [0] * (N + 1)
for _ in range(N - 1):
    a, b = read_ints()
    child[a].append(b)
    child[b].append(a)
for _ in range(Q):
    p, x = read_ints()
    score[p] += x

# 木を走査しながらscoreを合計していく
ans = [0] * (N + 1)


def dfs(u, s):  # ノードuの親におけるスコアs
    s += score[u]
    ans[u] = s
    for c in child[u]:
        if ans[c] != 0:
            continue
        dfs(c, s)


dfs(1, 0)
print(*ans[1:])