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
input = sys.stdin.readline
from collections import deque

icase=2
if icase==0:
    n,q=map(int,input().split())
    g = [set() for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
    xx=[0]*n
    for i in range(q):
        xx[p[i]]=xx[p[i]]+x[i]
#ans:100 110 111 110
elif icase==3:
    n,q=6,2
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1,2])
    g[1]=deque([0,3,4])
    g[2]=deque([0,5])
    g[3]=deque([1])
    g[4]=deque([1])
    g[5]=deque([2])
    p=[0]*q
    x=[0]*q
    p[0]=0
    x[0]=10    
    p[1]=0
    x[1]=10    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
        
#q = deque([0])
stack=[0]
parent=[-1]*n
while stack:
#    print(q)
    state = stack.pop()
#    print("------------- stack:",stack,"state:",state,"g:",g[state])
    for v in g[state]:
#        print("state:",state,"v:",v,"q:",q)
        if parent[state] == v:
            continue
        else:
            parent[v]=state
            stack.append(v)
            xx[v]+=xx[state]
#            print("parent:",parent,"xx:",xx,"stack",stack)

print(" ".join(map(str,xx[0: ])))

Submission status: Wrong Answer

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

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

# 木構造をリストで表現する
G = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    G[a].append(b)

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p = p - 1
    P[p] += x

# 各頂点のカウンター
Count = [0] * N


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとし、
    new_point = point + P[v]
    Count[v] = new_point

    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, new_point)


dfs(0, 0, 0)

res = " ".join(map(str, Count))

print(res)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n, q = map(int, input().split())
parent = [-1] * n
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    if a != 0 and parent[b] != -1:
        parent[a] = b
    else:
        parent[b] = a
add = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    add[p-1] += x

from_root = sorted(list(zip(range(n), parent, add)), key=itemgetter(1))
ans = [0] * n
for i, p, a in from_root:
    ans[i] = ans[p] + a

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

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
parent = [-1] * n
order = [0]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    if a != 0 and parent[b] != -1:
        parent[a] = b
        order.append(a)
    else:
        parent[b] = a
        order.append(b)
add = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    add[p-1] += x

ans = [0] * n
for i in order:
    ans[i] = ans[parent[i]] + add[i]
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
parent = [0] * n
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    parent[b] = a
add = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    add[p-1] += x

ans = [0] * n
for i in range(n):
    ans[i] = ans[parent[i]] + add[i]

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

Submission status: Wrong Answer

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

parents = set([link[0] for link in links])

counter = [0] * N

def dfs(cur, point):
  cur = cur
  if cur not in parents:
    counter[cur - 1] += point
    return
  else:
    counter[cur - 1] += point
    for link in links:
      if link[0] == cur:
        next_pos = link[1]
        dfs(next_pos, point)

for p_item in P:
  cur = p_item[0]
  point = p_item[1]
  dfs(cur, point)

counter = [str(s) for s in counter]
print(" ".join(counter))

Submission status: Wrong Answer

Solution code:
from collections import (
    deque,
    defaultdict,
    Counter,
)

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

tree = defaultdict(set)
for _ in range(1, N):
    a, b = map(int, input().split(' '))
    tree[a].add(b)

counter = Counter()

for _ in range(Q):
    p, x = map(int, input().split(' '))
    stack = deque()
    stack.appendleft(p)
    while len(stack) > 0:
        node = stack.popleft()
        for child in tree[node]:
            stack.append(child)
        counter[node] += x

print(' '.join([str(counter[node]) for node in range(1, N + 1)]))

Submission status: Wrong Answer

Solution code:
from collections import (
    deque,
    defaultdict,
    Counter,
)

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

tree = defaultdict(set)
for _ in range(1, N):
    a, b = map(int, input().split(' '))
    tree[min(a, b)].add(max(a, b))

counter = Counter()

for _ in range(Q):
    p, x = map(int, input().split(' '))
    stack = deque()
    stack.appendleft(p)
    while len(stack) > 0:
        node = stack.popleft()
        for child in tree[node]:
            stack.append(child)
        counter[node] += x

print(' '.join([str(counter[node]) for node in range(1, N + 1)]))

Submission status: Wrong Answer

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    n, q = map(int, input().split())
    childs = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        childs[a - 1].append(b - 1)
    counter = [0] * n
    for _ in range(q):
        p, x = list(map(int, input().split()))
        counter[p - 1] += x
    ans = [0] * n
    ans[0] = counter[0]
    q = [(0, x) for x in childs[0]]
    while q:
        p, i = q.pop()
        ans[i] = ans[p] + counter[i]
        for j in childs[i]:
            q.append((i, j))
    print(*ans)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)    
from collections import deque

seen=[]
first_order =[]
last_order = []
path=[]

def dfs(g, v, first_ptr, last_ptr,xi):
    first_ptr=first_ptr+1
    last_ptr=first_ptr
    first_order[v] = first_ptr
    path.append(v)
    seen[v]=True
#    c[v]+=xi
#    print(v,c,g[v])          
    for next_v in g[v]:
        if seen[next_v]:
            continue
        first_ptr, last_ptr=dfs(g, next_v, first_ptr, last_ptr,xi)
    last_ptr=last_ptr+1
    first_ptr=last_ptr
    last_order[v] = last_ptr
    path.append(v)

    return first_ptr, last_ptr

icase=3
if icase==0:
    n,q=map(int,input().split())
    g = [deque([]) for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
    p=[0]*q
    x=[0]*q
    for i in range(q):
        pi,xi=map(int,input().split())
        p[i]=pi-1
        x[i]=xi
elif icase==1:
    n,q=3,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([2])
    g[1]=deque([2])
    g[2]=deque([0,1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=2
    x[1]=100
    p[2]=0
    x[2]=1    
#ans:1 111 101
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
#ans:100 110 111 110
elif icase==3:
    n,q=6,2
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1,2])
    g[1]=deque([0,3,4])
    g[2]=deque([0,5])
    g[3]=deque([1])
    g[4]=deque([1])
    g[5]=deque([2])
    p=[0]*q
    x=[0]*q
    p[0]=0
    x[0]=10    
    p[1]=0
    x[1]=10
#ans:100 110 111 110

xx=[0]*n
for i in range(q):
    xx[p[i]]=xx[p[i]]+x[i]
    
c=[0]*n

#for i in range(q):
#    seen=[False]*n
#    first_ptr=0
#    last_ptr=0
#    first_order =[-1]*n
#    last_order = [-1]*n
#    first_ptr, last_ptr=dfs(g,p[i],first_ptr, last_ptr,x[i])

seen=[False]*n
first_ptr=0
last_ptr=0
first_order =[-1]*n
last_order = [-1]*n
first_ptr, last_ptr=dfs(g,0,first_ptr, last_ptr,x[0])

#print(path)

seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)    
from collections import deque

seen=[]
first_order =[]
last_order = []
path=[]

def dfs(g, v, first_ptr, last_ptr,xi):
    first_ptr=first_ptr+1
    last_ptr=first_ptr
    first_order[v] = first_ptr
    path.append(v)
    seen[v]=True
#    c[v]+=xi
#    print(v,c,g[v])          
    for next_v in g[v]:
        if seen[next_v]:
            continue
        first_ptr, last_ptr=dfs(g, next_v, first_ptr, last_ptr,xi)
    last_ptr=last_ptr+1
    first_ptr=last_ptr
    last_order[v] = last_ptr
    path.append(v)

    return first_ptr, last_ptr

icase=0
if icase==0:
    n,q=map(int,input().split())
    g = [deque([]) for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
    p=[0]*q
    x=[0]*q
    for i in range(q):
        pi,xi=map(int,input().split())
        p[i]=pi-1
        x[i]=xi
elif icase==1:
    n,q=3,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([2])
    g[1]=deque([2])
    g[2]=deque([0,1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=2
    x[1]=100
    p[2]=0
    x[2]=1    
#ans:1 111 101
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
#ans:100 110 111 110

xx=[0]*n
for i in range(q):
    xx[p[i]]=x[i]
    
c=[0]*n

#for i in range(q):
#    seen=[False]*n
#    first_ptr=0
#    last_ptr=0
#    first_order =[-1]*n
#    last_order = [-1]*n
#    first_ptr, last_ptr=dfs(g,p[i],first_ptr, last_ptr,x[i])

seen=[False]*n
first_ptr=0
last_ptr=0
first_order =[-1]*n
last_order = [-1]*n
first_ptr, last_ptr=dfs(g,0,first_ptr, last_ptr,x[0])

#print(path)

seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10000)    
from collections import deque

seen=[]
first_order =[]
last_order = []
path=[]

def dfs(g, v, first_ptr, last_ptr,xi):
    first_ptr=first_ptr+1
    last_ptr=first_ptr
    first_order[v] = first_ptr
    path.append(v)
    seen[v]=True
#    c[v]+=xi
#    print(v,c,g[v])          
    for next_v in g[v]:
        if seen[next_v]:
            continue
        first_ptr, last_ptr=dfs(g, next_v, first_ptr, last_ptr,xi)
    last_ptr=last_ptr+1
    first_ptr=last_ptr
    last_order[v] = last_ptr
    path.append(v)

    return first_ptr, last_ptr

icase=1
if icase==0:
    n,q=map(int,input().split())
    g = [deque([]) for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
    p=[0]*q
    x=[0]*q
    for i in range(q):
        pi,xi=map(int,input().split())
        p[i]=pi-1
        x[i]=xi
elif icase==1:
    n,q=3,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([2])
    g[1]=deque([2])
    g[2]=deque([0,1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=2
    x[1]=100
    p[2]=0
    x[2]=1    
#ans:1 111 101
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
#ans:100 110 111 110

xx=[0]*n
for i in range(q):
    xx[p[i]]=x[i]
    
c=[0]*n

#for i in range(q):
#    seen=[False]*n
#    first_ptr=0
#    last_ptr=0
#    first_order =[-1]*n
#    last_order = [-1]*n
#    first_ptr, last_ptr=dfs(g,p[i],first_ptr, last_ptr,x[i])

seen=[False]*n
first_ptr=0
last_ptr=0
first_order =[-1]*n
last_order = [-1]*n
first_ptr, last_ptr=dfs(g,0,first_ptr, last_ptr,x[0])

#print(path)

seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)    
from collections import deque

seen=[]
first_order =[]
last_order = []
path=[]

def dfs(g, v, first_ptr, last_ptr,xi):
    first_ptr=first_ptr+1
    last_ptr=first_ptr
    first_order[v] = first_ptr
    path.append(v)
    seen[v]=True
#    c[v]+=xi
#    print(v,c,g[v])          
    for next_v in g[v]:
        if seen[next_v]:
            continue
        first_ptr, last_ptr=dfs(g, next_v, first_ptr, last_ptr,xi)
    last_ptr=last_ptr+1
    first_ptr=last_ptr
    last_order[v] = last_ptr
    path.append(v)

    return first_ptr, last_ptr

icase=0
if icase==0:
    n,q=map(int,input().split())
    g = [deque([]) for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
    p=[0]*q
    x=[0]*q
    for i in range(q):
        pi,xi=map(int,input().split())
        p[i]=pi-1
        x[i]=xi
elif icase==1:
    n,q=3,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([2])
    g[1]=deque([2])
    g[2]=deque([0,1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=2
    x[1]=100
    p[2]=0
    x[2]=1    
#ans:1 111 101
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
#ans:100 110 111 110

xx=[0]*n
for i in range(q):
    xx[p[i]]=x[i]
    
c=[0]*n

#for i in range(q):
#    seen=[False]*n
#    first_ptr=0
#    last_ptr=0
#    first_order =[-1]*n
#    last_order = [-1]*n
#    first_ptr, last_ptr=dfs(g,p[i],first_ptr, last_ptr,x[i])

seen=[False]*n
first_ptr=0
last_ptr=0
first_order =[-1]*n
last_order = [-1]*n
first_ptr, last_ptr=dfs(g,0,first_ptr, last_ptr,x[0])

print(path)

seen=[False]*n

c=[0]*n
cpt=0
for pt in path:
    if seen[pt]==False:
        seen[pt]=True
#        print("pt:",pt,"cpt:",cpt,"xx[pt]:",xx[pt],"c[pt]:",c[pt]+cpt+xx[pt])
        cpt=cpt+xx[pt]
        c[pt]=c[pt]+cpt
    else:
        seen[pt]=False
        cpt=cpt-xx[pt]
           
for i in range(n):
    print(c[i],end=" ")
print()

Submission status: Wrong Answer

Solution code:
import queue
n,q = map(int,input().split())
graph = [[] for _ in range(n)]

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

v = [0 for _ in range(n)]
qs = queue.Queue()
for i in range(q):
    p,x = map(int,input().split())
    qs.put(p-1)
    while not qs.empty():
        now = qs.get()
        v[now] += x
        for y in graph[now]:
            qs.put(y)
            #v[y] += x
for i in v:
    print(i,end=' ')

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys


def my_input():
    return sys.stdin.readline()[:-1]


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

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

que = deque()
que.append(0)
kaisos = [None for _ in range(N)]
kaisos[0] = 0
kaiso_depth = 1
while len(que) > 0:
    node_i = que.popleft()
    neighbors = Nodes[node_i]
    v = kaisos[node_i]
    for neighbor in neighbors:
        if kaisos[neighbor] is None:
            kaisos[neighbor] = v + 1
            kaiso_depth = v + 2
            que.append(neighbor)

# print("")
# print("kaiso:", kaisos)
# print("depth:", kaiso_depth)


ans = [0 for _ in range(N)]
imosu = [0 for _ in range(kaiso_depth)]
for _ in range(Q):
    p, x = map(int, my_input().split())
    p -= 1
    ans[p] += x
    kaiso = kaisos[p]
    if kaiso < kaiso_depth - 1:
        imosu[kaiso + 1] += x

# print("imosu:", imosu)

kaiso_values = [0 for _ in range(kaiso_depth)]
for i in range(1, kaiso_depth):
    kaiso_values[i] = kaiso_values[i - 1] + imosu[i]

# print(kaiso_values)

# 解答
for i in range(N):
    kaiso = kaisos[i]
    ans[i] += kaiso_values[kaiso]
    print(ans[i], end=' ')

Submission status: Wrong Answer

Solution code:
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 _ in range(q):
    a,b = map(int,input().split())
    a = a -1
    point[a]+=b
stack = [];
stack.append(0)
visited = [False]*n
while stack:
    x = stack.pop()
    visited[x] = True
    for y in graph[x]:
        if visited[y] == False:
            point[y] += point[x]
            stack.append(y)
print(*point)

Submission status: Wrong Answer

Solution code:
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 _ in range(q):
    a,b = map(int,input().split())
    a = a -1
    point[a]+=b
stack = [];
stack.append(0)
now = -1
while stack:
    x = stack.pop()
    point[x] += point[now]
    now = x
    for y in graph[x]:
        stack.append(y)
print(*point)

Submission status: Wrong Answer

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

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

que = [0]
kaisos = [None for _ in range(N)]
kaisos[0] = 0
kaiso_depth = 1
while len(que) > 0:
    node_i = que.pop(0)
    neighbors = Nodes[node_i]
    v = kaisos[node_i]
    for neighbor in neighbors:
        if kaisos[neighbor] is None:
            kaisos[neighbor] = v + 1
            kaiso_depth = v + 2
            que.append(neighbor)

# print("")
# print("kaiso:", kaisos)
# print("depth:", kaiso_depth)


ans = [0 for _ in range(N)]
imosu = [0 for _ in range(kaiso_depth)]
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
    kaiso = kaisos[p]
    if kaiso < kaiso_depth-1:
        imosu[kaiso+1] += x

#print("imosu:", imosu)

kaiso_values = [0 for _ in range(kaiso_depth)]
for i in range(1, kaiso_depth):
    kaiso_values[i] = kaiso_values[i-1] + imosu[i]

#print(kaiso_values)

# 解答
for i in range(N):
    kaiso = kaisos[i]
    ans[i] += kaiso_values[kaiso]
    print(ans[i], end=' ')

Submission status: Wrong Answer

Solution code:
from collections import deque
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)
    tree[b - 1].append(a - 1)

X = [0] * N

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

d = deque([0])
ans = X
visited = [False] * N 

while d:
    q = d.pop()
        
    for t in tree[q]:
        if t > q:
            ans[t] += X[q]
        if not visited[t]:
            d.append(t)
    
    visited[q] = True

print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
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)
    tree[b - 1].append(a - 1)

X = [0] * N

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

d = deque([0])
ans = X
visited = [False] * N 

while d:
    q = d.popleft()
        
    for t in tree[q]:
        if t > q:
            ans[t] += X[q]
        if not visited[t]:
            d.append(t)
    
    visited[q] = True

print(*ans)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    n, q = map(int, input().split())
    tree = [[] for i in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree[a].append(b)
    
    node = [0] * n
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        node[p] += x
    
    ans = [0] * n

    st = [[0, 0]]
    
    while st:
        now_node, now_score = st.pop()

        now_score += node[now_node]

        ans[now_node] = now_score

        for nex in tree[now_node]:
            st.append([nex, now_score])
    
    for i in range(n):
        ans[i] = str(ans[i])
    print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)    
from collections import deque

seen=[]
first_order =[]
last_order = []

def dfs(g, v, first_ptr, last_ptr,xi):
    first_ptr=first_ptr+1
    last_ptr=first_ptr
    
    first_order[v] = first_ptr
    seen[v]=True
    c[v]+=xi
#    print(v,c,g[v])          
    for next_v in g[v]:
        if seen[next_v]:
            continue
        first_ptr, last_ptr=dfs(g, next_v, first_ptr, last_ptr,xi)
    last_ptr=last_ptr+1
    first_ptr=last_ptr

    last_order[v] = last_ptr
    return first_ptr, last_ptr


icase=0
if icase==0:
    n,q=map(int,input().split())
    g = [deque([]) for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
    p=[0]*q
    x=[0]*q
    for i in range(q):
        pi,xi=map(int,input().split())
        p[i]=pi-1
        x[i]=xi

c=[0]*n

for i in range(q):
    seen=[False]*n
    first_ptr=0
    last_ptr=0
    first_order =[-1]*n
    last_order = [-1]*n
    first_ptr, last_ptr=dfs(g,p[i],first_ptr, last_ptr,x[i])

for i in range(n):
    print(c[i],end=" ")
print()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
ki = [0]*n
cnt = [0]*n
for i in range(n-1):
    a,b = map(int,input().split())
    ki[b-1]=a
for i in range(q):
    p,x = map(int,input().split())
    cnt[p-1]+=x
for i in range(1,n):
    cnt[i]+=cnt[ki[i]-1]
[print(x,end=' ') for x in cnt]

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
ki = [[] for _ in range(n)]
cnt = [0]*n
for i in range(n-1):
    a,b = map(int,input().split())
    ki[a-1].append(b)
for i in range(q):
    p,x = map(int,input().split())
    cnt[p-1]+=x
    if ki[p-1]:
        for j in range(ki[p-1][0],n+1):
            cnt[j-1]+=x
[print(x,end=' ') for x in cnt]

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, Q = map(int, input().split())

tree = {}
tree[1] = []
counter = Counter()

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

    a_in_tree = a in tree
    b_in_tree = b in tree


    if a_in_tree == True:
        tmp = tree.pop(a)
        tmp.append(b)
        tree[a] = tmp
        tree[b] = []
    elif b_in_tree == True:
        tmp = tree.pop(b)
        tmp.append(a)
        tree[b] = tmp
        tree[a] = []


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

lst = ["0" for i in range(N)]

def calc(node, num):
    cnt = num + counter[node]
    
    lst[node-1] = str(cnt)

    if node in tree:
        for t in tree[node]:
            calc(t, cnt)
        
calc(1, 0)
print(" ".join(lst))

Submission status: Wrong Answer

Solution code:
import queue

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

node = [0] * (N+1)
nxt = [[] for _ in range(N+1)]

#for ab in AB:
    #a, b = ab[0], ab[1]
for _ in range(N-1):
    a,b = map(int, input().split())
    nxt[a].append(b)
    nxt[b].append(a)

#for px in PX:
    #p,x = px[0], px[1]
for _ in range(Q):
    p,x = map(int, input().split())
    node[p] += x

visited = [False] * (N+1)
q = queue.Queue()
q.put(1)
cnt = 1
while not q.empty():
    cnt += 1
    v = q.get()
    visited[v] = True
    for nv in nxt[v]:
        node[nv] += node[v]
        if not visited[nv]:
            q.put(nv)

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

Submission status: Wrong Answer

Solution code:
import queue

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

node = [0] * (N+1)
nxt = [[] for _ in range(N+1)]

#for ab in AB:
    #a, b = ab[0], ab[1]
for _ in range(N-1):
    a,b = map(int, input().split())
    nxt[a].append(b)
    nxt[b].append(a)

#for px in PX:
    #p,x = px[0], px[1]
for _ in range(Q):
    p,x = map(int, input().split())
    node[p] += x

visited = [False] * (N+1)
q = queue.Queue()
q.put(1)
cnt = 1
while not q.empty():
    cnt += 1
    v = q.get()
    visited[v] = True
    for nv in nxt[v]:
        node[nv] += node[v]
        if not visited[nv]:
            q.put(nv)
print(cnt)

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

Submission status: Wrong Answer

Solution code:
import queue

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

node = [0] * (N+1)
child = [[] for _ in range(N+1)]

for ab in AB:
    a, b = ab[0], ab[1]
    child[a].append(b)

for px in PX:
    p,x = px[0], px[1]
    node[p] += x

q = queue.Queue()
q.put(1)
while not q.empty():
    p = q.get()
    for c in child[p]:
        node[c] += node[p]
        q.put(c)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,q=map(int,input().split())
g=[[]for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

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

def dfs(i,j,k):
    nex=g[i]
    lis[i]=k
    for d in nex:
        if d==j: continue
        print(d)
        nk=k+lis[d]
        dfs(d,i,nk)

dfs(0,-1,lis[0])
print(*lis)

Submission status: Wrong Answer

Solution code:
# 愚直にQ回分各頂点を更新すると Q * N = 10^10 回の更新が必要で間に合わない
# 根のカウントを累計しておき、最後に木全体を操作しながらカウントを算出する
# 答えとなるカウント数 = 親 + 自分のカウントでOKなはず

from collections import deque

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

T = [[] for _ in range(N + 1)]

counts = [0] * (N + 1)

for _ in range(N - 1):
  a, b = map(int, input().split())
  T[a].append(b)
  T[b].append(b)
  
for _ in range(Q):
  p, x = map(int, input().split())
  counts[p] += x
  
q = deque([1])
visited = set()

# 1に近い順から処理していく
while q:
  parent = q.popleft()
  
  if parent in visited:
    continue
    
  visited.add(parent)
    
  for child in T[parent]:
    if child not in visited:
      counts[child] += counts[parent]
      q.append(child)
    
print(
  ' '.join(
    str(counts[i])
    for i in range(1, N + 1)
  )    
)

Submission status: Wrong Answer

Solution code:
# 愚直にQ回分各頂点を更新すると Q * N = 10^10 回の更新が必要で間に合わない
# 根のカウントを累計しておき、最後に木全体を操作しながらカウントを算出する
# 答えとなるカウント数 = 親 + 自分のカウントでOKなはず

from collections import deque

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

T = [[] for _ in range(N + 1)]

counts = [0] * (N + 1)

for _ in range(N - 1):
  a, b = map(int, input().split())
  T[a].append(b)
  
for _ in range(Q):
  p, x = map(int, input().split())
  counts[p] += x
  
q = deque([1])

# 1に近い順から処理していく
while q:
  parent = q.popleft()
  for child in T[parent]:
    counts[child] += counts[parent]
    q.append(child)
    
print(
  ' '.join(
    str(counts[i])
    for i in range(1, N + 1)
  )    
)

Submission status: Wrong Answer

Solution code:
# 愚直にQ回分各頂点を更新すると Q * N = 10^10 回の更新が必要で間に合わない
# 根のカウントを累計しておき、最後に木全体を操作しながらカウントを算出する
# 答えとなるカウント数 = 親 + 自分のカウントでOKなはず

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

T = [[] for _ in range(N + 1)]

counts = [0] * (N + 1)

for _ in range(N - 1):
  a, b = map(int, input().split())
  T[a].append(b)
  
for _ in range(Q):
  p, x = map(int, input().split())
  counts[p] += x
  
for parent, children in enumerate(T):
  for child in children:
    counts[child] += counts[parent]
    
print(
  ' '.join(
    str(counts[i])
    for i in range(1, N + 1)
  )    
)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

ans = [0] * (n + 1)

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

que = deque([[1, 0]])
while len(que) > 0:
    now = que.popleft()
    ans[now[0]] += now[1]
    for j in path[now[0]]:
        que.append([j, ans[now[0]]])

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