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 numpy as np
import sys

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

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

# 隣接リスト
t = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)

# スコア
s = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    s[p-1] = s[p-1] + x

ans = [0] * N

# 深さ優先探索
def dfs(v, p, value):
    value = value + s[v]
    ans[v] = ans[v] + value
    for c in t[v]:
        if c == p:
            continue
        dfs(c, v, value)

dfs(0, -1, 0)

print(ans)

Submission status: Wrong Answer

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

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

seen = [False]*N
root_list = [[i] for i in range(N)]
todo = []

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

def dfs(G, v):
    seen[v] = True
    for next_v in G[v]:
        ans[next_v] += ans[v]
        if seen[next_v]:
            break
        else:
            dfs(G, next_v)

dfs(G,0)

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

Submission status: Wrong Answer

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

counter = [0]*(N+1)

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

for i in range(2,N+1):
  for p in parent[i]:
    counter[i] += counter[p]
    
for i in range(1,N+1):
  print(counter[i],end=' ')

Submission status: Wrong Answer

Solution code:
# =============================================================================
#　ABC138D Ki
# =============================================================================
import sys
sys.setrecursionlimit(10**8)

N,Q=map(int,input().split())
cnt=[0]*(N+1)
ans=[0]*(N+1)
Graph=[[] for _ in range(N+1)]
for _ in range(N-1):
    a,b=map(int,input().split())
    Graph[a].append(b)

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

def dfs(Graph,v,x):
    global ans
    ans[v]=x
    for nv in Graph[v]:
        nx=x+cnt[nv]
        dfs(Graph,nv,nx)

dfs(Graph,1,cnt[1])
ans=[str(ans[i]) for i in range(1,N+1)]
print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
# =============================================================================
#　ABC138D Ki
# =============================================================================
import sys
sys.setrecursionlimit(10**8)

N,Q=map(int,input().split())
cnt=[0]*(N+1)
Graph=[[] for _ in range(N+1)]
for _ in range(N-1):
    a,b=map(int,input().split())
    Graph[a].append(b)

def dfs(Graph,v,x):
    for nv in Graph[v]:
        dfs(Graph,nv,x)
    cnt[v]+=x

for _ in range(Q):
    v,x=map(int,input().split())
    dfs(Graph,v,x)

ans=[str(cnt[i]) for i in range(1,N+1)]
print(" ".join(ans))

Submission status: Wrong Answer

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

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

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

for i in range(N):
    for n in d[i+1]:
        ans[n-1]+=ans[i]

for a in ans:
    print(a,end=' ')

Submission status: Wrong Answer

Solution code:
from collections import deque

class Tree:
    def __init__(self, n, init_list, root=1):
        self.num = (n + 1)
        self.parents = [-1] * self.num
        self.first_child = [-1] * self.num
        self.next_child = [-1] * self.num
        self.check = [-1] * self.num
        self.g = {i: [] for i in range(1, self.num)}
        self.make_g(init_list, root)

    def make_g(self, con, root):
        m = len(con)
        for i in range(m):
            self.g[con[i][0]].append(con[i][1])
            self.g[con[i][1]].append(con[i][0])
        q = deque([root])
        while q != deque():
            node = q.pop()
            self.check[node] = 1
            cnt = 0
            for i, sub_node in enumerate(self.g[node]):
                if self.check[sub_node] != -1:
                    continue
                if cnt == 0:
                    self.first_child[node] = sub_node
                self.parents[sub_node] = node
                if i != len(self.g[node])-1:
                    self.next_child[sub_node] = self.g[node][i+1]
                q.append(sub_node)
                cnt += 1

    def childs(self, node):
        child_list = []
        if self.first_child[node] != -1:
            child_list.append(self.first_child[node])
            node = self.first_child[node]
            while 1:
                if self.next_child[node] == -1:
                    break
                else:
                    child_list.append(self.next_child[node])
                node = self.next_child[node]
        return child_list

    def parent(self, n):
        return self.parents[n]

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
P = [0] * Q
X = [0] * Q
V = [0] * (N + 1)
for i in range(Q):
    P, X = map(int, input().split())
    V[P] += X

tr = Tree(N, AB)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
P = [0] * Q
X = [0] * Q
V = [0] * (N + 1)
for i in range(Q):
    P, X = map(int, input().split())
    V[P] += X

Submission status: Wrong Answer

Solution code:
from collections import deque


class Tree:
    def __init__(self, n, init_list, root=1):
        self.num = (n + 1)
        self.parents = [-1] * self.num
        self.first_child = [-1] * self.num
        self.next_child = [-1] * self.num
        self.check = [-1] * self.num
        self.g = {i: [] for i in range(1, self.num)}
        self.make_g(init_list, root)

    def make_g(self, con, root):
        m = len(con)
        for i in range(m):
            self.g[con[i][0]].append(con[i][1])
            self.g[con[i][1]].append(con[i][0])
        q = deque([root])
        while q != deque():
            node = q.pop()
            self.check[node] = 1
            cnt = 0
            for i, sub_node in enumerate(self.g[node]):
                if self.check[sub_node] != -1:
                    continue
                if cnt == 0:
                    self.first_child[node] = sub_node
                self.parents[sub_node] = node
                if i != len(self.g[node])-1:
                    self.next_child[sub_node] = self.g[node][i+1]
                q.append(sub_node)
                cnt += 1

    def childs(self, node):
        child_list = []
        if self.first_child[node] != -1:
            child_list.append(self.first_child[node])
            node = self.first_child[node]
            while 1:
                if self.next_child[node] == -1:
                    break
                else:
                    child_list.append(self.next_child[node])
                node = self.next_child[node]
        return child_list

    def parent(self, n):
        return self.parents[n]


N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
P = [0] * Q
X = [0] * Q
V = [0] * (N + 1)
for i in range(Q):
    P, X = map(int, input().split())
    V[P] += X

tr = Tree(N, AB)

q = deque()
q.extend(tr.childs(1))
while q != deque():
    node = q.pop()
    V[node] = V[tr.parent(node)]
    if tr.childs(node) != []:
        q.extend(tr.childs(node))

print(*V[1:])

Submission status: Wrong Answer

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

N, Q = map(int, input().split())
counter = {n: 0 for n in range(N + 1)}

# read trees
G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    ai, bi = map(int, input().split())
    G[ai].append(bi)

# dfs
def dfs(node, v):
    queue = deque([node])
    
    while queue:
        n = queue.pop()
        counter[n] += v
        for u in G[n]:
            queue.append(u)

# read query
for _ in range(Q):
    pi, xi = map(int, input().split())

    # dfs from pi with counter xi
    dfs(pi, xi)

# output
for n in range(1, N + 1):
    print(counter[n], end="")
    if n < N:
        print(" ", end="")
print()

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]

'''
def main():
'''
n, q = map(int, input().split())
G = defaultdict(list)
for i in range(n - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
print(G)

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

def dfs(v, pv):
    for nv in G[v]:
        if nv != pv:
            P[nv] += P[v]
            dfs(nv, v)


dfs(0, 0)
print(*P)


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

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]


def main():

    n, q = map(int, input().split())
    G = defaultdict(list)
    for i in range(n - 1):
        a, b = map(int, input().split())
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)
    print(G)

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

    def dfs(v, pv):
        for nv in G[v]:
            if nv != pv:
                P[nv] += P[v]
                dfs(nv, v)


    dfs(0, 0)
    print(*P)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math 
import bisect
import heapq
from operator import mul
from collections import deque

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

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

c = [0] * n

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

seen = [0] * n
seen[0] = 1
next = deque([0])


while next:
    v = next.popleft()
    cost = c[v]

    for nv in g[v]:

        if seen[nv]:
            continue
        seen[nv] = 1
        next.append(nv)
        c[nv] += cost

print(*c)

Submission status: Wrong Answer

Solution code:
import math 
import bisect
import heapq
from operator import mul
from collections import deque

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



def bfs(start):
    # if start == 1:
    #     return [True] * n
    task = deque([])
    seen = [False] * n

    task.append(start)
    seen[start-1] = True

    while task:
        restart = task.popleft()
        seen[restart - 1] = True
        for i in range(len(ab)):
            if seen[ab[i][1] - 1]:
                continue
            elif ab[i][0] == restart:
                next = ab[i][1]
                task.append(next)


    return seen


ans = [0]*n

for i in range(q):
    for j in range(n):
        ans[j] += px[i][1] if bfs(px[i][0])[j] else 0

for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import math 
import bisect
import heapq
from operator import mul
from collections import deque

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



def bfs(start):
    if start == 1:
        return [True] * n
    task = deque([])
    seen = [False] * n

    task.append(start)
    seen[start-1] = True

    while task:
        restart = task.popleft()
        seen[restart - 1] = True
        for i in range(len(ab)):
            if ab[i][0] == restart and not seen[ab[i][1]-1]:
                next = ab[i][1]
                task.append(next)


    return seen


ans = [0]*n

for i in range(q):
    for j in range(n):
        ans[j] += px[i][1] if bfs(px[i][0])[j] else 0

for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import math 
import bisect
import heapq
from operator import mul
from collections import deque

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



def dfs(start):
    if start == 1:
        return [True] * n
    task = deque([])
    seen = [False] * n

    task.append(start)
    seen[start-1] = True

    while task:
        restart = task.pop()
        seen[restart - 1] = True
        for i in range(len(ab)):
            if ab[i][0] == restart and seen[ab[i][1]-1] == False:
                next = ab[i][1]
                task.append(next)


    return seen


ans = [0]*n

for i in range(q):
    for j in range(n):
        ans[j] += px[i][1] if dfs(px[i][0])[j] else 0

for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import math 
import bisect
import heapq
from operator import mul
from collections import deque

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



def dfs(start):
    if start == 1:
        return [True] * n
    task = deque([])
    seen = [False] * n

    task.appendleft(start)
    seen[start-1] = True

    while task:
        restart = task.popleft()
        for i in range(len(ab)):
            if ab[i][0] == restart and seen[ab[i][1]-1] == False:
                next = ab[i][1]
                seen[next-1] = True
                task.appendleft(next)


    return seen


ans = [0]*n

for i in range(q):
    for j in range(n):
        ans[j] += px[i][1] if dfs(px[i][0])[j] else 0

for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import math 
import bisect
import heapq
from operator import mul
from collections import deque

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



def dfs(start):
    if start == 1:
        return [True] * n
    task = deque([])
    seen = [False] * n

    task.appendleft(start)
    seen[start-1] = True

    while task:
        task.popleft()
        for i in range(len(ab)):
            if ab[i][0] == start and seen[ab[i][1]-1] == False:
                next = ab[i][1]
                seen[next-1] = True
                task.appendleft(next)


    return seen


ans = [0]*n

for i in range(q):
    for j in range(n):
        ans[j] += px[i][1] if dfs(px[i][0])[j] else 0

for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import math 
import bisect
import heapq
from operator import mul
from collections import deque

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



def dfs(start):
    if start == 1:
        return [True] * n
    task = deque([])
    seen = [False] * n

    task.appendleft(start)
    seen[start-1] = True

    while task:
        task.popleft()
        for i in range(len(ab)):
            if ab[i][0] == start and seen[ab[i][1]-1] == False:
                next = ab[i][1]
                seen[next-1] = True
                task.appendleft(next)


    return seen


ans = [0]*n

for i in range(q):
    for j in range(n):
        ans[j] += px[i][1] if dfs(px[i][0])[j] else 0
print(ans)

Submission status: Wrong Answer

Solution code:
# D
n,q = map(int, input().split())
p_list = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int, input().split())
    p_list[b].append(a)
ans = [0 for i in range(n)]
for req in range(q):
    reqnode, x = map(int, input().split())
    ans[reqnode-1] += x
for i in range(2,n+1):
    if p_list[i]:
        for parent in p_list[i]:
            ans[i-1] += ans[parent - 1]
print(*ans, sep=' ')

Submission status: Wrong Answer

Solution code:
import sys

#import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig

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

'''
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:
'''

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]
''' 深さ優先探索
def dfs(G, v):
    global time, first_order,seen,last_order
    time += 1
    first_order[v-1] = time   #　行きがけ

    seen[v-1] = True # v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        if seen[next_v-1]:
            continue
        dfs(G, next_v)

    time += 1
    last_order[v - 1] = time  # 帰りがけ
'''

def main():
    N, Q = map(int,input().split())
    G = defaultdict(list)
    for i in range(1, N):
        a, b = map(int,input().split())
        G[a].append(b)
    
    P = []
    for i in range(Q):
        P.append(list(map(int,input().split())))
    #print(P)
    
    seen = [False] * N
    #seen_t = [True]*N
    count = [0] * N
    #print(seen)
    
    def dfs(v, G, seen_v):
        
        seen_v[v-1] = True
        #if len(P[v]) > 0:
        #seen[v-1] += P[v][0]
        # v からいける各頂点 next_v について
        for next_v in G[v]:
            dfs(next_v, G, seen_v)
    
    for i,j in P:
        seen_1 = copy.deepcopy(seen)
        dfs(i, G,seen_1)
        for k in range(N):
            if seen_1[k]:
                count[k] += j
    
    print(*count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

#import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig

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

'''
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:
'''

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]
''' 深さ優先探索
def dfs(G, v):
    global time, first_order,seen,last_order
    time += 1
    first_order[v-1] = time   #　行きがけ

    seen[v-1] = True # v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        if seen[next_v-1]:
            continue
        dfs(G, next_v)

    time += 1
    last_order[v - 1] = time  # 帰りがけ
'''

N, Q = map(int,input().split())
G = defaultdict(list)
for i in range(1, N):
    a, b = map(int,input().split())
    G[a].append(b)

P = []
for i in range(Q):
    P.append(list(map(int,input().split())))
#print(P)

seen = [False] * N
#seen_t = [True]*N
count = [0] * N
#print(seen)

def dfs(v, G, seen_v):

    seen_v[v-1] = True
    #if len(P[v]) > 0:
    #seen[v-1] += P[v][0]
    # v からいける各頂点 next_v について
    for next_v in G[v]:
        dfs(next_v, G, seen_v)

for i,j in P:
    seen_1 = copy.deepcopy(seen)
    dfs(i, G,seen_1)
    for k in range(N):
        if seen_1[k]:
            count[k] += j

print(*count)


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

Submission status: Wrong Answer

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

def main():
    N, Q = map(int, input().split())
    AB = [list(map(int,input().split())) for _ in range(N-1)]
    AB.sort()
    # print(AB)
    roots = [-1 for _ in range(N+1)]
    roots[1] = 0
    ans = [0 for _ in range(N+1)]
    order = [1]
    for r,l in AB:
        if roots[r] == -1:
            roots[r] = l
            order.append(r)
        else:
            roots[l] = r
            order.append(l)
    # print(roots)
    # print(order)
    for _ in range(Q):
        p,x = map(int, input().split())
        ans[p] += x
    # print(ans)
    # for i in range(1,N+1):
    for o in order:
        ans[o] += ans[roots[o]]
        # root = roots[i]
        # for r in roots[i]:
        #     ans[i] += ans[r]
        # if root:
        # ans[i] += ans[roots[i]]
    print(*ans[1:])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, Q = map(int, input().split())
    AB = [list(map(int,input().split())) for _ in range(N-1)]
    AB.sort()
    roots = [0 for _ in range(N+1)]
    ans = [0 for _ in range(N+1)]
    order = [1]
    for r,l in AB:
        if r != 1 and roots[r] == 0:
            roots[r] = l
            order.append(r)
        else:
            roots[l] = r
            order.append(l)
    # print(roots)
    # print(order)
    for _ in range(Q):
        p,x = map(int, input().split())
        ans[p] += x
    # print(ans)
    # for i in range(1,N+1):
    for o in order:
        ans[o] += ans[roots[o]]
        # root = roots[i]
        # for r in roots[i]:
        #     ans[i] += ans[r]
        # if root:
        # ans[i] += ans[roots[i]]
    print(*ans[1:])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, Q = map(int, input().split())
    # AB = [list(map(int,input().split())) for _ in range(N-1)]
    roots = [[] for _ in range(N+1)]
    ans = [0 for _ in range(N+1)]
    for _ in range(N-1):
        root,leaf = map(int,input().split())
        tmp = roots[leaf]
        tmp.append(root)
        roots[leaf] = tmp
    # print(roots)
    for _ in range(Q):
        p,x = map(int, input().split())
        ans[p] += x
    # print(ans)
    for i in range(1,N+1):
        # root = roots[i]
        for r in roots[i]:
            ans[i] += ans[r]
        # if root:
            # ans[i] += ans[roots[i]]
    print(*ans[1:])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, Q = map(int, input().split())
    # AB = [list(map(int,input().split())) for _ in range(N-1)]
    roots = [0 for _ in range(N+1)]
    ans = [0 for _ in range(N+1)]
    for _ in range(N-1):
        root,leaf = map(int,input().split())
        roots[leaf] = root
    # print(roots)
    for _ in range(Q):
        p,x = map(int, input().split())
        ans[p] += x
    # print(ans)
    for i in range(1,N+1):
        ans[i] += ans[roots[i]]
    print(*ans[1:])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

X.sort(key=lambda x:(x[1],x[0]))

c=[0]*(n+1)

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

a=0
for j in range(1,n+1):
    if X[a][1]==j:
        c[j]+=c[X[a][0]]
        a+=1
        if a>n-2:
            break

print(*c[1:])

Submission status: Wrong Answer

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

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

X.sort(key=lambda x:(x[0],x[1]))

c=[0]*(n+1)

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

a=0
for j in range(1,n+1):
    if X[a][1]==j:
        c[j]+=c[X[a][0]]
        a+=1
        if a>n-2:
            break

print(*c[1:])

Submission status: Wrong Answer

Solution code:
from collections import deque
n, q = map(int, input().split())
g = [[] 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())
    c[p-1] = x
used = [0]*n
used[0] = 1
next = deque([0])
while next:
    v = next.popleft()
    cost = c[v]
    for nv in g[v]:
        if used[nv]:
            continue
        used[nv] = 1
        c[nv] += cost
        next.append(nv)

print(*c)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
g = [[] 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())
    c[p-1] = x
used = [0]*n
used[0] = 1
next = [0]
while next:
    v = next.pop()
    cost = c[v]
    for nv in g[v]:
        if used[nv]:
            continue
        used[nv] = 1
        c[nv] += cost
        next.append(nv)

print(*c)

Submission status: Wrong Answer

Solution code:
from collections import deque
def func(n, add, tree):
    ans = [0 for _ in range(n+1)] # ans[i]:頂点iのカウンタ値
    for i,a in enumerate(add[1:], 1):
        q = deque()
        q.append(i)
        while q:
            root = q.popleft()
            ans[root] += a
            leafs = tree[root]
            for leaf in leafs:
                q.append(leaf)
    return ans


def main():
    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)]

    # 木構造を生成
    tree = [[] for _ in range(N+1)]
    for a,b in AB:
        tree[a].append(b)
    # print(tree)

    add = [0 for _ in range(N+1)] # add[i]:頂点iの配下に足す値を保持する
    # 操作を集計
    for p,x in PX:
        add[p] += x
    # print(add)

    ans = func(N,add,tree)
    print(*ans[1:])

if __name__ == "__main__":
    main()