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:
def main():
    N, Q = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(N-1)]
    ab = sorted(ab, key=lambda x: x[1])[::-1]
    tree = [[i] for i in range(N)]
    for a, b in ab:
        tree[a-1] += tree[b-1]
    ans = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        for n in tree[p-1]:
            ans[n] += x
    print(' '.join([str(v) for v in ans]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, Q = map(int, input().split())
    ab = reversed([list(map(int, input().split())) for _ in range(N-1)])
    tree = [[i] for i in range(N)]
    for a, b in ab:
        tree[a-1] += tree[b-1]
    ans = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        for n in tree[p-1]:
            ans[n] += x
    print(' '.join([str(v) for v in ans]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# coding: utf-8

from collections import defaultdict, deque

N, Q = (int(x) for x in input().split())
G = defaultdict(list)

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

ret = [0] * N


for i in range(Q):
    p, x = (int(x) for x in input().split())
    que = deque()
    que.append(p-1)
    while(que):
        node = que.popleft()
        ret[node] += x
        for next_node in G[node]:
            que.append(next_node)


print(" ".join(str(x) for x in ret))

Submission status: Wrong Answer

Solution code:
#
# abc138 d
#
import sys
from io import StringIO
import unittest
from collections import deque


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 3
1 2
2 3
2 4
2 10
1 100
3 1"""
        output = """100 110 111 110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10"""
        output = """20 20 20 20 20 20"""
        self.assertIO(input, output)


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

    G = [[i+1, 0] for i in range(N)]
    for ab in AB:
        a, b = ab
        G[a-1][1] += 1
        G[a-1].append(b)

    ans = [0] * N
    for px in PX:
        p, x = px
        ans[p-1] += x

    S = deque()

    F = [False] * N
    S.append(1)
    F[0] = True

    while S:
        p = S.pop()
        if G[p-1][1] == 0:
            continue

        for np in G[p-1][2:]:
            if F[np-1]:
                continue
            S.append(np)
            F[np-1] = True
            ans[np-1] += ans[p-1]

    print(*ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
#
# abc138 d
#
import sys
from io import StringIO
import unittest
from collections import deque


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 3
1 2
2 3
2 4
2 10
1 100
3 1"""
        output = """100 110 111 110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10"""
        output = """20 20 20 20 20 20"""
        self.assertIO(input, output)


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

    G = [[i+1, 0] for i in range(N)]
    for ab in AB:
        a, b = ab
        G[a-1][1] += 1
        G[a-1].append(b)

    ans = [0] * N
    S = deque()

    for px in PX:
        F = [False] * N
        p, x = px
        S.append(p)
        F[p-1] = True

        while S:
            cp = S.pop()
            ans[cp-1] += x

            if G[cp-1][1] == 0:
                continue

            for np in G[cp-1][2:]:
                if F[np-1]:
                    continue
                S.append(np)

    print(*ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
#
# abc138 d
#
import sys
from io import StringIO
import unittest
from collections import deque


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 3
1 2
2 3
2 4
2 10
1 100
3 1"""
        output = """100 110 111 110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10"""
        output = """20 20 20 20 20 20"""
        self.assertIO(input, output)


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

    ans = [0] * N
    S = deque()

    for px in PX:
        p, x = px
        S.append(p)

        while S:
            cp = S.pop()
            ans[cp-1] += x

            for ab in AB:
                a, b = ab
                if a != cp:
                    continue
                S.append(b)

    print(*ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
root = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    root[b-1].append(a)
ans = [0] * N
for i in range(Q):
    p,x = map(int,input().split())
    ans[p-1] += x
for i in range(N):
    for j in root[i]:
        ans[i] += ans[j-1]
print(*ans)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
root = [0]*N
for i in range(N-1):
    a,b = map(int,input().split())
    root[b-1] = a
ans = [0] * N
for i in range(Q):
    p,x = map(int,input().split())
    ans[p-1] += x
for i in range(N):
    if root[i] != 0:
        ans[i] += ans[root[i]-1]
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    n, m = map(int, input().split())

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

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

    q = deque()
    q.append(0)
    visited = [False] * n
    visited[0] = True

    while q:
        u = q.pop()
        for v in adj[u]:
            if visited[v]:
                continue
            ans[v] += ans[u]
            q.append(v)
            visited[v] = True

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        point[u] += point[v]
        dfs(u,v)

N, Q = (map(int,input().split()))
graph = [[] for _ in range(N)]
point = [0]*N

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

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

dfs(0)
print(*point)

Submission status: Wrong Answer

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

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        point[u] += point[v]
        dfs(u,v)

N, Q = list(map(int,input().split()))
graph = [[] for _ in range(N)]
point = [0]*N

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

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

dfs(0)
print(*point)

Submission status: Wrong Answer

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

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        point[u] += point[v]
        dfs(u,v)

N, Q = list(map(int,input().split()))
graph = [[] for _ in range(N)]
point = [0]*N

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

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

dfs(0)
print(*point)

Submission status: Wrong Answer

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, q = read_ints()
    tree = [[] for _ in range(n)]
    c = [0] * n
    for _ in range(n-1):
        a, b = read_ints()
        tree[~-a].append(~-b)
    for _ in range(q):
        p, x = read_ints()
        c[~-p] += x
    for i in range(n):
        for val in tree[i]:
            c[val] += c[i]
    print(*c)

if __name__ == '__main__':
    Main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit
from numba.types import Array, int32
i4 = np.int32
import sys

if sys.argv[-1] != 'ONLINE_JUDGE':
    adjacency_list = '''
import numpy as np
from numba import njit
from collections import namedtuple

AdjacencyList = namedtuple('AdjacencyList', ['v', 'adj'])

@njit
def adjacency_list(n, a):
    """
    隣接リストの作成
    :param n: vertex の数
    :param a: 2d の ndarray, 各行は、[u, v] u: Edge の始点、v: Edge の終点
    :return: AdjacencyList
    """
    v = np.zeros(n + 1, np.int32)
    for i in range(a.shape[0]):
        v[a[i, 0] + 1] += 1
    for i in range(1, v.shape[0]):
        v[i] += v[i - 1]
    adj = np.empty(a.shape[0], np.int32)
    temp = np.zeros(n, np.int32)
    for i in range(a.shape[0]):
        from_ = a[i, 0]
        adj[v[from_] + temp[from_]] = a[i, 1]
        temp[from_] += 1
    return AdjacencyList(v, adj)


@njit
def at(gc, n):
    return gc.adj[gc.v[n]:gc.v[n + 1]]


@njit
def iter(gc, n):
    for i in range(gc.v[n], gc.v[n + 1]):
        yield gc.adj[i]        
    '''
    import os
    os.makedirs('nbacl/graphs', exist_ok=True)
    f = open('nbacl/graphs/adjacency_list.py', 'w')
    f.write(adjacency_list)
    f.close()

import nbacl.graphs.adjacency_list as tree

@njit((int32, int32, Array(int32, 1, 'C'), Array(int32, 1, 'C'), Array(int32, 1, 'C'), Array(int32, 1, 'C')))
def dfs(d, prev, v, adj, u, val):
    y = val[d]
    for i in range(v[d], v[d + 1]):
        x = adj[i]
        if x == prev:
            continue
        val[x] = y + u[x]
        dfs(x, d, v, adj, u, val)


@njit((Array(int32, 2, 'C'), Array(int32, 2, 'C'), int32), cache=True)
def solve(a, p, N):
    tr = tree.adjacency_list(N, a)
    u = np.zeros(N, i4)
    val = np.zeros(N, i4)
    for i in range(p.shape[0]):
        u[p[i, 0] - 1] += p[i, 1]
    val[0] = u[0]
    dfs(0, -1, tr.v, tr.adj, u, val)
    return val


def main():
    f = open(0)
    N, Q = [int(x) for x in f.readline().split()]
    ap = np.fromstring(f.read(), i4, sep=' ').reshape((-1, 2))
    a = ap[:N - 1] - 1
    p = ap[N - 1:]
    val = solve(a, p, N)
    print(*val.tolist())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit
from numba.types import Array, int32
# import nbacl.graphs.adjacency_list as tree
i4 = np.int32

@njit
def adjacency_list(n, a):
    """
    隣接リストの作成
    :param n: vertex の数
    :param a: 2d の ndarray, 各行は、[u, v] u: Edge の始点、v: Edge の終点
    :return: AdjacencyList
    """
    v = np.zeros(n + 1, np.int32)
    for i in range(a.shape[0]):
        v[a[i, 0] + 1] += 1
    for i in range(1, v.shape[0]):
        v[i] += v[i - 1]
    adj = np.empty(a.shape[0], np.int32)
    temp = np.zeros(n, np.int32)
    for i in range(a.shape[0]):
        from_ = a[i, 0]
        adj[v[from_] + temp[from_]] = a[i, 1]
        temp[from_] += 1
    return v, adj


@njit((int32, int32, Array(int32, 1, 'C'), Array(int32, 1, 'C'), Array(int32, 1, 'C'), Array(int32, 1, 'C')))
def dfs(d, prev, v, adj, u, val):
    y = val[d]
    for i in range(v[d], v[d + 1]):
        x = adj[i]
        if x == prev:
            continue
        val[x] = y + u[x]
        dfs(x, d, v, adj, u, val)


@njit((Array(int32, 2, 'C'), Array(int32, 2, 'C'), int32), cache=True)
def solve(a, p, N):
    v, adj = adjacency_list(N, a)
    u = np.zeros(N, i4)
    val = np.zeros(N, i4)
    for i in range(p.shape[0]):
        u[p[i, 0] - 1] += p[i, 1]
    val[0] = u[0]
    dfs(0, -1, v, adj, u, val)
    return val


def main():
    f = open(0)
    N, Q = [int(x) for x in f.readline().split()]
    ap = np.fromstring(f.read(), i4, sep=' ').reshape((-1, 2))
    a = ap[:N - 1] - 1
    p = ap[N - 1:]
    val = solve(a, p, N)
    print(*val.tolist())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

B = [0]*N
for i in range(N):
    ans = A[i] + B[P[i]]
    B[i] = ans
    print(ans, end=' ')

print()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
  n,q=map(int,input().split())
  node=[[]*n for i in range(n)]
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    node[b].append(a)
    node[a].append(b)
  
  root=[-1]*n
  edge=[[]*n for i in range(n)]
  root[0]=0
  for r,es in enumerate(node):
    for e in es:
      if root[r]==-1:
        root[r]=e
      else:
        edge[r].append(e)
  
  
  ans=[0]*n
  for i in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x
  
  p=[0]*n
  q=deque(edge[0])
  visited=[False]*n
  while q:
    e=q.popleft()
    p[e]=p[root[e]]+1
    for e2 in edge[e]:
      if not visited[e2]:
        visited[e2]=True
        q.append(e2)
  
  p=sorted(enumerate(p), key=lambda x:x[1])
  for i in range(1,n):
    e=p[i][0]
    r=root[e]
    ans[e]+=ans[r]
    
  print(*ans,sep=' ')


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
  n,q=map(int,input().split())
  root=[0]*n
  edge=[[]*n for i in range(n)]
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    root[b]=a
    edge[a].append(b)
    
  ans=[0]*n
  for i in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x
  
  p=[0]*n
  q=deque(edge[0])
  visited=[False]*n
  while q:
    e=q.popleft()
    p[e]=p[root[e]]+1
    for e2 in edge[e]:
      if not visited[e2]:
        visited[e2]=True
        q.append(e2)
  
  p=sorted(enumerate(p), key=lambda x:x[1])
  for i in range(1,n):
    e, r=p[i][0], root[p[i][0]]
    ans[e]+=ans[r]
    
  print(*ans,sep=' ')


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  n,q=map(int,input().split())
  g=[[] for i in range(n)]
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    g[b].append(a)
    
  ans=[0]*n
  for i in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x
  
  g=sorted(enumerate(g), key=lambda x:(len(x[1]), x[1]))
  #print(g)
  for i in range(n):
    e,rs=g[i][0],g[i][1]
    for r in rs:
      ans[e]+=ans[r]
    
  print(*ans,sep=' ')


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  n,q=map(int,input().split())
  g=[[] for i in range(n)]
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    g[b].append(a)
    
  ans=[0]*n
  for i in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x
  
  g=sorted(enumerate(g), key=lambda x:(len(x[1]), x[1]))
  #print(g)
  for i in range(n):
    e,rs=g[i][0],g[i][1]
    for j in rs:
      ans[i]+=ans[j]
    
  print(*ans,sep=' ')


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  n,q=map(int,input().split())
  g=[[] for i in range(n)]
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    g[b].append(a)
    
  ans=[0]*n
  for i in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x

  for i in range(n):
    for j in g[i]:
      ans[i]+=ans[j]
    
  print(*ans,sep=' ')


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

destinations = [0 for _ in range(N+1)]
visited = [False for _ in range(N+1)]
route = deque([1])
visited[1] = True

last = 0
while len(route) > 0:
  current = route.pop()
  for _next in routings[current]:
    if not visited[_next]:
      route.appendleft(_next)
      destinations[_next] = destinations[current] + 1
      last = destinations[_next]
      visited[_next] = True

layer_points = [0 for _ in range(last+1)]
accumulates = [0 for _ in range(last+1)]
points = [0 for _ in range(N+1)]
for _ in range(Q):
  p, x = map(int, input().split())
  if destinations[p] < last:
    layer_points[destinations[p]+1] += x
  points[p] += x
accumulates[0] = layer_points[0]
for i in range(last):
  accumulates[i+1] = accumulates[i] + layer_points[i+1]
for i in range(1, N+1):
  points[i] += accumulates[destinations[i]]
print(' '.join(map(str, points[1:])))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

destinations = [0 for _ in range(N+1)]
visited = [False for _ in range(N+1)]
route = deque([1])
visited[1] = True

last = 0
while len(route) > 0:
  current = route.pop()
  for _next in routings[current]:
    if not visited[_next]:
      route.appendleft(_next)
      destinations[_next] = destinations[current] + 1
      last = destinations[_next]
      visited[_next] = True

layer_points = [0 for _ in range(last+1)]
accumulates = [0 for _ in range(last+1)]
points = [0 for _ in range(N+1)]
for _ in range(Q):
  p, x = map(int, input().split())
  if destinations[p] < last:
    layer_points[destinations[p]+1] += x
  points[p] += x
accumulates[0] = layer_points[0]
for i in range(last):
  accumulates[i+1] = accumulates[i] + layer_points[i+1]
for i in range(1, N+1):
  points[i] += accumulates[destinations[i]]

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
N, Q = [int(n) for n in input().split()]
 
tree_list = [[] for _ in range(N)]
count_list = [0] * N
 
for i in range(N-1):
    a, b = [int(n)-1 for n in input().split()]
    tree_list[a].append(b)
 
#print(tree_list)
#print(count_list)
 
for j in range(Q):
    p, x = [int(n) for n in input().split()]
 
    def func(pn, xn):
        count_list[pn] += xn
        if not tree_list[pn]:
            return
        for k in tree_list[pn]:
            func(k, xn)
 
    func(p-1, x)
    
#print(count_list)
 
print(*count_list)

Submission status: Wrong Answer

Solution code:
def main():
  n,q=map(int,input().split())
  g=[[] for i in range(n)]
  g2=[[] for i in range(n)]
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    g[a].append(b)
    g[b].append(a)
  
  #print(g)
  
  for edge in reversed(range(n)):
    for root in g[edge]:
      if root<edge:
        g2[root]=set(g2[edge])|set(g[edge])|set(g[root])|set(g2[root])
  
  print(g2)
  ans=[0]*n
  """
  for i in range(q):
    root,x=map(int,input().split())
    root-=1
    ans[root]+=x
    for edge in g2[root]:
      if root<edge:
        ans[edge]+=x
  """
  print(*ans,sep=' ')


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  n,q=map(int,input().split())
  g=[[] for i in range(n)]
  g2=[set([]) for i in range(n)]
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    g[a].append(b)
    g[b].append(a)
  
  #print(g)
  
  for edge in reversed(range(n)):
    for root in g[edge]:
      if edge>root:
        g2[root]|=set(g2[edge])|set(g[edge])|set(g[root])
  
  #print(g2)
  
  ans=[0]*n
  for i in range(q):
    root,x=map(int,input().split())
    root-=1
    ans[root]+=x
    for edge in g2[root]:
      if root<edge:
        ans[edge]+=x
  
  print(*ans,sep=' ')


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque


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

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

    visited=[False]*n
    used=[False]*n
    q=deque([])
    for idx in g[p]:
       q.append(idx)
    visited[p]=True
    used[p]=True
    while q:
      t=q.pop()
      if not used[t]:
        ans[t]+=x
        used[t]=True
      for idx in g[t]:
        if not visited[idx]:
          q.append(idx)
          visited[idx]=True

  print(*ans,sep=' ')


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
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)]

tree = [[] for _ in range(N)]
for a, b in ab:
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)

counter = [0] * N
for p, x in px:
  counter[p-1] += x
  
flag = [1] * N
t = deque()
t.append(0)
print(tree)

#1(0)から順に探索していけば、自然と親→子の順番になる
while t:
  v = t.popleft()
  flag[v] = 0
  for i in tree[v]:
    if flag[i]:
      counter[i] += counter[v]
      t.append(i)
      
print(*counter)

Submission status: Wrong Answer

Solution code:
from operator import *
N,Q = map(int,input().split())
AB = sorted([list(map(int,input().split())) for n in range(N-1)])
PX = [list(map(int,input().split())) for q in range(Q)]
ans = N*[0]

for p,x in PX:
  ans[p-1]+=x

for a,b in AB:
  ans[b-1]+=ans[a-1]

print(*ans)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
T = (N+1)*[0]
V = (N+1)*[0]

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

for q in range(Q):
  p,x = map(int,input().split())
  V[p]+=x
  
for n in range(1,N+1):
  V[n]+=V[T[n]]

print(*V[1:])

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
edges=[]
points=[0]*N
parents=[-1]*N
for i in range(N-1):
  l=list(map(int,input().split()))
  l[0]-=1
  l[1]-=1
  edges.append(l)
edges.sort()
for edge in edges:
  parents[edge[1]]=edge[0]

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

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
edges=[]
points=[0]*N
parents=[0]*N
childs=[[] for i in range(N)]
for i in range(N-1):
  l=list(map(int,input().split()))
  l[0]-=1
  l[1]-=1
  edges.append(l)
edges.sort()

for edge in edges:
  parents[edge[1]]=edge[0]
  childs[edge[0]].append(edge[1])

for i in range(Q):
  p,x=map(int,input().split())
  points[p-1]+=x
ans=[]
l=[0]
while l:
  n=l.pop(0)
  ans.append(points[n])
  for i in childs[n]:
    points[i]+=points[n]
    l.append(i)

print(*ans)

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
edges=[]
points=[0]*N
parents=[0]*N
for i in range(N-1):
  l=list(map(int,input().split()))
  l[0]-=1
  l[1]-=1
  edges.append(l)
edges.sort()
for edge in edges:
  parents[edge[1]]=edge[0]

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

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())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    
X =[0]*n
for w in range(q):
    p,x = map(int,input().split())
    X[p-1]+=x
    
def bfs(u):
    queue = deque([u])
    d = [None]*n
    
    d[u] = 0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v]+1
                X[i] = X[v]
                queue.append(i)
    return d

p = [None]*n
d = bfs(0)

print(*X)

Submission status: Wrong Answer

Solution code:
N,Q = map(int, input().split())
 
V = [0]*N
 
A = []
for i in range(N-1):
    a,b = map(int, input().split())
    A.append((a,b))
A.sort()
P = []
for i in range(Q):
    x,y = map(int, input().split())
    P.append((x,y))
P.sort()
 
#print("V", V)
#print("A", A)
#print("P", P)
 
for p in P:
    V[p[0]-1] += p[1]
for a in A:
    V[a[1]-1] += V[a[0]-1]
 
print(*V)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,q = map(int,input().split())
h = [[] for _ in range(n)]

for _ in range(n-1):
    c,d = map(int,input().split())
    c-=1
    d-=1
    h[c].append(d)
    
P =[0]*q
X =[0]*q
for w in range(q):
    p,x = map(int,input().split())
    P[w]+=p-1
    X[w]+=x
    
z = [0]*n

def bfs(p,x):
    queue = deque([p])
    z[p]+=x
    
    while queue:
        v=queue.popleft()
        
        for i in h[v]:
            z[i]+=x
            queue.append(i)
            
for j in range(q):
    d = bfs(P[j],X[j])

print(*z)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,q = map(int,input().split())
h = [[] for _ in range(n)]

for _ in range(n-1):
    c,d = map(int,input().split())
    c-=1
    d-=1
    h[c].append(d)
    
X =[0]*n
for w in range(q):
    p,x = map(int,input().split())
    X[p-1]+=x
    
z = [0]*n

def bfs(u,x):
    queue = deque([u])
    z[u]+=x
    
    while queue:
        v=queue.popleft()
        
        for i in h[v]:
            z[i]+=x
            queue.append(i)
            
for u in range(n):
    d = bfs(u,X[u])

print(*z)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,q = map(int,input().split())
h = [[] for _ in range(n)]

for _ in range(n-1):
    c,d = map(int,input().split())
    c-=1
    d-=1
    h[c].append(d)
    
P =[0]*q
X =[0]*q
for w in range(q):
    p,x = map(int,input().split())
    P[w]+=p-1
    X[w]+=x
    
z = [0]*n

def bfs(p,x):
    queue = deque([p])
    z[p]+=x
    
    while queue:
        v=queue.popleft()
        
        for i in h[v]:
            z[i]+=x
            queue.append(i)
            
for j in range(q):
    d = bfs(P[j],X[j])

Z=[str(a) for a in z]
Z=" ".join(Z)
print(Z)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,q = map(int,input().split())
h = [[] for _ in range(n)]

for _ in range(n-1):
    c,d = map(int,input().split())
    c-=1
    d-=1
    h[c].append(d)
    
P =[0]*q
X =[0]*q
for w in range(q):
    p,x = map(int,input().split())
    P[w]+=p-1
    X[w]+=x
    
z = [0]*n

def bfs(p,x):
    queue = deque([p])
    z[p]+=x
    
    while queue:
        v=queue.popleft()
        
        for i in h[v]:
            z[i]+=x
            queue.append(i)
            
for j in range(q):
    d = bfs(P[j],X[j])

print(z)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
edge=[[] for _ in range(n)]
o=[0]*n
for i in range(n-1):
    x,y=map(int,input().split())
    if o[y-1]:
        edge[y-1].append(x-1)
    else:
        edge[x-1].append(y-1)
        o[y-1]+=1
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
for i in range(n):
    for j in edge[i]:
        ans[j]+=ans[i]
print(*ans)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
edge=[[] for _ in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
for i in range(n):
    for j in edge[i]:
        ans[j]+=ans[i]
print(*ans)