Problem:


Score : 400 points

Problem Statement

Given is a rooted tree with N vertices numbered 1 to N.
The root is Vertex 1, and the i-th edge (1 \leq i \leq N - 1) connects Vertex a_i and b_i.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0.

Now, the following Q operations will be performed:

Operation j (1 \leq j \leq Q): Increment by x_j the counter on every vertex contained in the subtree rooted at Vertex p_j.

Find the value of the counter on each vertex after all operations.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq Q \leq 2 \times 10^5

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

Sample Input 1

4 3
1 2
2 3
2 4
2 10
1 100
3 1

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:

Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.

Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.

Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Sample Input 2

6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10

Sample Output 2

20 20 20 20 20 20



Sample input:
4 3
1 2
2 3
2 4
2 10
1 100
3 1


Sample output:
100 110 111 110

Submission status: Wrong Answer

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

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

def bfs(parent,current):
    if not graph[parent]:
        return
    if not (parent == 0 and current == 0):
        cnt[current] += cnt[parent]

    for child in graph[current]:
        bfs(current,child)

bfs(0,0)
print(*cnt)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N

for i in range(N-1):
    a, b = map(int, input().split())
    neighbor[a-1].append(b-1)
    # neighbor[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x


def find(x, llist):
    while llist is not None:
        y, llist = llist
        if y == x:
            return True
    return False


stack = [(0, 0, None)]
while stack:
    (node, acc, ancestors) = stack.pop()
    counter[node] += acc
    acc = counter[node]
    ancestors = (node, ancestors)
    for c in neighbor[node]:
        # if not find(c, ancestors):
        stack.append((c, acc, ancestors))

print(*counter, sep=' ')

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)
N, Q = map(int, input().split())

child = defaultdict(list)
counter = [0] * N
pcounter = [0] * N

for i in range(N-1):
    a, b = map(int, input().split())
    child[a-1].append(b-1)
for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def propagate(node, acc):
    counter[node] += acc
    acc = counter[node]
    for c in child[node]:
        propagate(c, acc)

propagate(0, 0)
print(*counter, sep=' ')

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int, input().split())

child = defaultdict(list)
counter = [0] * N
pcounter = [0] * N

for i in range(N-1):
    a, b = map(int, input().split())
    child[a-1].append(b-1)
for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def propagate(node, acc):
    counter[node] += acc
    acc = counter[node]
    for c in child[node]:
        propagate(c, acc)

propagate(0, 0)
print(*counter, sep=' ')

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
bars = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    bars[a - 1].append(b - 1)
processes = [list(map(int, input().split())) for _ in range(Q)]
# print(bars)
counters = [0 for _ in range(N)]
for tree_index, point in processes:
    queue = deque([tree_index - 1])
    seen_point = [False for _ in range(N)]
    while queue:
        now_index = queue.pop()
        seen_point[now_index] = True
        # print(now_index)
        counters[now_index] += point
        for next_index in bars[now_index]:
            if not seen_point[next_index]:
                queue.append(next_index)
    # print(counters)
print(*counters)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
bars = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    bars[a - 1].append(b - 1)
processes = [list(map(int, input().split())) for _ in range(Q)]
# print(bars)
counters = [0 for _ in range(N)]

for tree_index, point in processes:
    queue = deque([tree_index - 1])
    while queue:
        now_index = queue.pop()
        # print(now_index)
        counters[now_index] += point
        for next_index in bars[now_index]:
            queue.append(next_index)
    # print(counters)
print(*counters)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, Q = map(int, input().split())
bars = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    bars[a - 1].append(b - 1)
processes = [list(map(int, input().split())) for _ in range(Q)]
# print(bars)
counters = [0 for _ in range(N)]

for tree_index, point in processes:
    queue = deque([tree_index - 1])
    while queue:
        now_index = queue.pop()
        # print(now_index)
        counters[now_index] += point
        for next_index in bars[now_index]:
            queue.append(next_index)
    # print(counters)
print(*counters)

Submission status: Wrong Answer

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

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

class Node(object):
	def __init__(self, num):
		self.num = num #各ノードの数字0〜9
		self.children = []
		self.c = 0
	#heapq.heapify()する際に必要となる比較関数
	def __lt__(self, x):
		return self.value < x.value
	#子どもをセットする
	def setChildren(self, x):
		self.children.append(x)
	def solve(self,x):
		self.c += x
		for child in self.children:
			table[child].solve(x)


table = [Node(i+1) for i in range(n)]
counter = [0 for _ in range(n)]

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

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

for i in range(n):
	if counter[i] != 0:
		table[i].solve(counter[i])

ans = [str(table[i].c) for i in range(n)]
print(" ".join(ans))

Submission status: Wrong Answer

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

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

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

ans = [None] + [0]*N

check = set()
def dfs(root, x):
    global ans, check
    for i in range(N-1):
        if ab[i][0] == root:
            if root not in check:
                ans[root] += x
                check.add(root)
            ans[ab[i][1]] += x
            check.add(ab[i][1])
            dfs(ab[i][1], x)
        if ab[i][1] == root:
            if root not in check:
                ans[root] += x
                check.add(root)


for _ in range(Q):
    p, x = MAP()
    dfs(p, x)
    check = set()

print(" ".join([str(i) for i in ans[1:]]))

Submission status: Wrong Answer

Solution code:
import queue

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

q = queue.Queue()
q.put(0)

while not q.empty():
  index = q.get()
  for i in tree[index]:
    counter[i] += counter[index]
    q.put(i)
    
print(*counter)

Submission status: Wrong Answer

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

def ta(v):
    for j in range(q):
        count = 0
        if (y[j]!=[]):
            if (y[j][0]==v):
                count += y[j][1]
    return count

ans = [0]*(n+1)
stack = [(1,-1)]
while stack:
    v,par = stack.pop()
    if (way[v]!=[]):
        for i in range(len(way[v])):
            stack.append((way[v][i],v))
    if v==1:
        ans[v] = ta(v)
    else:
        ans[v] += (ta(v) + ans[par])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N - 1)]
ops = [list(map(int, input().split())) for _ in range(Q)]
edges = np.array(edges) - 1

childs = [[] for i in range(N)]
counter = np.zeros(N, dtype=int)

for a, b in edges:
    childs[a] += [b]

for v, c in ops:
    counter[v - 1] += c

def propagate(vtx):
    count = counter[vtx]
    for child in childs[vtx]:
        counter[child] += count
        propagate(child)

propagate(0)
print(str(counter)[1:-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def main():
    _map = map
    _int = int
    _input = input
    n, q = _map(_int, _input().split())
    work = [[] for i in range(n+1)]
    counter = [0]*(n+1)
    result = [0]*(n+1)
    for i in range(n-1):
        a, b = _map(_int, _input().split())
        work[a].append(b)
    for i in range(q):
        p, x = _map(_int, _input().split())
        counter[p] += x
    def calc(r, v, i):
        r[i] = v + counter[i]
        for j in work[i]:
            calc(r, r[i], j)
    calc(result, 0, 1)
    print(" ".join(_map(str, result[1:])))
main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def main():
    n, q = map(int, input().split())
    work = [[] for i in range(n+1)]
    counter = [0 for i in range(n+1)]
    result = [0 for i in range(n+1)]
    for i in range(n-1):
        a, b = map(int, input().split())
        work[a].append(b)
    for i in range(q):
        p, x = map(int, input().split())
        counter[p] += x
    def calc(r, v, i):
        r[i] = v + counter[i]
        for j in work[i]:
            calc(r, r[i], j)
    calc(result, 0, 1)
    print(" ".join(map(str, result[1:])))
main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def main():
    n, q = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n-1)]
    px = [list(map(int, input().split())) for i in range(q)]
    work = [[] for i in range(n+1)]
    counter = [0 for i in range(n+1)]
    result = [0 for i in range(n+1)]
    for a, b in ab:
        work[a].append(b)
    for p, x in px:
        counter[p] += x
    def calc(v, i):
        result[i] = v + counter[i]
        for j in work[i]:
            calc(result[i], j)
    calc(0, 1)
    print(" ".join(map(str, result[1:])))
main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n-1)]
px = [list(map(int, input().split())) for i in range(q)]
work = [[] for i in range(n)]
counter = [0 for i in range(n)]
result = [0 for i in range(n)]
for a, b in ab:
    work[a-1].append(b)
for p, x in px:
    counter[p-1] += x
def calc(v, i):
    result[i-1] = v + counter[i-1]
    for j in work[i-1]:
        calc(result[i-1], j)
calc(0, 1)
print(" ".join(map(str, result)))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import sys
sys.setrecursionlimit(200000)

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

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
      
par = [-1]*n
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    unite(u,v)

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

def dfs(now, prev):
    # リストはglobal宣言の必要がない？
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            chk[next] += chk[now]
            dfs(next, now)

par = tuple(par)            
for i in range(n):
  if par[i] < 0:
    dfs(i,-1)

chk = list(map(str,chk))
print(' '.join(chk))

Submission status: Wrong Answer

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(que!=deque()):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            que.append(e)


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

from collections import deque
sys.setrecursionlimit(10**9)

#入力受け取り
N, Q = mi()
x = li2(N-1)
#p = li2(Q)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])


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

#for a in range(N):
que.append((0, 0))
num = 0
while que!=deque():
    v = que.popleft()
    ans[v[1]] = ans[v[0]] + cnt[v[1]]
    for next in adj[v[1]]:
        que.append((v[1], next))

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

Submission status: Wrong Answer

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(que!=deque()):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            que.append(e)


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

from collections import deque
sys.setrecursionlimit(10**9)

#入力受け取り
N, Q = mi()
x = li2(N-1)
#p = li2(Q)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

#print(adj)
#print(cnt)
que = deque()
kotae = [0]*N

for a in range(N):
    que.append(a)
    kotae[a] += cnt[a]
    while que!=deque():
        v = que.popleft()
        for next in adj[v]:
            que.append(next)
            kotae[next] += cnt[a]

for k in kotae:
    print(k, '', end='')

Submission status: Wrong Answer

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(que!=deque()):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            que.append(e)


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

from collections import deque
sys.setrecursionlimit(10**9)

#DFS
def dfs(x):
    if flag[x]:
        return
    else:
        flag[x] = 1
        for a in adj[x]:
            dfs(a)
        global ans
        ans.appendleft(x)

#入力受け取り
N, Q = mi()
x = li2(N-1)
p = li2(Q)

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])
'''
#DFSを利用したトポロジカルソート
flag = [0]*N
ans = deque([])
for i in range(N):
    dfs(i)
#print(ans)
'''
cnt = [0]*N
for i in range(Q):
    #ind = bisect.bisect_left(ans, p[i][0]-1)
    cnt[p[i][0]-1] += p[i][1]

#print(adj)
#print(cnt)
que = deque()
kotae = [0]*N

for a in range(N):
    que.append(a)
    kotae[a] += cnt[a]
    while que!=deque():
        v = que.popleft()
        for next in adj[v]:
            que.append(next)
            kotae[next] += cnt[a]

for k in kotae:
    print(k, '', end='')

Submission status: Wrong Answer

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(que!=deque()):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            que.append(e)


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

from collections import deque
sys.setrecursionlimit(10**9)

#DFS
def dfs(x):
    if flag[x]:
        return
    else:
        flag[x] = 1
        for a in adj[x]:
            dfs(a)
        global ans
        ans.appendleft(x)

#入力受け取り
N, Q = mi()
x = li2(N-1)
p = li2(Q)

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

#DFSを利用したトポロジカルソート
flag = [0]*N
ans = deque([])
for i in range(N):
    dfs(i)
#print(ans)

cnt = [0]*N
for i in range(Q):
    #ind = bisect.bisect_left(ans, p[i][0]-1)
    cnt[p[i][0]-1] += p[i][1]

#print(adj)
#print(cnt)
que = deque()
kotae = [0]*N

for a in ans:
    que.append(a)
    kotae[a] += cnt[a]
    while que!=deque():
        v = que.popleft()
        for next in adj[v]:
            que.append(next)
            kotae[next] += cnt[a]

for k in kotae:
    print(k, '', end='')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(que!=deque()):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            que.append(e)


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(len(que)!=0):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            #ans[e] += a
            que.append(e)


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(len(que)!=0):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            #ans[e] += a
            que.append(e)
        print(ans)


for i in range(1, N+1):
    print(ans[i])

Submission status: Wrong Answer

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

N,Q = [int(i) for i in input().split()] #N個の頂点、Q回の操作
aaabbb = [[int(i) for i in input().split()] for j in range(N-1)] #木の辺
pppxxx = [[int(i) for i in input().split()] for j in range(Q)] #操作

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

for a,b in aaabbb: #aがbの親とは限らないのでこの表記はまずい
    tree[a].append(b)

#print(tree)

counter = [0 for i in range(N+1)]

for p,x in pppxxx:
    counter[p] += x

#print(counter)

def dfs(pos):
    for next_pos in tree[pos]:
        counter[next_pos] += counter[pos]
        dfs(next_pos)

dfs(1)

#print(counter)

print(" ".join([str(i) for i in counter[1:]]))

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q = (int(x) for x in input().split())
par = [0] * N
par[0] = 500000
for _ in range(N-1):
    a,b = (int(x) for x in input().split())
    if par[a-1] == 0:
        par[a-1] = b
    else:
        par[b-1] = a
counter = [0] * N
for _ in range(Q):
    p,x = (int(y) for y in input().split())
    counter[p-1] += x
ans = [0] * N
def count(vert):
    if vert == 1:
        ans[vert-1] = counter[0]
    else:
        ans[vert-1] = ans[par[vert-1]-1] + counter[vert-1]
q = deque([1])
searched = [0] * N
while q:
    temp = q.popleft()
    if temp is not None:
        if searched[temp-1] == 0:
            count(temp)
            searched[temp-1] = 1
            children = [x for x, y in enumerate(par) if y == temp]
            for child in children:
                q.append(child+1)
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q = (int(x) for x in input().split())
par = [0] * N
par[0] = 500000
for _ in range(N-1):
    a,b = (int(x) for x in input().split())
    if par[a-1] == 0:
        par[a-1] = b
    else:
        par[b-1] = a
counter = [0] * N
for _ in range(Q):
    p,x = (int(y) for y in input().split())
    counter[p-1] += x
ans = [0] * N
def count(vert):
    if vert == 1:
        ans[vert-1] = counter[0]
    else:
        ans[vert-1] = ans[par[vert-1]-1] + counter[vert-1]
q = deque([1])
while q:
    temp = q.popleft()
    if temp is not None:
        count(temp)
        children = [x for x, y in enumerate(par) if y == temp]
        for child in children:
            q.append(child+1)
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q = (int(x) for x in input().split())
par = [0] * N
par[0] = 500000
for _ in range(N-1):
    a,b = (int(x) for x in input().split())
    if par[a-1] == 0:
        par[a-1] = b
    else:
        par[b-1] = a
counter = [0] * N
for _ in range(Q):
    p,x = (int(y) for y in input().split())
    counter[p-1] += x
ans = [0] * N
def count(vert):
    if vert == 1:
        ans[vert-1] = counter[0]
    else:
        ans[vert-1] = ans[par[vert-1]-1] + counter[vert-1]
q = deque([1])
while len(q) > 0:
    temp = q.popleft()
    if temp is not None:
        count(temp)
        children = [x for x, y in enumerate(par) if y == temp]
        children.sort()
        for child in children:
            q.append(child+1)
print(*ans)

Submission status: Wrong Answer

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


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

ans=[0]*N
def dfs(start, pre, preval):
  addval=preval+add[start]
  ans[start]+=addval
  for next_node in tree[start]:
    dfs(next_node, start,addval)
dfs(0,-1,0)  
for a in ans:
  print(a, end=" ")

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q = (int(x) for x in input().split())
par = [0] * N
par[0] = 500000
for _ in range(N-1):
    a,b = (int(y) for y in input().split())
    if par[a-1] == 0:
        par[a-1] = b
    else:
        par[b-1] = a
counter = [0] * N
for _ in range(Q):
    p,x = (int(y) for y in input().split())
    counter[p-1] += x
ans = [0] * N
def count(vert):
    if vert == 1:
        ans[vert-1] = counter[0]
    else:
        prev = ans[par[vert-1]-1]
        ans[vert-1] = prev + counter[vert-1]
q = deque([1])
while len(q) > 0:
    temp = q.popleft()
    if temp is not None:
        count(temp)
        children = [x for x, y in enumerate(par) if y == temp]
        for child in children:
            q.append(child+1)
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q = (int(x) for x in input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
counter = [0] * N
for _ in range(Q):
    p,x = (int(y) for y in input().split())
    counter[p-1] += x
par = [0] * N
ans = [0] * N
par[0] = 500000
for i in ab:
    for j in range(2):
        if par[i[j]-1] == 0:
            par[i[j]-1] = i[1-j]
def count(vert):
    if vert == 1:
        ans[vert-1] = counter[0]
    else:
        prev = ans[par[vert-1]-1]
        ans[vert-1] = prev + counter[vert-1]
q = deque([1])
while len(q) > 0:
    temp = q.popleft()
    if temp is not None:
        count(temp)
        children = [x for x, y in enumerate(par) if y == temp]
        for child in children:
            q.append(child+1)
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q = (int(x) for x in input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]
par = [0] * N
ans = [0] * N
par[0] = 500000
for i in ab:
    for j in range(2):
        if par[i[j]-1] == 0:
            par[i[j]-1] = i[1-j]
def count(vert):
    if vert == 1:
        ans[vert-1] = sum([px[i][1] for i in range(Q) if px[i][0] == vert])
    else:
        prev = ans[par[vert-1]-1]
        ans[vert-1] = prev + sum([px[i][1] for i in range(Q) if px[i][0] == vert])
q = deque([1])
while len(q) > 0:
    temp = q.popleft()
    if temp is not None:
        count(temp)
        children = [x for x, y in enumerate(par) if y == temp]
        for child in children:
            q.append(child+1)
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q = (int(x) for x in input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]
par = [0] * N
ans = [0] * N
par[0] = 500000
for i in ab:
    for j in range(2):
        if par[i[j]-1] == 0:
            par[i[j]-1] = i[1-j]
def count(vert):
    if vert == 1:
        prev = 0
    else:
        prev = ans[par[vert-1]-1]
    ans[vert-1] = prev + sum([px[i][1] for i in range(Q) if px[i][0] == vert])
q = deque([1])
while len(q) > 0:
    temp = q.popleft()
    if temp is not None:
        count(temp)
        children = [x for x, y in enumerate(par) if y == temp]
        for child in children:
            q.append(child+1)
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    edge = [[] for _ in range(N)]
    for i in ab:
        edge[i[0]-1].append(i[1]-1)
        edge[i[1]-1].append(i[0]-1)
    cnt = [0]*N
    for i in px:
        cnt[i[0]-1] += i[1]

    stk = []
    visited = set()
    stk.append(0)
    while len(stk):
        v = stk.pop()
        if not v in visited:
            visited.add(v)
        if v>0:
            cnt[v] += cnt[par]
        for i in edge[v]:
            if not i in visited:
                stk.append(i)
        par = v

    print(*cnt)

if __name__ == '__main__':
    resolve()