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:
N, Q = map(int, input().split())
Child = [[False] * N for _ in range(N)]
X = [0] * N
Y = [0] * N
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Child[a][b] = True
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    X[p] += x


def dfs(u, k):
    Y[u] += k
    for v in range(N):
        if Child[u][v]:
            dfs(v, k + X[v])


dfs(0, X[0])
print(' '.join(str(y) for y in Y))

Submission status: Wrong Answer

Solution code:
# D - Ki
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 -= 1
    b -= 1
    g[a].append(b)

def dfs(p, q):
    ans[p] += q
    for gi in g[p]:
        dfs(gi, q)

ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    dfs(p, x)
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2*(10**5)+1)

n, q = map(int, input().split())
tree_dic = [[] for _ in range(n)] #tree_dic = {i:{p:j, c:[k, l]}}
for i in range(n):
    tree_dic[i] = [-1, [], 0]

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

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

x_list = [0 for _ in range(n)]

import queue
next_visit = queue.Queue()
next_visit.put(0)
while not next_visit.empty():
    i = next_visit.get()
    tmp = tree_dic[i][2]
    if i != 0:
        tmp += x_list[tree_dic[i][0]]
    x_list[i] = tmp
    for j in tree_dic[i][1]:
        next_visit.put(j)

for i in x_list:
    print(i, end=" ")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2*(10**5)+1)

n, q = map(int, input().split())
tree_dic = [{} for _ in range(n)] #tree_dic = {i:{p:j, c:[k, l]}}
for i in range(n):
    tree_dic[i] = {"p": -1, "c": [], "x": 0}

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

for i in range(q):
    p, x = map(int, input().split())
#     tree_dic[p-1]["x"] += x
# 
# x_list = [0 for _ in range(n)]
# 
# import queue
# next_visit = queue.Queue()
# next_visit.put(0)
# while not next_visit.empty():
#     i = next_visit.get()
#     tmp = tree_dic[i]["x"]
#     if i != 0:
#         tmp += x_list[tree_dic[i]["p"]]
#     x_list[i] = tmp
#     for j in tree_dic[i]["c"]:
#         next_visit.put(j)
# 
# for i in x_list:
#     print(i, end=" ")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2*(10**5)+1)

n, q = map(int, input().split())
tree_dic = [{} for _ in range(n)] #tree_dic = {i:{p:j, c:[k, l]}}
for i in range(n):
    tree_dic[i] = {"p": -1, "c": [], "x": 0}

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

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

x_list = [0 for _ in range(n)]

import queue
next_visit = queue.Queue()
next_visit.put(0)
while not next_visit.empty():
    i = next_visit.get()
    tmp = tree_dic[i]["x"]
    if i != 0:
        tmp += x_list[tree_dic[i]["p"]]
    x_list[i] = tmp
    for j in tree_dic[i]["c"]:
        next_visit.put(j)

for i in x_list:
    print(i, end=" ")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2*(10**5)+1)

n, q = map(int, input().split())
tree_dic = {} #tree_dic = {i:{p:j, c:[k, l]}}
for i in range(n):
    tree_dic[i] = {"p": -1, "c": [], "x": 0}

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

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

x_list = [0 for _ in range(n)]

import queue
next_visit = queue.Queue()
next_visit.put(0)
while not next_visit.empty():
    i = next_visit.get()
    tmp = tree_dic[i]["x"]
    if i != 0:
        tmp += x_list[tree_dic[i]["p"]]
    x_list[i] = tmp
    for j in tree_dic[i]["c"]:
        next_visit.put(j)

for i in x_list:
    print(i, end=" ")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2*(10**5)+1)
def make_tree(node):
    global cnt
    cnt += 1
    for i in tree_list[node]:
        if i == tree_dic[node]["p"]:
            continue
        tree_dic[node]["c"].append(i)
        tree_dic[i]["p"] = node
        make_tree(i)

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

tree_dic = {} #tree_dic = {i:{p:j, c:[k, l]}}
for i in range(n):
    tree_dic[i] = {"p": -1, "c": [], "x": 0}

make_tree(0)

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

x_list = [0 for _ in range(n)]

import queue
next_visit = queue.Queue()
next_visit.put(0)
while not next_visit.empty():
    i = next_visit.get()
    tmp = tree_dic[i]["x"]
    if i != 0:
        tmp += x_list[tree_dic[i]["p"]]
    x_list[i] = tmp
    for j in tree_dic[i]["c"]:
        next_visit.put(j)

for i in x_list:
    print(i, end=" ")

Submission status: Wrong Answer

Solution code:
def make_tree(node):
    for i in tree_list[node]:
        if i != tree_dic[node]["p"]:
            tree_dic[node]["c"].append(i)
            tree_dic[i]["p"] = node
            make_tree(i)

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

# tree_dic = {} #tree_dic = {i:{p:j, c:[k, l]}}
# for i in range(n):
#     tree_dic[i] = {"p": None, "c": [], "x": 0}
# 
# make_tree(0)
#
# for i in range(q):
#     p, x = map(int, input().split())
#     tree_dic[p-1]["x"] += x
# # print(tree_dic)
#
# x_list = [0 for _ in range(n)]
#
# import queue
# next_visit = queue.Queue()
# next_visit.put(0)
# while not next_visit.empty():
#     i = next_visit.get()
#     tmp = tree_dic[i]["x"]
#     if i != 0:
#         tmp += x_list[tree_dic[i]["p"]]
#     x_list[i] = tmp
#     for j in tree_dic[i]["c"]:
#         next_visit.put(j)
#
# for i in x_list:
#     print(i, end=" ")

Submission status: Wrong Answer

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


def dfs(u, x):
    Cnt[u] += x
    for v in range(N):
        if Child[u][v]:
            dfs(v, x)


for _ in range(Q):
    p, x = map(int, input().split())
    dfs(p - 1, x)
print(' '.join(str(c) for c in Cnt))

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q=map(int,input().split())
AB=[tuple(map(int,input().split())) for _ in range(N-1)]
k=[0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    k[p-1]+=x
q=deque([1])
ab=AB[:]
while q:
    t=q.popleft()
    tab=ab[:]
    for a,b in tab:
        if t==a:
            q.append(b)
            k[b-1]+=k[t-1]
            ab.remove((a,b))
            break
        elif t==b:
            q.append(a)
            k[a-1]+=k[t-1]
            ab.remove((a,b))
            break
print(*k)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
edges = {}
p = []

def dfs(target_node, keisyo_point):
    global p
    p[target_node] += keisyo_point
    next_node = edges[target_node]
    if not next_node:
        return
    else:
        for next in next_node:
            dfs(next, p[target_node])

def main():
    global edges, p
    n, q = map(int, input().split())
    #edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    edges = {e: [] for e in range(1, n+1)}
    for _ in range(n - 1):
        a, b = tuple(map(int, input().split()))
        edges[a].append(b)
    p = [0] * (n + 1)
    for _ in range(q):
        p1, x1 = map(int, input().split())
        p[p1] += x1

    dfs(1, 0)
    for i1 in range(1, n + 1):
        print(p[i1], end=' ')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
edges = []
p = []
r = []
def dfs(target_node, keisyo_point):
    for ep in p:
        if ep[0] == target_node:
            keisyo_point += ep[1]
    r[target_node] += keisyo_point

    senisaki = []
    for edge in edges:
        if edge[0] == target_node:
            senisaki.append(edge[1])
    if not senisaki:
        return
    else:
        for es in senisaki:
            dfs(es, keisyo_point)

def main():
    global edges, r, p
    n,q = map(int, input().split())
    for _ in range(n - 1):
        edges.append(tuple(map(int, input().split())))
    p = []
    for _ in range(q):
        p.append(tuple(map(int, input().split())))
    r = [0] * (n + 1)

    dfs(1,0)
    for i1 in range(1, n + 1):
        print(r[i1], end=' ')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
n, q = map(int, input().split())

edges = [[] for _ in range(n)]
for _ in range(n - 1):
    frm, to = map(int, input().split())
    # 0-index
    edges[frm - 1].append(to - 1)
#    edges[to - 1].append(frm - 1)

scores = [0] * n
for _ in range(q):
    v, s = map(int, input().split())
    scores[v - 1] += s


def dfs(frm, cur):
    if cur > 0:
        scores[cur] += scores[frm]
    for to in edges[cur]:
        if frm != to:
            dfs(cur, to)


print(edges)
dfs(-1, 0)
print(" ".join([str(w) for w in scores]))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
n, q = map(int, input().split())

tree = [[] for _ in range(n)]
for _ in range(n - 1):
    frm, to = map(int, input().split())
    # 0-index
    tree[frm - 1].append(to - 1)

counter = [0] * n
scores = []
for _ in range(q):
    v, s = map(int, input().split())
    scores.append([v - 1, s])


def dfs(tree, v, score):
    global visited
    global counter
    visited[v] = True
    counter[v] += score
    for next_v in tree[v]:
        if visited[next_v]:
            continue
        else:
            dfs(tree, next_v, score)


for score in scores:
    visited = [False] * n
    dfs(tree, score[0], score[1])

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

Submission status: Wrong Answer

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

def search(pos, x):
    Ans[pos - 1] += x
    for i in range(n-1):
        if AB[i][0] == pos:
            search(AB[i][1], x)

n, q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n-1)]

Ans = [0 for i in range(n)]

for i in range(q):
    p, x = map(int, input().split())
    search(p, x)
    
for i in range(n-1):
    print(Ans[i], end = ' ')
print(Ans[n-1])

Submission status: Wrong Answer

Solution code:
def search(pos, x):
    Ans[pos - 1] += x
    for i in range(n-1):
        if AB[i][0] == pos:
            search(AB[i][1], x)

n, q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n-1)]

Ans = [0 for i in range(n)]

for i in range(q):
    p, x = map(int, input().split())
    search(p, x)
    
for i in range(n-1):
    print(Ans[i], end = ' ')
print(Ans[n-1])

Submission status: Wrong Answer

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

tree={}
tree[1]=-1
for n in range(2,N):
    tree[n]=1
    
cnt=[0]*N

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

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

for k in range(1,N):
    cnt[k]+=cnt[tree[k+1]-1]

# def search(root,x):
#     leaf =[]
#     for i,j in tree.items():
#         if j ==root:
#             leaf.append(i)
        
#     if len(leaf)!=0:
#         for k in leaf:
#             search(k,x)
#             cnt[k-1]+=x

# for i in range(N-1):
#     a,b = map(int,input().split())
#     tree[b]=a
# for j in range(Q):
#     p,x=map(int,input().split())
#     if p==1:
#         cnt+=x
#     else:
#         cnt[p-1]+=x
#         search(p,x)


print(*cnt)

Submission status: Wrong Answer

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

import numpy as np
cnt = np.array([0]*N)

tree={}
tree[1]=-1

def search(root,x):
    leaf =[]
    for i,j in tree.items():
        if j ==root:
            leaf.append(i)
        
    if len(leaf)!=0:
        for k in leaf:
            search(k,x)
            cnt[k-1]+=x

for i in range(N-1):
    a,b = map(int,input().split())
    tree[b]=a
for j in range(Q):
    p,x=map(int,input().split())
    if p==1:
        cnt+=x
    else:
        cnt[p-1]+=x
        search(p,x)


print(*cnt)

Submission status: Wrong Answer

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

import numpy as np
cnt = np.array([0]*N)

tree={}
tree[1]=-1

def search(root,x):
    leaf =[]
    for i,j in tree.items():
        if j ==root:
            leaf.append(i)
        
    if len(leaf)!=0:
        for k in leaf:
            search(k,x)
            cnt[k-1]+=x

for i in range(N-1):
    a,b = map(int,input().split())
    tree[b]=a
for j in range(Q):
    p,x=map(int,input().split())
    cnt[p-1]+=x
    search(p,x)


print(*cnt)

Submission status: Wrong Answer

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

import numpy as np
tree = np.array([-1]*N) 
cnt = np.array([0]*N)


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

for j in range(Q):
    p,x=map(int,input().split())
    #根の番号
    p-=1
    if p!=0:
        cnt[p]+=x
        cnt[np.where(tree == p)] +=x
    else:
        cnt+=x

print(cnt)

Submission status: Wrong Answer

Solution code:
def dfs(ans, pos, value, root):
    stack = [pos]
    while len(stack) > 0:
        p = stack.pop()
        ans[p - 1] += value
        if p in root:
            for t in root[p]:
                stack.append(t)


N, Q = map(int, input().split())
root = {}
for _ in range(N - 1):
    x, y = map(int, input().split())
    if not x in root:
        root[x] = [y]
    else:
        root[x].append(y)

ans = [0 for _ in range(N)]
stack = []
for _ in range(Q):
    x, y = map(int, input().split())
    dfs(ans, x, y, root)


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

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
n,q=map(int,input().split())
g=[list(map(int,input().split())) for i in range(n-1)]
g.sort(key=lambda x: x[0])
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
for i in range(n-1):
    ans[g[i][1]-1]+=ans[g[i][0]-1]
print(*ans,sep=" ")

Submission status: Wrong Answer

Solution code:
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,Q = LI()
ab = [LI() for _ in [None]*(N-1)]
px = [LI() for _ in [None]*(Q)]
ans = [0]*(N+1) #1_index
deque = collections.deque()
graph = [deque for _ in [None]*(N+1)] #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [0]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
AB=sorted([tuple(map(int,input().split())) for _ in range(N-1)])
k=[0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    k[p-1]+=x
for a,b in AB:
    k[b-1]+=k[a-1]
print(*k)

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
AB=[tuple(map(int,input().split())) for _ in range(N-1)]
k=[0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    k[p-1]+=x
for a,b in AB:
    k[b-1]+=k[a-1]
print(*k)

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,q = mi()
A = [[]for _ in range(n)]
for _ in range(n-1):
    a,b = mi()
    A[a-1].append(b-1)
P = [0]*(2*(10**5))
for _ in range(q):
    p,x = mi()
    P[p-1] += x

from collections import deque
que = deque()
dp = [0]*(n)
que.append((0,0))

while que:
    ima,mae = que.popleft()
    dp[ima] = P[ima] + dp[mae]
    for i in A[ima]:
        que.append((i,ima))

print(*dp)

Submission status: Wrong Answer

Solution code:
import collections
def LI(): return list(map(int,input().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = [0]*(N+1) #1_index
graph = {i:collections.deque() for i in range(1,N+1)} #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [-1]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for g_NO in graph:
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Wrong Answer

Solution code:
import collections
def LI(): return list(map(int,input().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = [0]*(N+1) #1_index
graph = [collections.deque()]*(N+1) #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [-1]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

Submission status: Wrong Answer

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

def main():
    N, Q = map(int,input().split())
    tree = [[] for _ in range(N+1)]
    ans = [0] * (N+1)
    parent_counter = [0] * (N+1)

    def add_tree(x,y):
        tree[x].append(y)

    def solve():
        next = [1]
        count = [0] * (N+1)

        while len(next) > 0:
            i = next.pop()
            count[i] += parent_counter[i]
            for j in tree[i]:
                count[j] += count[i]
                next.append(j)

        return count[1:]

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

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


    print(*solve())

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

def main():
    N, Q = map(int,input().split())
    tree = [[] for _ in range(N+1)]
    ans = [0] * (N+1)
    parent_counter = [0] * (N+1)

    def add_tree(x,y):
        tree[x].append(y)

    def solve(i,count):
        count += parent_counter[i]
        ans[i] = count
        for next in tree[i]:
            solve(next,count)

        return ans[1:]

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

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


    print(*solve(1,0))

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

def main():
    N, Q = map(int,input().split())
    tree = {}
    ans = [0] * (N+1)
    parent_counter = [0] * (N+1)

    def add_tree(x,y):
        if x > y:
            x,y = y,x

        if not x in tree:
            tree[x] = [y]
        else:
            tree[x].append(y)

    def solve(i,count):
        count += parent_counter[i]
        ans[i] = count
        if i in tree.keys():
            for next in tree[i]:
                solve(next,count)

        return ans[1:]

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


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


    print(*solve(1,0))

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import collections,copy
def LI(): return list(map(int,input().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = {i:0 for i in range(1,N+1)} #1_index
graph = {i:collections.deque() for i in range(1,N+1)} #1_index
for a,b in ab:
    graph[a].append(b)
def dfs(p,x):
    seen = {i:-1 for i in range(1,N+1)} #1_index
    stack = []
    graph_dfs = copy.deepcopy(graph)
    seen[p] = 1
    stack.append(p)
    ans[p] += x
    while stack:
        s = stack.pop()
        if not graph_dfs[s]:
            continue
        for j in range(len(graph_dfs[s])):
            g_NO = graph_dfs[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += x
for p,x in px:
    dfs(p,x)
print(*[a for a in ans.values()])

Submission status: Wrong Answer

Solution code:
import collections,copy
def LI(): return list(map(int,input().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = {i:0 for i in range(1,N+1)} #1_index
graph = {i:collections.deque() for i in range(1,N+1)} #1_index
for a,b in ab:
    graph[a].append(b)
def dfs(p,x):
    seen = {i:-1 for i in range(1,N+1)} #1_index
    stack = []
    graph_dfs = copy.deepcopy(graph)
    seen[p] = -1
    stack.append(p)
    ans[p] += x
    while stack:
        s = stack.pop()
        if not graph_dfs[s]:
            continue
        for j in range(len(graph_dfs[s])):
            g_NO = graph_dfs[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += x
for p,x in px:
    dfs(p,x)
print(*[a for a in ans.values()])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

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


def dfs(s):
    check = [False] * n
    stack = deque([s])
    while stack:
        now = stack.pop()
        check[now] = True
        for nxt in graph[now]:
            if check[nxt]:
                continue
            stack.appendleft(nxt)
            cnt[nxt] += cnt[now]


dfs(0)
print(*cnt)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

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


def dfs(s):
    check = [False] * (n + 1)
    stack = deque([s])
    while stack:
        now = stack.pop()
        check[now] = True
        for nxt in graph[now]:
            if check[nxt]:
                continue
            stack.appendleft(nxt)
            cnt[nxt] += cnt[now]


dfs(1)
print(*cnt[1:])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500*500)

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

graph = [[] for _ in range(N+1)]
value = [0] * (N + 1)

for edge in edges:
    graph[edge[0]].append(edge[1])
    # graph[edge[1]].append(edge[0])

for que in process:
    value[que[0]] += que[1]

def dfs(s, parent, add):
    value[s] += add
    for x in graph[s]:
        if x == parent:
            continue
        dfs(x, s, value[s])

dfs(1, 0, 0)

ans =  ' '.join(map(str, value[1:]))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500*500)

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

graph = [[] for _ in range(N+1)]
sum_stack = [0] * (N + 1)

for edge in edges:
    graph[edge[0]].append(edge[1])

for que in process:
    sum_stack[que[0]] += que[1]

ans = [0] * (N+1)



def dfs(s):
    if ans[s] == 0:
        ans[s] = sum_stack[s]
    if ans[s] != 0:
        for v in graph[s]:
            ans[v] = ans[s] + sum_stack[v]
            dfs(v)

dfs(1)

del ans[0]
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500*500)

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

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

for edge in edges:
    graph[edge[0]].append(edge[1])

count = [0] * (N+1)

def dfs(p,x):
    count[p] += x
    for i in graph[p]:
        dfs(i,x)

for i in process:
    dfs(i[0], i[1])

del count[0]

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

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
M=[list(map(int,input().split()))for _ in range(N-1)]
p=[list(map(int,input().split()))for _ in range(Q)]
s=[0]*N
c=[0]*N
plus=[0]*N
p.sort()
tes=[0]*N
for w in range(Q):
  plus[p[w][0]-1]+=p[w][1]
def d(m):
  c[m]=1
  s[m]+=plus[m]  
  for i in range(tes[m],N-1):
    if M[i][0]-1==m:
      tes[m]=i
      if c[M[i][1]-1]==0:
        s[M[i][1]-1]+=s[m]
        d(M[i][1]-1)
for j in range(N):
  c[j] or d(j)
for q in range(N):
  print(s[q],end=" ")

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
M=[list(map(int,input().split()))for _ in range(N-1)]
p=[list(map(int,input().split()))for _ in range(Q)]
s=[0]*N
c=[0]*N
plus=[0]*N
p.sort()
for w in range(Q):
  plus[p[w][0]-1]+=p[w][1]
def d(m):
  global t
  c[m]=1
  s[m]+=plus[m]
  for i in range(N-1):
    if M[i][0]-1>m:
      break
    elif M[i][0]-1==m:
      if c[M[i][1]-1]==0:
        s[M[i][1]-1]+=s[m]
        d(M[i][1]-1)
for j in range(N):
  c[j] or d(j)
for q in range(N):
  print(s[q],end=" ")

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
M=[list(map(int,input().split()))for _ in range(N-1)]
p=[list(map(int,input().split()))for _ in range(Q)]
s=[0]*N
c=[0]*N
plus=[0]*N
for w in range(Q):
  plus[p[w][0]-1]+=p[w][1]
def d(m):
  global t
  c[m]=1
  s[m]+=plus[m]
  for i in range(N-1):
    if M[i][0]-1==m:
      if c[M[i][1]-1]==0:
        s[M[i][1]-1]+=s[m]
        d(M[i][1]-1)
for q in range(N):
  print(s[q],end=" ")

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
M=[list(map(int,input().split()))for _ in range(N-1)]
p=[list(map(int,input().split()))for _ in range(Q)]
s=[0]*N
c=[0]*N
plus=[0]*N
for w in range(Q):
  plus[p[w][0]-1]+=p[w][1]
def d(m):
  global t
  c[m]=1
  s[m]+=plus[m]
  for i in range(N-1):
    if M[i][0]-1==m:
      if c[M[i][1]-1]==0:
        s[M[i][1]-1]+=s[m]
        d(M[i][1]-1)
  c[m]=2

d(0)
for q in range(N):
  print(s[q],end=" ")

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
M=[list(map(int,input().split()))for _ in range(N-1)]
p=[list(map(int,input().split()))for _ in range(Q)]
s=[0]*N
c=[0]*N
plus=[0]*N
for w in range(Q):
  plus[p[w][0]-1]+=p[w][1]
def d(m):
  global t
  c[m]=1
  s[m]+=plus[m]
  for i in range(N-1):
    if M[i][0]-1==m:
      if c[M[i][1]-1]==0:
        s[M[i][1]-1]+=s[m]
        d(M[i][1]-1)
  c[m]=2

for j in range(N):
  c[j] or d(j)
for q in range(N):
  print(s[q],end=" ")

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
M=[list(map(int,input().split()))for _ in range(N-1)]
p=[list(map(int,input().split()))for _ in range(Q)]
s=[0]*N
c=[0]*N
plus=[0]*N
for w in range(Q):
  plus[p[w][0]-1]+=p[w][1]
def d(m):
  c[m]=1
  for z in range(N):
    if c[z]==1:
      s[m]+=plus[z]
  for i in range(N-1):
    if M[i][0]-1==m:
      c[M[i][1]-1] or d(M[i][1]-1)
  c[m]=2
for j in range(N):
  c[j] or d(j)
for q in range(N):
  print(s[q],end=" ")

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
M=[list(map(int,input().split()))for _ in range(N-1)]
p=[list(map(int,input().split()))for _ in range(Q)]
s=[0]*N
c=[0]*N
plus=[0]*N
for w in range(Q):
  plus[p[w][0]-1]+=p[w][1]
def d(m):
  global t
  c[m]=1
  for z in range(N):
    if c[z]==1:
      s[m]+=plus[z]
  for i in range(N-1):
    if M[i][0]-1>m:
      break
    elif M[i][0]-1==m:
      c[M[i][1]-1] or d(M[i][1]-1)
  c[m]=2

for j in range(N):
  c[j] or d(j)
for q in range(N):
  print(s[q],end=" ")

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())

graph=[[]for i in range(n)]

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

score=[0]*n

for i in range(q):
    x,y=map(int,input().split())
    score[x-1]+=y
    
from collections import deque
option=deque()
option.append(0)
completed=[0]*n

while option:
    now=option.pop()
    completed[now]=1
    for nex in graph[now]:
        if completed[nex]==0 and nex not in option:
            score[nex]+=score[now]
            option.append(nex)

print(*score)