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
from collections import OrderedDict
sys.setrecursionlimit(2*(10**5))


class Graph():
    def __init__(self):
        self.adjacency_dict = OrderedDict()
        self.counter_dict = OrderedDict()
        self.x_dict = OrderedDict()

    def add_vertex(self, v):
        self.adjacency_dict[v] = []
        self.counter_dict[v] = 0
        self.x_dict[v] = 0

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].append(v2)

    def add_x(self, v, x):
        self.x_dict[v] += x

    def dfs(self, start, count=None, visited=None):
        if visited is None:
            visited = []
        if count is None:
            count = self.x_dict[start]
        self.counter_dict[start] = count
        visited.append(start)
        print(start)
        for v in self.adjacency_dict[start]:
            if v in visited:
                continue
            self.dfs(v, count + self.x_dict[v], visited)

    def print_counters(self):
        print(*self.counter_dict.values())


def main():
    n, q = map(int, input().split())
    tree = Graph()
    for v in range(1, n+1):
        tree.add_vertex(v)
    for _ in range(n-1):
        a, b = map(int, input().split())
        a = min(a, b)
        b = max(a, b)
        tree.add_edge(a, b)
    for _ in range(q):
        p, x = map(int, input().split())
        tree.add_x(p, x)
    tree.dfs(1)
    tree.print_counters()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import OrderedDict
sys.setrecursionlimit(2*(10**5))


class Graph():
    def __init__(self):
        self.adjacency_dict = OrderedDict()
        self.counter_dict = OrderedDict()
        self.x_dict = OrderedDict()

    def add_vertex(self, v):
        self.adjacency_dict[v] = []
        self.counter_dict[v] = 0
        self.x_dict[v] = 0

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].append(v2)

    def add_x(self, v, x):
        self.x_dict[v] += x

    def dfs(self, start, count=None, visited=None):
        if visited is None:
            visited = []
        if count is None:
            count = self.x_dict[start]
        self.counter_dict[start] = count
        visited.append(start)
        # print(start)
        for v in self.adjacency_dict[start]:
            if v in visited:
                continue
            self.dfs(v, count + self.x_dict[v], visited)

    def print_counters(self):
        print(*self.counter_dict.values())


def main():
    n, q = map(int, input().split())
    tree = Graph()
    for v in range(1, n+1):
        tree.add_vertex(v)
    for _ in range(n-1):
        a, b = map(int, input().split())
        tree.add_edge(a, b)
    for _ in range(q):
        p, x = map(int, input().split())
        tree.add_x(p, x)
    tree.dfs(1)
    tree.print_counters()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import OrderedDict


class Graph():
    def __init__(self):
        self.adjacency_dict = OrderedDict()
        self.counter_dict = OrderedDict()

    def add_vertex(self, v):
        self.adjacency_dict[v] = []
        self.counter_dict[v] = 0

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].append(v2)

    def dfs_stack(self, start, count):
        stack = [start]
        visited = []

        while stack != []:
            current_vertex = stack.pop()
            self.counter_dict[current_vertex] += count
            visited.append(current_vertex)
            for v in self.adjacency_dict[current_vertex]:
                if v not in visited and v not in stack:
                    stack.append(v)

    def print_counters(self):
        print(*self.counter_dict.values())


def main():
    n, q = map(int, input().split())
    tree = Graph()
    for v in range(1, n+1):
        tree.add_vertex(v)
    for _ in range(n-1):
        a, b = map(int, input().split())
        tree.add_edge(a, b)
    for _ in range(q):
        p, x = map(int, input().split())
        tree.dfs_stack(p, x)
    tree.print_counters()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import queue
import sys
sys.setrecursionlimit(5*10**5)

N, Q = map(int, input().split())
ab=[]
for _ in range(N-1):
    ab.append(tuple(map(int, input().split())))
px=[]
for _ in range(Q):
    px.append(tuple(map(int, input().split())))

cnt=[0]*(N+1)
for el in px:
    cnt[el[0]]+=el[1]
#print(cnt)

todo=queue.Queue()


lst=[[] for _ in range(N+1)]
for el in ab:
    lst[el[0]].append(el[1])
#print(lst)

def bfs(n):

    for child in lst[n]:
        cnt[child]+=cnt[n]
        todo.put(child)
    if not todo.empty():
        bfs(todo.get())
    else:
        return None

bfs(1)
#print(cnt)
print(' '.join(list(map(str, cnt[1:]))))

Submission status: Wrong Answer

Solution code:
import queue
import sys
sys.setrecursionlimit(5*10**5)

N, Q = map(int, input().split())
ab=[]
for _ in range(N-1):
    ab.append(tuple(map(int, input().split())))
px=[]
for _ in range(Q):
    px.append(tuple(map(int, input().split())))

cnt=[0]*(N+1)
for el in px:
    cnt[el[0]]+=el[1]
#print(cnt)

todo=queue.Queue()


lst=[[] for _ in range(N+1)]
for el in ab:
    lst[el[0]].append(el[1])
#print(lst)

def bfs(n):

    for child in lst[n]:
        cnt[child]+=cnt[n]
        todo.put(child)
    if not todo.empty():
        bfs(todo.get(0))
    else:
        return None

bfs(1)
#print(cnt)
print(' '.join(list(map(str, cnt[1:]))))

Submission status: Wrong Answer

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

todo = []
ans = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    done = set()
    todo.append(p - 1)
    while todo:
        c = todo.pop()
        for n in T[c]:
            if not n in done:
                todo.append(n)
        done.add(c)
        ans[c] += x

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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(G, v, p, point):
    """G: graph, v: vertex, p: parent"""
    point[v] += point[p]
    # Loop for each child
    for c in G[v]:
        if c == p:
            continue
        dfs(G, c, v, point)


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

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

    dfs(G, 0, -1, point)
    print(" ".join(map(str, point)))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

# ポイント
node = [0]*N
for i in p:
    node[i[0]-1] += i[1]
# 葉の集合
seed = [[] for _ in range(N)]
for i in a:
    seed[i[0]-1].append(i[1]-1)
stack = [[0, 0]]
result = [0] * N
tuka = [0]
while len(stack) > 0:
    n = stack.pop(-1)
    result[n[0]] = n[1] + node[n[0]]
    for j in seed[n[0]]:
        if not j in tuka:
            tuka.append(j)
            stack += [[j, result[n[0]]]]


print(*result)

Submission status: Wrong Answer

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

# ポイント
node = [0]*N
for i in p:
    node[i[0]-1] += i[1]
# 葉の集合
seed = [[] for _ in range(N)]
for i in a:
    seed[i[0]-1].append(i[1]-1)
stack = [[0, 0]]
result = [0] * N
tuka = []
while len(stack) > 0:
    n = stack.pop(-1)
    tuka.append(n[0])
    result[n[0]] = n[1] + node[n[0]]
    for j in seed[n[0]]:
        if not j in tuka:
            stack += [[j, result[n[0]]]]


print(*result)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)

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

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

def dfs(v):
  for nv in tree[v]:
    points[nv] += points[v]
    dfs(nv)

dfs(0)
print(*points)

Submission status: Wrong Answer

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

nd = [[] for i in range(n+1)]
ans = [0] * (n+1)

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


def f(pi, xi):
    ans[pi] += xi
    c[pi] = False
    for j in nd[pi]:
        if c[j]:
            f(j, ans[pi])

for _ in range(q):
    c = [True for ii in range(n+1)]
    p, x = map(int, input().split())

    ans[p] += x
# j = nd[1]
# x = ans[1]

c[1] = False
for jj in nd[1]:
    c[jj] = False
    f(jj, ans[1])

print(*ans[1:])

Submission status: Wrong Answer

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

nd = [[] for i in range(n+1)]
ans = [0] * (n+1)

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


def f(pi, xi):
    # print(pi, xi)
    if c[pi]:
        return c
    else:
        c[pi] = True

    ans[pi] += xi
    for j in nd[pi]:
        f(j, ans[pi])
    return c


for _ in range(q):
    c = [False for ii in range(n+1)]
    p, x = map(int, input().split())

    ans[p] += x
# j = nd[1]
# x = ans[1]

p1 = 1
x = ans[p1]

for jj in nd[p1]:
    f(jj, x)

print(*ans[1:])

Submission status: Wrong Answer

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


def dfs(graph,start,point,mark_dict):
    global tree_point
    mark_dict[start] = True
    tree_point[start] += point
    for target in graph[start]:
        if target not in mark_dict:
            mark_dict[target] = True
            dfs(graph,target,tree_point[start],mark_dict)


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

tree = [[] for _ in range(n+1)]
tree_point = [0] * (n+1)

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

for _ in range(q):
    array = list(map(int, input().split()))
    tree_point[array[0]] += array[1]

dfs(tree,1,0,mark_dict={})

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

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
tree=[[]for _ in range(n)]
for _ in range(1,n):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)
counter=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    qu=[p-1]
    while qu:
      y=qu.pop(0)
      counter[y]+=x
      for i in tree[y]:
        qu.append(i)
print(*counter)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())
tree = [[] for i in range(n)]
ans = [0]*n
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    # tree[b].append(a)

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

c = [0]
while c:
    d = c.pop()
    for i in tree[d]:
        ans[i] += ans[d]
        c.append(i)

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,q = map(int,sys.stdin.readline().rstrip().split())
t = {}
for i in range(n-1):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    if a in t:
        t[a].append(b)
    else:
        t[a] = [b]
ans = [0 for i in range(n)]

def search(j):
    if j in t:
        l = [j]
        for k in t[j]:
            l = l + search(k)
    else:
        l = [j]
    return l

for i in range(q):
    p,x = map(int,sys.stdin.readline().rstrip().split())
    s = search(p)
    for i in s:
        ans[i-1] += x
print(" ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import setitem

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def main():
    n, q = map(int, input().split())
    edges = {i: 0 for i in range(n+1)}

    bigroot = False
    for a, b in readlines(n-1):
        if not bigroot and edges[b] > 0:
            edges = {v: k for k, v in edges.items()}
            bigroot = True

        if bigroot:
            edges[a] = b
        else:
            edges[b] = a

    counter = [0] * (n+1)

    for q, x in readlines(q):
        counter[q] += x

    iterator = range(n, 0, -1) if bigroot else range(1, n+1)
    for i in iterator:
        parent = edges.get(i)
        if parent is None:
            continue
        counter[i] += counter[parent]

    print(" ".join(map(str, counter[1:])))

main()

Submission status: Wrong Answer

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

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def main():
    n, q = map(int, input().split())
    edges = [0] * (n+1)
    for a, b in readlines(n-1):
        edges[b] = a

    counter = [0] * (n+1)

    for q, x in readlines(q):
        counter[q] += x

    for i in range(2, n+1):
        parent = edges[i]
        counter[i] += counter[parent]

    print(" ".join(map(str, counter[1:])))

main()

Submission status: Wrong Answer

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

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def main():
    n, q = map(int, input().split())
    edges = [0] * (n+1)
    for a, b in readlines(n-1):
        edges[b] = a

    counter = [0] * (n+1)

    for q, x in readlines(q):
        counter[q] += x

    for i in range(n+1):
        parent = edges[i]
        counter[i] += counter[parent]

    print(" ".join(map(str, counter[1:])))

main()

Submission status: Wrong Answer

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

N, Q = list(map(int, input().split()))
nodes = [[] for i in range(N)]
for i in range(N-1):
  r, e = list(map(int, input().split()))
  r, e = r - 1, e - 1
  nodes[r].append(e)
  nodes[e].append(r)
#print(nodes)

result = [0] * N
for i in range(Q):
  r, s = list(map(int, input().split()))
  result[r-1] += s

def dfs(r, prev=-1):
  for i in nodes[r]:
    if i == prev:
      continue
    result[i] += result[r]
    dfs(i, r)

dfs(0)
#print(" ".join(map(str, result)))

Submission status: Wrong Answer

Solution code:
import copy
N, Q = list(map(int, input().split()))
nodes = dict()
for i in range(N-1):
  r, e = list(map(int, input().split()))
  if r not in nodes:
    nodes[r] = [e]
  else:
    nodes[r].append(e)
#print(nodes)

result = [0] * N
edges = []
for i in range(Q):
  r, s = list(map(int, input().split()))
  result[r-1] += s
  if r in nodes:
    edges = copy.copy(nodes[r])
  while len(edges) != 0:
    r = edges.pop(0)
    result[r-1] += s
    if r in nodes:
      edges.extend(nodes[r])
      #print(edges, nodes[r])
  #print(result)
print(" ".join(map(str, result)))

Submission status: Wrong Answer

Solution code:
N, Q = [int(i) for i in input().split()]
G = [[] for _ in range(N)]
counter = [0] * N
res = [0] * N
visited = [0] * N

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

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

# def dfs(G, v, p):
#     visited[v] = 1
#     res[v] = res[p]+counter[v]
#     for nv in G[v]:
#         if visited[nv]: continue
#         dfs(G, nv, v)

stack = [0]
v = 0
while stack:
    p = v
    v = stack.pop()
    visited[v] = 1
    res[v] = res[p]+counter[v]
    for nv in G[v]:
        if visited[nv]: continue
        stack.append(nv)

# dfs(G, 0, 0)
print(*res)

Submission status: Wrong Answer

Solution code:
import copy
N, Q = list(map(int, input().split()))
nodes = dict()
for i in range(N-1):
  r, e = list(map(int, input().split()))
  if r not in nodes:
    nodes[r] = [e]
  else:
    nodes[r].append(e)
#print(nodes)

result = [0] * N
edges = []
for i in range(Q):
  r, s = list(map(int, input().split()))
  result[r-1] += s
  if r in nodes:
    edges = copy.copy(nodes[r])
  while len(edges) != 0:
    r = edges.pop(0)
    result[r-1] += s
    if r in nodes:
      edges.extend(nodes[r])
      #print(edges, nodes[r])
  #print(result)
print(" ".join(map(str, result)))

Submission status: Wrong Answer

Solution code:
import copy
N, Q = list(map(int, input().split()))
nodes = dict()
for i in range(N-1):
  r, e = list(map(int, input().split()))
  if r not in nodes:
    nodes[r] = [e]
  else:
    nodes[r].append(e)
#print(nodes)

result = [0] * N
edges = []
for i in range(Q):
  r, s = list(map(int, input().split()))
  result[r-1] += s
  if r in nodes:
    edges = copy.copy(nodes[r])
  while len(edges) != 0:
    r = edges.pop(0)
    result[r-1] += s
    if r in nodes:
      edges.extend(nodes[r])
      #print(edges, nodes[r])
  #print(result)
print(result)

Submission status: Wrong Answer

Solution code:
import queue

class Tree:
    def __init__(self, ind):
        self.children = []
        self.counter = 0
        self.index = ind


N, Q = map(int, input().split(" "))
tree = [Tree(i) for i in range(N)]
ans = [0 for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split(" "))
    tree[a - 1].children.append(b - 1)

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

# bfs
que = queue.Queue()
que.put(0)  # root is 0

while not que.empty():
    ind = que.get()
    ans[ind] = tree[ind].counter
    for child in tree[ind].children:
        tree[child].counter += tree[ind].counter
        que.put(child)

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

Submission status: Wrong Answer

Solution code:
import queue

class Tree:
    def __init__(self, ind):
        self.children = []
        self.counter = 0
        self.index = ind


N, Q = map(int, input().split(" "))
tree = [Tree(i) for i in range(N)]
ans = [0 for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split(" "))
    tree[a - 1].children.append(b - 1)

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

# bfs
que = queue.Queue()
que.put(0)  # root is 0

while not que.empty():
    ind = que.get()
    ans[ind] = tree[ind].counter
    for child in tree[ind].children:
        tree[child].counter += tree[ind].counter
        que.put(child)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n , q = map(int,input().split())
point = [0] * n
edge = [[] for i in range(n)]

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

for _ in range(q):
    a , b = map(int,input().split())
    point[a-1] += b

def dfs(now, last=-1):
    for nxt in edge[now]:
        if nxt==last: continue
        point[nxt] += point[now]
        dfs(nxt, now)
dfs(0)
print(*point)

Submission status: Wrong Answer

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


def dfs(graph,start,point,mark_dict):
    global tree_point
    mark_dict[start] = True
    tree_point[start] += point
    for target in graph[start]:
        if target not in mark_dict:
            mark_dict[target] = True
            dfs(graph,target,tree_point[start],mark_dict)


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

tree = [[] for _ in range(n+1)]
tree_point = [0] * (n+1)

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

for _ in range(q):
    array = list(map(int, input().split()))
    tree_point[array[0]] += array[1]

dfs(tree,1,0,mark_dict={})

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

Submission status: Wrong Answer

Solution code:
from collections import deque


def read():
    N, Q = list(map(int, input().strip().split()))
    G = [i for i in range(N+1)]
    PX = list()
    G[1] = 0  # 終点
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[b] = a  # 逆辺を張る
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX


def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    V = [0 for i in range(N+1)]
    for p, x in PX:
        C[p] += x
    V[1] = C[1]
    for i in range(2, N+1):
        V[i] = V[G[i]] + C[i]
    return ' '.join(map(str, V[1:]))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Wrong Answer

Solution code:
from collections import deque


def read():
    N, Q = list(map(int, input().strip().split()))
    G = [i for i in range(N+1)]
    PX = list()
    G[1] = 0  # 終点
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[b] = a  # 逆辺を張る
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX


def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    V = [-1 for i in range(N+1)]
    for p, x in PX:
        C[p] += x
    V[1] = C[1]
    for i in range(2, N+1):
        V[i] = V[G[i]] + C[i]
    return ' '.join(map(str, V[1:]))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Wrong Answer

Solution code:
from collections import deque


def read():
    N, Q = list(map(int, input().strip().split()))
    G = [i for i in range(N+1)]
    PX = list()
    G[1] = 0  # 終点
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[b] = a  # 逆辺を張る
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX


def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    V = [-1 for i in range(N+1)]
    values = deque()
    for p, x in PX:
        C[p] += x
    for i in range(N, 0, -1):
        node = i
        v = 0
        while node > 0:
            if V[node] > 0:  # use cache
                v += V[node]
                break
            v += C[node]
            node = G[node]
        V[i] = v 
        values.append(v)
    return ' '.join(map(str, values))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

if __name__ == "__main__":
    N, Q = map(int, input().split())
    Parents = {}
    TT = {}

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

    checked = set()
    for i in range(1, N+1):
        if i in checked:
            continue
        TT[i] = set()
        bag = set()
        cur = i
        while True:
            bag.add(cur)
            TT[cur] = TT[cur] | bag
            checked.add(cur)
            if cur not in Parents:
                break
            cur = Parents[cur]

    result_map = {}
    for i in range(1, N+1):
        result_map[i] = 0

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

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

Submission status: Wrong Answer

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

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

ctr = [0] * (N + 1)
queue = [(1, cnt[1])]
while queue:
    u, x = queue.pop()
    ctr[u] += x
    for v in tree[u]:
        queue.append((v, x + cnt[v]))

print(*ctr[1:])

Submission status: Wrong Answer

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

tree = [[] for _ in range(N + 1)]
for a, b in X:
    tree[a].append(b)
    
cnt = [0] * (N + 1)
for p, x in P:
    cnt[p] += x

ctr = [0] * (N + 1)
queue = [(1, cnt[1])]
while queue:
    u, x = queue.pop()
    ctr[u] += x
    for v in tree[u]:
        queue.append((v, x + cnt[v]))

print(*ctr[1:])

Submission status: Wrong Answer

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

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

ctr = [0] * (N + 1)
for p, x in P:
    queue = [p]
    while queue:
        u = queue.pop()
        ctr[u] += x
        for v in tree[u]:
            queue.append(v)
    
print(*ctr[1:])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

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

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

def dfs(u, x):
    ctr[u] += x
    for v in tree[u]:
        dfs(v, x)

ctr = [0] * (N + 1)
for p, x in P:
    dfs(p, x)
    
print(*ctr[1:])

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    N, Q = input_nums()
    C = [0]*(N+1)
    ab = []
    for i in range(N-1):
        a, b = input_nums()
        ab.append((a, b))
    ab.sort(key=lambda x: x[0])
    for i in range(Q):
        p, x = input_nums()
        C[p] += x
    for a, b in ab:
        C[b] += C[a]
    ans = ' '.join(map(str, C[1:]))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
ab=[]
for _ in range(N-1):
    ab.append(tuple(map(int, input().split())))
px=[]
for _ in range(Q):
    px.append(tuple(map(int, input().split())))

#print(N,Q,ab,px)

counter=[0]*N
def func(start, plus, counter):
    counter[start-1]+=plus
    for val in ab:
        if start==val[0]:
            func(val[1], plus, counter)

for val in px:
    func(val[0], val[1], counter)

print(' '.join(list(map(str, counter))))

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
ab=[]
for _ in range(N-1):
    ab.append(tuple(map(int, input().split())))
px=[]
for _ in range(Q):
    px.append(tuple(map(int, input().split())))

print(N,Q,ab,px)

counter=[0]*N
def func(start, plus, counter):
    counter[start-1]+=plus
    for val in ab:
        if start==val[0]:
            func(val[1], plus, counter)

for val in px:
    func(val[0], val[1], counter)

print(' '.join(list(map(str, counter))))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    N, Q = Scanner.map_int()
    G = [-1 for _ in range(N)]
    for _ in range(N - 1):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        G[b] = a
    P = [0 for _ in range(N)]
    for _ in range(Q):
        p, x = Scanner.map_int()
        p -= 1
        P[p] += x
    ans = [0 for _ in range(N)]
    for i in range(N):
        if G[i] == -1:
            ans[i] = P[i]
            continue
        P[i] += P[G[i]]
        ans[i] = P[i]
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
E=[[] for _ in range(N)]
for i in range(N-1):
  x,y=map(int,input().split())
  x-=1
  y-=1
  E[x].append(y)
  E[y].append(x)
par=[-1]*N
par[0]=0
stack=[0]
while stack:
  u=stack.pop()
  for v in E[u]:
    if par[v]==-1:
      stack.append(v)
      par[v]=u
counter=[0]*N
for i in range(Q):
  u,x=map(int,input().split())
  u-=1
  counter[u]+=x
for i in range(N):
  if i==0:
    pass
  else:
    counter[i]+=int(counter[par[i]])
  counter[i]=str(counter[i])
print(' '.join(counter))