Problem:


Score : 400 points

Problem Statement

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

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

Now, the following Q operations will be performed:

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

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

Constraints

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

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

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

100 110 111 110

The tree in this input is as follows:

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

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

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

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

Sample Input 2

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

Sample Output 2

20 20 20 20 20 20



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


Sample output:
100 110 111 110

Submission status: Wrong Answer

Solution code:
import sys
from collections import 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)
p = [0] * q
x = [0] * q
for i in range(q):
    pp, xx = map(int, input().split())
    p[i], x[i] = pp, xx

ans = [0] * (n+1)

for i in range(q):
    que = deque([p[i]])
    while len(que) > 0:
        now = que.popleft()
        ans[now] += x[i]
        for j in path[now]:
            que.append(j)

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

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
L=[[] for _ in range(n)]
star=[]
for _ in range(n-1):
    a,b=map(int,input().split())
    L[a-1].append(b)
    L[b-1].append(a)
for i in range(1,n):
    if len(L[i])==1:
        star.append(i+1)

mp=[[x] for x in range(1,n+1)]
while len(star)>1 or star[0]!=1:
    nstar=[]
    for x in star:
        w=L[x-1][0]
        if x!=1:
            mp[w-1] += mp[x-1]
            L[w-1].remove(x)
        if w not in nstar:
            nstar.append(w)
    star=nstar

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q = (int(x) for x in input().split())
connection ={i:[] for i in range(1,N+1)}
#木の構造
for i in range(1,N):
    a,b = (int(x) for x in input().split())
    connection[a].append(b)
    connection[b].append(a)

#各頂点のポイント入力
point ={i:0 for i in range(1,N+1)}
for i in range(1,Q+1):
    p,x = (int(x) for x in input().split())
    point[p] =x

#深さ優先探索
dq =deque()
dq.append(1)
passed ={i:0 for i in range(1,N+1)} #各頂点を通過チェック、０は未通過
while dq:
    now =dq.pop()
    passed[now] =1
    for next in connection[now]:
        if passed[next] ==1:
            continue
        point[next] +=point[now]
        dq.append(next)
        #print(next,end=" ")
print(*point.values())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(node,cnt):
  for nd in tree[node]:
    if visited[nd] > -1:
      continue
    counter[nd] += cnt
    visited[nd] =1
    dfs(nd,cnt+p[nd])
    


N,Q= map(int,input().split())
tree = {}
p = {}
counter = [0]*(N+1)
visited = [-1]*(N+1)
for i in range(1,N+1):
  tree[i] = []
  p[i] = 0
  
for i in range(N-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
  
for i in range(Q):
  p_i,x = map(int,input().split())
  p[p_i] += x
  
visited[1] = 1
counter[1] += p[1]
dfs(1,p[1])

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

Submission status: Wrong Answer

Solution code:
N,Q = (int(x) for x in input().split())
connection ={i:[] for i in range(1,N+1)}
#木の構造
for i in range(1,N):
    a,b = (int(x) for x in input().split())
    connection[a].append(b)
    connection[b].append(a)
#頂点を通過した時のポイント
point ={i:0 for i in range(1,N+1)}
for i in range(1,Q+1):
    p,x = (int(x) for x in input().split())
    point[p] +=x

#幅優先探索
start =1
stack=[start]
prev =0
point[0]=0
passed =[]
while stack:
    sarch =stack.pop()
    if sarch not in passed:
        point[sarch] +=point[prev]
        
        stack.extend(connection[sarch])
        passed.append(sarch)
        print((prev,sarch))
        prev =sarch
del point[0]
print(*(point.values()))

Submission status: Wrong Answer

Solution code:
n,q = map(int, input().split())
way = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    way[a-1].append(b-1)
add = [0]*n
for i in range(q):
    a,b = map(int, input().split())
    add[a-1] += b
ans = [0]*n
ans[0] += add[0]
    
stack = [(0,add[0])]
while stack:
    a,b = stack.pop()
    for i in range(len(way[a])):
        stack.append((way[a][i],b+add[way[a][i]]))
        ans[way[a][i]] = b+add[way[a][i]]
print(*ans)

Submission status: Wrong Answer

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


def input(): return sys.stdin.readline().strip()


def resolve():

    N, Q = map(int, input().split())
    M = N-1  # 頂点数，辺数
    ans = [0]*N
    # グラフ入力受取 (ここでは無向グラフを想定)
    G = [[] for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        # G[b].append(a)

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

    seen = [False]*N

    def dfs(G, v=-1):
        seen[v] = True

        for next_v in G[v]:
            if seen[next_v]:
                continue
            ans[next_v] += ans[v]
            dfs(G, next_v)

    # 頂点 0 をスタートとした探索
    dfs(G, 0)
    print(*ans)


resolve()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

n, q = map(int, input().split())
root = [[] for _ in range(n)]
plus = [0 for _ in range(n)]
ans = [0 for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    root[a - 1].append(b - 1)
for _ in range(q):
    p, x = map(int, input().split())
    plus[p - 1] += x
    
def dfs(pos, cost):
    check[pos] = True
    cost += plus[pos]
    ans[pos] = cost
    for next_pos in root[pos]:
        dfs(next_pos, cost)

check = [False for _ in range(n)]
for i in range(n):
    if not check[i]:
        dfs(i, 0)

for i in ans[:-1]:
    print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

n, q = map(int, input().split())
root = [[] for _ in range(n)]
plus = [0 for _ in range(n)]
ans = [0 for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    root[a - 1].append(b - 1)
for _ in range(q):
    p, x = map(int, input().split())
    plus[p - 1] += x
    
def dfs(pos, cost):
    cost += plus[pos]
    ans[pos] = cost
    for next_pos in root[pos]:
        dfs(next_pos, cost)

dfs(0, 0)

for i in ans[:-1]:
    print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

n, q = map(int, input().split())
root = [[] for _ in range(n)]
plus = [0 for _ in range(n)]
ans = [0 for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    root[a - 1].append(b - 1)
for _ in range(q):
    p, x = map(int, input().split())
    plus[p - 1] += x
    
def dfs(root, plus, pos, ans, cost):
    cost += plus[pos]
    ans[pos] = cost
    for next_pos in root[pos]:
        dfs(root, plus, next_pos, ans, cost)
    cost -= plus[pos]
        
dfs(root, plus, 0, ans, 0)

for i in ans[:-1]:
    print(i, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

n, q = map(int, input().split())
root = [[] for _ in range(n)]
plus = [0 for _ in range(n)]
ans = [0 for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    root[a - 1].append(b - 1)
for _ in range(q):
    p, x = map(int, input().split())
    plus[p - 1] += x
    
def dfs(root, plus, pos, ans, cost):
    cost += plus[pos]
    ans[pos] = cost
    for next_pos in root[pos]:
        dfs(root, plus, next_pos, ans, cost)
    cost -= plus[pos]
        
dfs(root, plus, 0, ans, 0)

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
n, q = map(int, input().split())
Tree = [[] for i in range(n)]
children = set()
for i in range(n-1):
    a, b = map(int, input().split())
    Tree[a-1].append(b-1)
    children.add(b-1)
root = list(set(list(range(n))) - children)[0]

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

Ans = [0] * n
stack = [[root, 0]]
while stack != []:
    temp = []
    for node, point in stack:
        point += Add_point[node]
        Ans[node] = point
        for next_node in Tree[node]:
            temp.append([next_node, point])
    stack = temp

for i in range(n):
    print(Ans[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
n, q = map(int, input().split())
Tree = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    Tree[a-1].append(b-1)

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

Ans = [0] * n
stack = [[0, 0]]
while stack != []:
    temp = []
    for node, point in stack:
        point += Add_point[node]
        Ans[node] = point
        for next_node in Tree[node]:
            temp.append([next_node, point])
    stack = temp

for i in range(n):
    print(Ans[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
n, q = map(int, input().split())
Tree = dd(lambda: [])
for i in range(n-1):
    a, b = map(int, input().split())
    Tree[a-1].append(b-1)

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

Ans = [0] * n
stack = [[0, 0]]
while stack != []:
    temp = []
    for node, point in stack:
        point += Add_point[node]
        Ans[node] = point
        for next_node in Tree[node]:
            temp.append([next_node, point])
    stack = temp

for i in range(n):
    print(Ans[i])

Submission status: Wrong Answer

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

from collections import defaultdict as dd
n, q = map(int, input().split())
Tree = dd(lambda: [])
for i in range(n-1):
    a, b = map(int, input().split())
    Tree[a].append(b)

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

Ans = dd(lambda: 0)
def write(node, point):
    point += Point[node]
    Ans[node] = point
    for next_node in Tree[node]:
        write(next_node, point)
write(1, 0)

for i in range(1, n+1):
    print(Ans[i])

Submission status: Wrong Answer

Solution code:
cin = open(0).read().strip().split('\n')
n, q = map(int, cin[0].split(' '))
ab = [tuple(map(int, a.split(' '))) for a in cin[1:n]]
px = [tuple(map(int, a.split(' '))) for a in cin[n:n+q]]

g = [[] for _ in range(n)]
for abi in ab:
    g[abi[0]-1].append(abi[1]-1)

for idx in range(n):
    g[idx] = sorted(g[idx])

score = [0]*n
for pxi in px:
    score[pxi[0]-1] += pxi[1]

for idx in range(n):
    for aa in g[idx]:
        score[aa] += score[idx]

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

Submission status: Wrong Answer

Solution code:
cin = open(0).read().strip().split('\n')
n, q = map(int, cin[0].split(' '))
ab = [tuple(map(int, a.split(' '))) for a in cin[1:n]]
px = [tuple(map(int, a.split(' '))) for a in cin[n:n+q]]

g = [[] for _ in range(n)]
for abi in ab:
    g[abi[0]-1].append(abi[1]-1)

for idx in range(n):
    g[idx] = sorted(g[idx])

score = [0]*n
for pxi in px:
    score[pxi[0]-1] = pxi[1]

for idx in range(n):
    for aa in g[idx]:
        score[aa] += score[idx]

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

Submission status: Wrong Answer

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

def add(m,n,x,v,r):
    r[x] += v
    for i in range(n):
        if(m[x][i] == 1):
            add(m,n,i,v,r)

n,q = LI()
m = [[0]*n for i in range(n)]
r = [0]*n
for i in range(n-1):
    a,b = LI()
    m[a-1][b-1] = 1
for i in range(q):
    p,x = LI()
    add(m,n,p-1,x,r)
print(*r)

Submission status: Wrong Answer

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

import numpy as np
ans = np.zeros(N)

#木の表記を変更
tree = []
for i in range(N):
    list_j = []
    for j in ab:
        if j[0]-1 == i:
            list_j.append(j[1])
    tree.append(list_j)


    
def plus_point(p,x,tree,ans):
    ans[p-1] += x
    #print(p,x)
    if tree[p-1] == []:#葉のない頂点だった場合
        return p, x, tree, ans
    
    #葉がある場合
    for i in tree[p-1]:
        #print(tree[p-1])
        _,_,_,ans = plus_point(i,x,tree,ans)
        
    return p, x, tree, ans
    

for p, x in px:
    #pとその部分木にxを足す
    _,_,_,ans = plus_point(p, x, tree,ans)

ans = [int(i) for i in ans]
    
print(*ans)

Submission status: Wrong Answer

Solution code:
N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
node_lst=sorted(node_lst, key=lambda x:x[0])
for l in node_lst:
    src, dst = l[0]-1, l[1]-1
    cnt_lst[dst]+=cnt_lst[src]
print(" ".join([str(c) for c in cnt_lst]))

Submission status: Wrong Answer

Solution code:
n, q = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(n-1)]
px = [tuple(map(int,input().split())) for _ in range(q)]
ab.sort()

# The list saves its origin.
origin_list = [0]*n
for a,b in ab:
    origin_list[b-1] = a

# The dict saves its destination candidates.
edge_dict_d = {i:set() for i in range(1,n+1)}
for i in range(2,n+1):
    origin = origin_list[i-1]
    while origin != 0:
        edge_dict_d[origin].add(i)
        origin = origin_list[origin-1]
# print(edge_dict_d)

ans = [0]*n
for p, x in px:
    ans[p-1] += x
    for j in edge_dict_d[p]:
        ans[j-1] += x

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




# # The dict saves its destination.
# edge_dict = {i:set() for i in range(1,n+1)}
# for a,b in ab:
#     edge_dict[a].add(b)
# #print(edge_dict)

# flag = True
# while flag:
#     flag = False
#     for i in range(1,n+1):
#         after = edge_dict[i]
#         for j in edge_dict[i]:
#             after = after.union(edge_dict[j])
#         if after != edge_dict[i]:
#             edge_dict[i] = after
#             flag = True
# #    print(edge_dict)

Submission status: Wrong Answer

Solution code:
n, q = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(n-1)]
px = [tuple(map(int,input().split())) for _ in range(q)]
ab.sort()

edge_dict = {i:set() for i in range(1,n+1)}
for a,b in ab:
    edge_dict[a].add(b)
#print(edge_dict)

flag = True
while flag:
    flag = False
    for i in range(1,n+1):
        after = edge_dict[i]
        for j in edge_dict[i]:
            after = after.union(edge_dict[j])
        if after != edge_dict[i]:
            edge_dict[i] = after
            flag = True
#    print(edge_dict)

ans = [0]*n
for p, x in px:
    ans[p-1] += x
    for j in edge_dict[p]:
        ans[j-1] += x

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n,q = list(map(int, input().split()))
li = [[] for i in range(n)]
ans=[0]*n


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

def dfs(now, v, p=None):
    ans[now]+=v
    for u in range(len(li[now])):
        if li[now][u] != now:
            dfs(li[now][u],ans[now],now)
        else:
            return


dfs(0,0)
for i in ans:
    print(i)

Submission status: Wrong Answer

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

n,q = list(map(int, input().split()))
li = [[] for i in range(n)]
ans=[0]*n


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

def dfs(now, v, p=None):
    ans[now]+=v
    for u in li[now]:
        if u != now:
            dfs(u,ans[now],now)
        else:
            return


dfs(0,0)
for i in ans:
    print(i)

Submission status: Wrong Answer

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


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

def dfs(now, v, p=None):
    ans[now]+=v
    for u in li[now]:
        if u == now:
            return
        dfs(u,ans[now],now)


dfs(0,0)
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
sys.setrecursionlimit(200100)
N, Q = map(int, input().split())
graph = [[] for _ in range(N)]
visited = [0] * N
children = [0] * N
count = 0
order = [0] * N
def dfs_recursive(edge):
    global count
    visited[edge] = 1
    order[edge] = count
    count += 1
    child = edge
    for e in graph[edge]:
        if not visited[e]:
            child = dfs_recursive(e)
    children[edge] = child
    return child
for _ in range(N - 1):
    a, b = map(lambda n: int(n) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
dfs_recursive(0)
imos = [0] * (N + 1)
for _ in range(Q):
    p, x = map(int, input().split())
    root = p - 1
    root_idx = order[root]
    child = children[root]
    child_idx = order[child]
    imos[root_idx] += x
    imos[child_idx + 1] -= x
ans = list(accumulate(imos))
ans.pop()
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

from heapq import heappop, heappush

class Dijkstra:
    """
    shortest_distance(goal): startノードからgoalノードまでの最短距離
    shortest_path(goal): startノードからgoalノードまでの最短経路
    """
    def __init__(self, graph, start):
        """
        graph: 隣接リストによるグラフ
        start: 始点のノード番号
        """
        self.g = graph
        self.V = len(graph)

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = [float('inf')] * self.V
        self.dist[start] = 0

        # 最短経路での1つ前のノードを保持するリスト
        self.prev = [None] * self.V

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (0, start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if dist_u > self.dist[u]:
                continue
            for v, weight in self.g[u]:
                alt = self.dist[u] + weight
                if alt < self.dist[v] :
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self):
        return self.dist

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


def main():
    N,Q,*m = map(int, read().split())
    AB = m[:2*(N-1)]
    PX = m[2*(N-1):]

    E = [[] for _ in range(N+1)]
    for a, b in zip(*[iter(AB)]*2):
        E[a].append([b, 0])

    myself = [0] * (N+1)
    for p, x in zip(*[iter(PX)]*2):
        if E[p]:
            for edge in E[p]:
                edge[1] += x
        myself[p] += x

    d = Dijkstra(E, 1)
    count = d.shortest_distance()

    ans = []
    for c, d in zip(count[1:], myself[1:]):
        ans.append(c + d)

    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,Q,*m = map(int, read().split())
    AB = m[:2*(N-1)]
    PX = m[2*(N-1):]

    E = [[] for _ in range(N+1)]
    for a, b in zip(*[iter(AB)]*2):
        E[a].append(b)

    cost = [0] * (N+1)
    for p, x in zip(*[iter(PX)]*2):
        cost[p] += x

    seen = [-1] * (N+1)
    seen[1] = cost[1]
    stack = [1]
    while stack:
        v = stack.pop()
        for e in E[v]:
            if seen[e] == -1:
                seen[e] = seen[v] + cost[e]
                stack.append(e)

    print(*seen[1:])
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

from heapq import heappop, heappush

class Dijkstra:
    """
    shortest_distance(goal): startノードからgoalノードまでの最短距離
    shortest_path(goal): startノードからgoalノードまでの最短経路
    """
    def __init__(self, graph, start):
        """
        graph: 隣接リストによるグラフ
        start: 始点のノード番号
        """
        self.g = graph
        self.V = len(graph)

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = [float('inf')] * self.V
        self.dist[start] = 0

        # 最短経路での1つ前のノードを保持するリスト
        self.prev = [None] * self.V

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (0, start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if dist_u > self.dist[u]:
                continue
            for v, weight in self.g[u]:
                alt = self.dist[u] + weight
                if alt < self.dist[v] :
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self):
        return self.dist

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


def main():
    N,Q,*m = map(int, read().split())
    AB = m[:2*(N-1)]
    PX = m[2*(N-1):]

    E = [[] for _ in range(N+1)]
    for a, b in zip(*[iter(AB)]*2):
        E[a].append([b, 0])

    myself = [0] * (N+1)
    for p, x in zip(*[iter(PX)]*2):
        if E[p]:
            for edge in E[p]:
                edge[1] += x
        myself[p] += x

    d = Dijkstra(E, 1)
    count = d.shortest_distance()

    for c, d in zip(count[1:], myself[1:]):
        print(c + d)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
a = []
b = []
for i in range(N-1):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
p = []
x = []
for i in range(Q):
    pp, xx = map(int, input().split())
    p.append(pp)
    x.append(xx)
    

def Main(N, Q, a, b, p, x):
    ans = [0]*N
    for i in range(Q):
        ans[p[i]-1] += x[i]
    for i in range(N-1):
        ans[b[i]-1] += ans[a[i]-1]
    return ans
        
         

out = Main(N, Q, a, b, p, x)
print(" ".join(map(str, out)))

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
a = []
b = []
for i in range(N-1):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
p = []
x = []
for i in range(Q):
    pp, xx = map(int, input().split())
    p.append(pp)
    x.append(xx)
    

def Main(N, Q, a, b, p, x):
    g = {}
    root_list = [0]*N
    for i in range(N):
        g[i+1] = []
    for i in range(N-1):
        g[a[i]].append(b[i])
        root_list[b[i]-1] = a[i]
    for i, e in enumerate(reversed(root_list)):
        if e > 0:
            g[e] += g[N-i]
    ans = [0]*N
    for i in range(Q):
        ans[p[i]-1] += x[i]
        for e in g[p[i]]:
            ans[e-1] += x[i]
    return ans
    

out = Main(N, Q, a, b, p, x)
print(" ".join(map(str, out)))

Submission status: Wrong Answer

Solution code:
from collections import OrderedDict
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
#初期データ、構造
N,Q = (int(x) for x in input().split())
connection ={i:set() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b)
    connection[b].add(a)
#point =OrderedDict({i:0 for i in range(1,N+1)})
point ={i:0 for i in range(1,N+1)}
for i in range(Q):
    p,x = (int(x) for x in input().split())
    point[p]=x

def DFS(now,prev = -1):
    for next in connection[now]:
        if next == prev:
            continue
        point[next] +=point[now] 
        DFS(next,now)

DFS(1)
print(*point.values())

Submission status: Wrong Answer

Solution code:
from collections import OrderedDict
import sys
sys.setrecursionlimit(10 ** 6)
#初期データ、構造
N,Q = (int(x) for x in input().split())
connection ={i:set() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b)
    connection[b].add(a)
#point =OrderedDict({i:0 for i in range(1,N+1)})
point ={i:0 for i in range(1,N+1)}
for i in range(Q):
    p,x = (int(x) for x in input().split())
    point[p]=x

def DFS(now,prev = -1):
    for next in connection[now]:
        if next == prev:
            continue
        point[next] +=point[now] 
        DFS(next,now)

DFS(1)
print(*point.values())

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
from collections import deque
s = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a = a-1
    b = b-1
    s[a].append(b)
    s[b].append(a)
count = [0 for i in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
ans = [-1 for i in range(n)]
ans[0] = count[0]
d = deque([(0,0)])
while d:
    print(d)
    u,v = d.popleft()
    ans[u] = v + count[u]
    for b in s[u]:
        if ans[b] == -1:
            d.append((b,ans[u]))
        else:
            continue
for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
from collections import deque
s = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a = a-1
    b = b-1
    s[a].append(b)
    s[b].append(a)
count = [0 for i in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
ans = [-1 for i in range(n)]
ans[0] = count[0]
d = deque([(0,0)])
while d:
    print(d)
    u,v = d.popleft()
    ans[u] = v + count[u]
    for b in s[u]:
        if ans[b] == -1:
            d.append((b,ans[u]))
        else:
            continue
for i in range(n):
    print(ans)

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
from collections import deque
s = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a = a-1
    b = b-1
    s[a].append(b)
    s[b].append(a)
count = [0 for i in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
ans = [-1 for i in range(n)]
ans[0] = count[0]
d = deque([(0,0)])
while d:
    print(d)
    u,v = d.popleft()
    ans[u] = v + count[u]
    for b in s[u]:
        if ans[b] == -1:
            d.append((b,ans[u]))
        else:
            continue
print(ans)

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
s = [0 for i in range(n-1)]
for i in range(n-1):
    a,b = map(int,input().split())
    s[i] = [a,b]
count = [0 for i in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
ans = [-1 for i in range(n)]
ans[0] = count[0]
for i in range(n-1):
    if ans[s[i][1]-1] == -1:
        ans[s[i][1]-1] = ans[s[i][0]-1] + count[s[i][1]-1]
    else:
        ans[s[i][0]-1] = ans[s[i][1]-1] + count[s[i][0]-1]
for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
s = [0 for i in range(n-1)]
for i in range(n-1):
    a,b = map(int,input().split())
    s[i] = [a,b]
s.sort()
count = [0 for i in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
ans = [-1 for i in range(n)]
ans[0] = count[0]
for i in range(n-1):
    if ans[s[i][1]-1] == -1:
        ans[s[i][1]-1] = ans[s[i][0]-1] + count[s[i][1]-1]
    else:
        ans[s[i][0]-1] = ans[s[i][1]-1] + count[s[i][0]-1]
for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
s = [0 for i in range(n-1)]
for i in range(n-1):
    a,b = map(int,input().split())
    s[i] = [a,b]
s.sort()
ans = [-1 for i in range(n)]
for i in range(n-1):
    ans[s[i][1]-1] = s[i][0]-1
count = [0 for i in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
ans1 = [0 for i in range(n)]
ans1[0] = count[0]
for i in range(1,n):
    ans1[i] = ans1[ans[i]] + count[i]
for i in range(n):
    print(ans1[i])

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
s = [0 for i in range(n-1)]
for i in range(n-1):
    a,b = map(int,input().split())
    s[i] = [a,b]
s.sort()
ans = [-1 for i in range(n)]
for i in range(n-1):
    ans[s[i][1]-1] = s[i][0]-1
count = [0 for i in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
ans1 = [0 for i in range(n)]
for i in range(n):
    ans1[i] = ans1[ans[i]] + count[i]
for i in range(n):
    print(ans1[i])

Submission status: Wrong Answer

Solution code:
n,q = list(map(int, input().split()))
li = [[0]*n for i in range(n)]
v  = [0]*n



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

#print(li)

def dfs(now_node, value):
    if checked_li[now_node-1]==1:#探索済み
        return 
    v[now_node-1]+=value
    checked_li[now_node-1]=1
    for i in range(len(li[now_node-1])):
        if li[now_node-1][i]==1:
            dfs(i+1, value)

for i in range(q):
    checked_li=[0]*n
    p, x = list(map(int, input().split()))
    dfs(p, x)

for i in v:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q = map(int,input().split())
adjacent = dict.fromkeys(list(range(1,N+1)),[])
counter = dict.fromkeys(list(range(1,N+1)),0)
for i in range(N-1):
    a,b = map(int,input().split())
    adjacent[a].append(b)
    adjacent[b].append(a)
for j in range(Q):
    p,q = map(int,input().split())
    counter[p] += q
start = 1
frontier = deque([start])
visited = [start]
while len(frontier) > 0:
    x = frontier.pop()
    for y in adjacent[x]:
        if y not in visited:
            frontier.append(y)
            counter[y] += counter[x]
            visited.append(y)
value = [counter[i] for i in range(1,N+1)]
print(*value)