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: Accepted

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)
    graph[b-1].append(a-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: Accepted

Solution code:
from collections import deque
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)]

adlist=[]
finish=set()

point=[0]*n
for h in range(n):    
    adlist.append([])
for j in range(n-1):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
for i in range(q):
    point[px[i][0]-1]+=px[i][1]
#print(point)
deq=deque()
deq.append(1)


while deq:
    now=deq.pop()
       # print(now)
    finish.add(now)
    for i in range(len(adlist[now-1])):
        #print(adlist[now-1][i],now)
        if adlist[now-1][i] not in finish:
            point[adlist[now-1][i]-1]+=point[now-1]
            deq.append(adlist[now-1][i])

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

Submission status: Accepted

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)
    graph[b-1].append(a-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: Accepted

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

N,Q = map(int,readline().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:N+N-2])
PX = iter(ABPX[N+N-2:])

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

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

stack = [1]

parent = [0] * (N+1)
while stack:
    x = stack.pop()
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        val[y] += val[x]

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

Submission status: Accepted

Solution code:
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G
from collections import deque
def dfs(G,point,v,p):
    q=deque()
    q.append((v,p,0))

    while q:
        V,P,S=q.pop()
        if S==0:
            for new_v in G[V-1]:
                if new_v==P:continue
                point[new_v - 1] += point[V - 1]
                q.append((new_v,V,0))

n, q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n - 1)]
G = Graph(ab)

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

dfs(G, point, 1, -1)
print(*point)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
graph=[[] for _ in range(N+1)]
for _ in range(N-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
data=[0 for i in range(N+1)]
visited=[False for i in range(N+1)]
for i in range(Q):
    p,x=map(int,input().split())
    data[p]+=x
    
from collections import deque
d=deque()
e=deque()
visited[1]=True
d.append(1)
while d:
    while d:
        x=d.popleft()
        adder=data[x]
        for node in graph[x]:
            if visited[node]==False:
                visited[node]=True
                data[node]+=adder
                e.append(node)
            else:
                pass
    if e:
        d=e
        e=deque()
print(*data[1:])

Submission status: Accepted

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()
    visited[q] = True

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

print(*ans)

Submission status: Accepted

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)
        tree[b].append(a)
    
    node = [0] * n
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        node[p] += x
    
    ans = [0] * n
    visited = [False] * n

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

        now_score += node[now_node]

        ans[now_node] = now_score

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x:int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)

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

from collections import deque
st = deque([[0, points[0]]])
result = ['0'] * N
visited = [0] * N
visited[0] = 1
while st:
    idx, count = st.pop()
    result[idx] = str(count)
    for ni in G[idx]:
        if visited[ni] != 1:
            visited[ni] = 1
            st.append([ni, count+points[ni]])

print(" ".join(result))

Submission status: Accepted

Solution code:
#/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

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

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

adj = [[] for _ in range(N)]

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

def dfs(node, parent):
    for child in adj[node]:
        if child == parent: continue
        values[child] += values[node]
        dfs(child, node)

dfs(0, -1)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q =map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
 
g = [[] for _ in range(N+1)]
for a, b in ab:
    g[b].append(a)
    g[a].append(b)
cnt = [0]*(N+1)
 
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x
 
temp = [1]
visited = [0]*(N+1)
visited[1] = 1
 
while temp:
    q = temp.pop()   
    for i in g[q]:
        if visited[i] == 0:
            temp.append(i)
            visited[i] = 1
            cnt[i] += cnt[q]
print(*cnt[1:])

Submission status: Accepted

Solution code:
# 私はDFSを書けるようになるまで諦めない！！
n, q = map(int, input().split())
edges = [[]for _ in range(n)]
count = [0]*n
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)
for _ in range(q):
    p, x = map(int, input().split())
    count[p-1] += x

stack = [0]
INF = 10**18
counter = [INF]*n
counter[0] = count[0]
while stack:
    v1 = stack.pop()
    for v2 in edges[v1]:
        if counter[v2] != INF:
            continue
        counter[v2] = counter[v1] + count[v2]
        stack.append(v2)

print(*counter)

Submission status: Accepted

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

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

g = {}
for a, b in ab:
    if a in g: g[a].append(b)
    else: g[a] = [b]
    if b in g: g[b].append(a)
    else: g[b] = [a]

cnt = [0]*(N+1)

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

temp = [1]
visited = [0]*(N+1)
visited[1] = 1

while temp:
    q = temp.pop()   
    for i in g[q]:
        if visited[i] == 0:
            temp.append(i)
            visited[i] = 1
            cnt[i] += cnt[q]
print(*cnt[1:])

Submission status: Accepted

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

g = [set() for _ in range(N+1)]
for a, b in ab:
    g[b].add(a)
    g[a].add(b)
cnt = [0]*(N+1)

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

temp = [1]
visited = [0]*(N+1)
visited[1] = 1

while temp:
    q = temp.pop()   
    for i in g[q]:
        if visited[i] == 0:
            temp.append(i)
            visited[i] = 1
            cnt[i] += cnt[q]
print(*cnt[1:])

Submission status: Accepted

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

g = [[] for _ in range(N+1)]
for a, b in ab:
    g[b].append(a)
    g[a].append(b)
cnt = [0]*(N+1)

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

temp = [1]
visited = [0]*(N+1)
visited[1] = 1

while temp:
    q = temp.pop()   
    for i in g[q]:
        if visited[i] == 0:
            temp.append(i)
            visited[i] = 1
            cnt[i] += cnt[q]
print(*cnt[1:])

Submission status: Accepted

Solution code:
import sys
import queue

input = sys.stdin.readline

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        edges[a].append(b)
        edges[b].append(a)

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

    def dfs(cur, par):
        for nex in edges[cur]:
            if nex == par:
                continue
            counter[nex] += counter[cur]
            dfs(nex, cur)

    dfs(0, -1)
    print(*counter, sep=" ")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
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):
    nex=g[i]
    for d in nex:
        if d==j: continue
        #print(d)
        lis[d]+=lis[i]
        dfs(d,i)

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

Submission status: Accepted

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(a)
  
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: Accepted

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)
    path[b].append(a)

ans = [0] * (n + 1)

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

alr = [0] * (n + 1)
alr[1] = 1

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

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
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(1,N):
    a,b = (int(x) for x in input().split())
    connection[a].add(b)
    connection[b].add(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

#深さ優先探索
que =deque()
que.append(1)
passed =set()
while que:
    now =que.pop()
    passed.add(now)
    for next in connection[now]:
        if next not in passed:
            point[next] +=point[now]
            que.append(next)
            #print(next,end=" ")
print(*point.values())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from collections import deque

def main():
    n, q = map(int, input().split())
    link = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        link[a].append(b)
        link[b].append(a)
    manip = [list(map(int, input().split())) for _ in range(q)]

    cnt = [0 for _ in range(n+1)]
    for m in manip:
        node, x = m
        cnt[node] += x

    parent = [0 for _ in range(n+1)]
    unchecked = [True for _ in range(n+1)]
    unchecked[1] = False
    que = deque([1])
    while que:
        node = que.pop()
        for l in link[node]:
            if unchecked[l]:
                unchecked[l] = False
                cnt[l] += cnt[node]
                que.append(l)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N, Q = map(int, input().split())
G = defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  # 0-indexed
    G[a].append(b)
    G[b].append(a)

# print('G', G)

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


def dfs(v, p):
    if p != -1:
        V[v] += V[p]
    for idx in G[v]:
        if idx == p:
            continue
        dfs(idx, v)


dfs(0, -1)

# print('V', V)

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

Submission status: Accepted

Solution code:
def input_undirected_graph(V: int, E: int, origin: int = 1):
    graph = [list() for _ in range(V)]
    for i in range(E):
        u, v = [int(x) for x in input().split()]
        u -= origin
        v -= origin
        graph[u].append(v)
        graph[v].append(u)
    return graph


def main():
    N, Q = [int(x) for x in input().split()]
    graph = input_undirected_graph(N, N-1)

    vals = [0] * N
    for _ in range(Q):
        p, x = [int(x) for x in input().split()]
        vals[p-1] += x
    
    ans = [0] * N
    stack = [(0, -1, 0)]  # node, par, val
    while stack:
        node, par, val = stack.pop()
        ans[node] += vals[node] + val

        for child in graph[node]:
            if child == par:
                continue
            stack.append((child, node, ans[node]))

    for i in range(N):
        print(ans[i])
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Submission status: Accepted

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

N , Q = map(int,readline().rstrip().split())
G = [[] for _ in range(N)]
for n in range(N-1):
    a , b = map(int,readline().rstrip().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
query = [0] * N
for q in range(Q):
    p , x = map(int,readline().rstrip().split())
    query[p-1] += x
counter = [0] * N 
visit = [0] * N

def dfs(root , x ):
    if visit[root] == 0:
        visit[root] = 1
        x += query[root]
        counter[root] += x
    else:
        return 0
    
    for g in G[root]:
        dfs( g, x )

    return 0

def solve():
    dfs(0 , 0)
    [print(c , end = " " ) for c in counter]
    print("")

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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)

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

#BFSで親のカウンターを子に継がせる
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in tree[v]:
        if dist[w] > -1:
            continue
        que.append(w)
        dist[w]=d+1
        ans[w]+=ans[v]

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

N, Q = map(int, input().split())
Tree = [[] for _ in range(N)]
Query = [0] * N
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Tree[a].append(b)
    Tree[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    Query[p] += x
Ans = [-1] * N
A = deque()
A.append(0)
Ans[0] = Query[0]
while len(A) > 0:
    now = A.pop()
    num = Ans[now]
    for next in Tree[now]:
        if Ans[next] >= 0:
            continue
        else:
            Ans[next] = num + Query[next]
            A.append(next)

ans = ''
for aa in Ans:
    ans += str(aa) + ' '
ans = ans[:-1]
print(ans)

Submission status: Accepted

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

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

from collections import deque
graph = {i: deque() for i in range(1, N+1)}
for i in range(1, N):
    graph[a[i]].append(b[i])
    graph[b[i]].append(a[i])


def dfs(v):
    seen = [0]*(N+1)
    stack = []
    seen[v] = 1
    stack.append(v)
    while stack:
        s = stack[-1]
        if not graph[s]:
            stack.pop()
            continue
        g = graph[s].popleft()
        if seen[g]:
            continue
        seen[g] = 1
        stack.append(g)
        counter[g] += counter[s]

dfs(v=1)
print(*counter[1:])

Submission status: Accepted

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

def main():
    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)
        way[b-1].append(a-1)
    add = [0]*n
    for i in range(q):
        a,b = map(int, input().split())
        add[a-1] += b
    ans = [-1]*n
    ans[0] = add[0]
    
    stack = [(0,add[0])]
    while stack:
        a,b = stack.pop()
        for i in range(len(way[a])):
            if (ans[way[a][i]]==-1):
                stack.append((way[a][i],b+add[way[a][i]]))
                ans[way[a][i]] = b+add[way[a][i]]
    print(*ans)
    
if __name__=="__main__":
    main()

Submission status: Accepted

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

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)
    way[b-1].append(a-1)
add = [0]*n
for i in range(q):
    a,b = map(int, input().split())
    add[a-1] += b
ans = [-1]*n
ans[0] = add[0]
    
stack = [(0,add[0])]
while stack:
    a,b = stack.pop()
    for i in range(len(way[a])):
        if (ans[way[a][i]]==-1):
            stack.append((way[a][i],b+add[way[a][i]]))
            ans[way[a][i]] = b+add[way[a][i]]
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
output = sys.stdout.writelines


def bfs(G, v, p, counter):
    queue = deque([(v, p)])
    while queue:
        v, p = queue.popleft()
        for c in G[v]:
            if c == p:
                continue
            counter[c] += counter[v]
            queue.append((c, v))


def main():
    N, Q = map(int, input().split())

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

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

    bfs(G, 1, -1, counter)

    output([" ".join(map(str, counter[1:])), "\n"])


if __name__ == "__main__":
    main()

Submission status: Accepted

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)
    way[b-1].append(a-1)
add = [0]*n
for i in range(q):
    a,b = map(int, input().split())
    add[a-1] += b
ans = [-1]*n
ans[0] = add[0]
    
stack = [(0,add[0])]
while stack:
    a,b = stack.pop()
    for i in range(len(way[a])):
        if (ans[way[a][i]]==-1):
            stack.append((way[a][i],b+add[way[a][i]]))
            ans[way[a][i]] = b+add[way[a][i]]
print(*ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
N,Q=map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	#隣接リスト
for _ in range(N-1):
	u,v=map(int, sys.stdin.readline().split())
	al[u].append(v)
	al[v].append(u)

increment=[ 0 for _ in range(N+1) ]
for _ in range(Q):
    p,x=map(int, sys.stdin.readline().split())
    increment[p]+=x

#BFS
visit=[ 0 for _ in range(N+1) ] #訪問した頂点
q=deque()
q.append((0,1)) #親,自分
visit[1]=1

score=[ 0 for _ in range(N+1) ] #各頂点のカウンターの値を記録
point=0

while q:
    par,cur=q.popleft()
    score[cur]=score[par]+increment[cur]    #自分のカウンターの値は、親の値+自分のところでの増加分
    for to in al[cur]:
        if visit[to]==0:
            visit[to]=1
            q.append((cur,to))

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

Submission status: Accepted

Solution code:
import sys
from collections import deque


def bfs(G, v, p, counter):
    queue = deque([(v, p)])
    while queue:
        v, p = queue.popleft()
        for c in G[v]:
            if c == p:
                continue
            counter[c] += counter[v]
            queue.append((c, v))


def main():
    input = sys.stdin.readline

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

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

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

    bfs(G, 1, -1, counter)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(G, v, p, counter):
    queue = deque([(v, p)])
    while queue:
        v, p = queue.popleft()
        for c in G[v]:
            if c == p:
                continue
            counter[c] += counter[v]
            queue.append((c, v))


def main():
    N, Q = map(int, input().split())

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

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

    bfs(G, 1, -1, counter)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(G, v, p, counter):
    queue = deque([(v, p)])
    while queue:
        v, p = queue.popleft()
        for c in G[v]:
            if c == p:
                continue
            counter[c] += counter[v]
            queue.append((c, v))


def main():
    N, Q = map(int, input().split())

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

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

    bfs(G, 0, -1, counter)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def dfs(G, v, p, counter):
    stack = deque([(v, p)])
    while stack:
        v, p = stack.pop()
        for c in G[v]:
            if c == p:
                continue
            counter[c] += counter[v]
            stack.append((c, v))


def main():
    N, Q = map(int, input().split())

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

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

    dfs(G, 0, -1, counter)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def dfs(G, v, p, counter):
    stack = deque([(v, p)])
    while stack:
        v, p = stack.pop()
        counter_v = counter[v]
        for c in G[v]:
            if c == p:
                continue
            counter[c] += counter_v
            stack.append((c, v))


def main():
    N, Q = map(int, input().split())

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

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

    dfs(G, 0, -1, counter)

    print(*counter)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def dfs(G, v, p, counter):
    stack = deque([(v, p)])
    while stack:
        v, p = stack.pop()
        for c in G[v]:
            if c == p:
                continue
            counter[c] += counter[v]
            stack.append((c, v))


def main():
    N, Q = map(int, input().split())

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

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

    dfs(G, 0, -1, counter)

    print(*counter)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(G, v, p, counter):
    queue = deque([(v, p)])
    while queue:
        v, p = queue.popleft()
        for c in G[v]:
            if c == p:
                continue
            counter[c] += counter[v]
            queue.append((c, v))


def main():
    N, Q = map(int, input().split())

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

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

    bfs(G, 0, -1, counter)

    print(*counter)


if __name__ == "__main__":
    main()