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())
tree = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

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

from collections import deque

todo = deque([(1,0)])
while len(todo) > 0:
    x,parent = todo.pop()
    ans[x] += ans[parent]
    for next in tree[x]:
        if next == parent:
            continue
        else:
            todo.append((next,x))
            
answer = ' '.join(map(str,ans[1:]))
print(answer)

Submission status: Accepted

Solution code:
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().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 = [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: Accepted

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

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

from collections import deque

count = [0]*N

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

queue = deque([0])
checked  = [0]*N
while queue:
    v = queue.pop()
    checked[v] = 1
    x = count[v]
    Vs = query[v]
    for i in Vs:
        if checked[i]:
            continue
        count[i] += x
        queue.append(i)
    
print(*count)

Submission status: Accepted

Solution code:
from collections import deque
n,q = map(int,input().split())
c = [[] for _ in range(n)]
for i in range(n-1):
    A,B = map(int,input().split())
    c[A-1].append(B)
    c[B-1].append(A)
z = [0] * n
for i in range(q):
    P,X = map(int,input().split())
    z[P - 1] += X


d = [-1] * n
d[0] = 0
q = deque([])
q.append(1)
while(q):
    tp = q.popleft()
    td = d[tp - 1]
    for n2 in c[tp - 1]:
        if(d[n2 - 1] == -1):
            d[n2 - 1] = td + 1
            z[n2 - 1] += z[tp - 1]
            q.append(n2)

print(*z)

Submission status: Accepted

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

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

def bfs(x,x_list):
  qu=deque([])
  qu.append(0)
  qu.append(x)
  node_number=1
  while qu:
    pre=qu.popleft()
    node_number = qu.popleft()
    nodes = edge[node_number]
    for i in nodes:
      if pre != i:
        qu.append(node_number)
        qu.append(i)
        x_list[i]+=x_list[node_number]
      else:continue
  return x_list
answer=bfs(1,x_list)[1:]
print(*answer)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
counter=[0]*(n)
edge=[[] for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a].append(b)
  edge[b].append(a)
  
for j in range(q):
  p,x=map(int,input().split())
  counter[p-1]+=x

def bfs(x,counter):
  qu=deque([])
  qu.append(x)
  qu.append(0)
  while qu:
    now=qu.popleft()
    pre=qu.popleft()
    if now!=1:
      counter[now-1]+=counter[pre-1]
    for i in edge[now]:
      if i!=pre:
        qu.append(i)
        qu.append(now)#あとであとのノードなるもの
      else:continue
  return counter
bfs(1,counter)
print(*counter)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N, Q = map(int, input().split())
    g = [[] for _ in range(N)]

    # for storing the value of the each node
    cnt = [0]*N

    # for DFS
    stack = deque()
    stack.append(0)
    seen = [0] * N

    # store the structure of the graph
    for i in range(N-1):
        a, b = map(int, input().split())
        g[b-1].append(a-1)
        g[a-1].append(b-1)

    # add values to parent nodes
    for i in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x

    # DFS
    while len(stack):
        idx = stack.pop()
        seen[idx] += 1
        for c in g[idx]:
            if seen[c]:
                continue
            cnt[c] += cnt[idx]
            stack.append(c)

    print(*cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from _collections import deque
N, Q = map(int, input().split())
graph = [[] for _ in range(N+1)]
for i in range(N-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

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

stack = deque()
stack.append(1)
score = 0
score_array = [0]*(N+1)
is_checked = [0]*(N+1)
#print(graph)
while stack:
    node = stack.pop()
    is_checked[node] = 1

    #print("node=" + str(node))
    score_array[node] += points[node]
    #print("score=" + str(score_array[node]))
    for goto in graph[node]:
        if not is_checked[goto]:
            #print("goto=" + str(goto))
            stack.append(goto)
            score_array[goto] += score_array[node]

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

Submission status: Accepted

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

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

value = [0] * (N+1)
for p,x in px:
    value[p] += x

from collections import deque
todo = deque([(1,0)])
while len(todo) > 0:
    x,parent = todo.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        todo.append((y,x))

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

Submission status: Accepted

Solution code:
#@hoshikawa1309
# dfsを用いて累積和を計算する
import sys
sys.setrecursionlimit(10 ** 6)
def input():#入力方法にも注意
    return sys.stdin.readline()[:-1]
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ 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
# 初期状態だと前の値がないためデフォルト引数に-1を代入
def dfs(now , prev = -1):
    for next in graph[now]:#いま見ているノードから行けるノードをチェック
        # 次のノードが前に参照した値の時はcontinue、逆走防止
        if next == prev:
            continue
        # 現在の値を次のポイントに加算することで累積和をとる
        point[next] += point[now]#実質的な処理は、これだけ
        # 次のノードと現在のノードを引数にdfsを継続する
        dfs(next , now)
dfs(0)
print(*point)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
import sys
def input():
    return sys.stdin.readline()[:-1]
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
#print(graph)
for _ in range(Q):
    a , b = map(int,input().split())
    a = a - 1
    point[a] += b
# dfsを用いて累積和を計算する
# 初期状態だと前の値がないためデフォルト引数に-1を代入
def dfs(now , prev = -1):
    for next in graph[now]:
        # 次のノードが前に参照した値の時はcontinue
        if next == prev:
            continue
        # 現在の値を次のポイントに加算することで累積和をとる
        point[next] += point[now]
        # 次のノードと現在のノードを引数にdfsを継続する
        dfs(next , now)

dfs(0)
print(*point)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
# 遅延評価で加えてあげるだけ
 
N,Q = map(int,input().split())
ab = [[int(x) for x in input().split()] for _ in range(N-1)]
px = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in px:
    value[p] += x
    
q = [(1,0)]
while q:
    x,parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y,x))
 
answer = ' '.join(map(str,value[1:]))
print(answer)

Submission status: Accepted

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

graph = [[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in px:
    value[p] += x
    
q = [(1,0)]
while q:
    x,parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y,x))
 
answer = ' '.join(map(str,value[1:]))
print(answer)

Submission status: Accepted

Solution code:
from collections import deque

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

g = [[] for _ 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)

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

que = deque([])
que.append(0)
s = [0] * N
while que:
    t = que.popleft()
    s[t] = 1
    for e in g[t]:
        if s[e] == 1: continue
        cnt[e] += cnt[t]
        que.append(e)

print(*cnt)

Submission status: Accepted

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

def abc138_d():
    N, _ = map(int, readline().strip().split())
    input_data = list(map(int, read().split()))
    AB = iter(input_data[:N+N-2])
    PX = iter(input_data[N+N-2:])

    # 隣接リスト作成
    graph = [[] for _ in range(N+1)]
    for a, b in zip(AB, AB):
        graph[a].append(b)
        graph[b].append(a)

    # クエリをもとにスコア加算　※頂点pだけに加算し、子へは加算しない
    val = [0] * (N+1)
    for p, x in zip(PX, PX):
        val[p] += x

    # DFSで根元から順に足していく
    stack = [1]
    visited = [False] * (N+1)
    visited[1] = True
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if visited[y]: continue
            stack.append(y)
            visited[y] = True
            val[y] += val[x]

    print(*val[1:], sep=' ')

abc138_d()

Submission status: Accepted

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

def abc138_d():
    N, _ = map(int, readline().strip().split())
    input_data = [tuple(map(int, ln.strip().split())) for ln in readlines()]

    # 隣接リスト作成
    graph = [[] for _ in range(N+1)]
    for a, b in input_data[:N-1]:
        graph[a].append(b)
        graph[b].append(a)

    # クエリをもとにスコア加算　※頂点pだけに加算し、子へは加算しない
    val = [0] * (N+1)
    for p, x in input_data[N-1:]:
        val[p] += x

    # DFSで根元から順に足していく
    stack = [1]
    visited = [False] * (N+1)
    visited[1] = True
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if visited[y]: continue
            stack.append(y)
            visited[y] = True
            val[y] += val[x]

    print(*val[1:], sep=' ')

abc138_d()

Submission status: Accepted

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

def abc138_d():
    N, _ = map(int, readline().strip().split())
    input_data = [tuple(map(int, ln.strip().split())) for ln in readlines()]

    # 隣接リスト作成
    graph = [[] for _ in range(N+1)]
    for a, b in input_data[:N-1]:
        graph[a].append(b)
        graph[b].append(a)

    # クエリをもとにスコア加算　※頂点pだけに加算し、子へは加算しない
    val = [0] * (N+1)
    for p, x in input_data[N-1:]:
        val[p] += x

    # DFSで根元から順に足していく
    stack = [1]
    visited =set([1])
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if y in visited: continue
            stack.append(y)
            visited.add(y)
            val[y] += val[x]

    print(*val[1:], sep=' ')

abc138_d()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

input=lambda: sys.stdin.readline().rstrip() 

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

lv =[[] for _ in range(n)]
ans=[0] * (n)

def dfs(v,p=-1):
    for u in lv[v]:
        if u == p: continue
        ans[u] += ans[v]
        dfs(u,v)

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

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

dfs(0)

print(*ans)
# for i in ans:print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

input=sys.stdin.readline      

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

lv =[[] for _ in range(n)]
ans=[0] * (n)

def dfs(v,p=-1):
    for u in lv[v]:
        if u == p: continue
        ans[u] += ans[v]
        dfs(u,v)

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

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

dfs(0)

print(*ans)
# for i in ans:print(i)

Submission status: Accepted

Solution code:
I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################
 
 
from sys import stdin,setrecursionlimit
#from copy import deepcopy
 
setrecursionlimit(10**6)
input=stdin.readline
 
def dfs(p,father=-1):
    for i in tree[p]:
        if i == father:
            continue
        counter[i]+=counter[p]
        dfs(i,p)
 
n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
 
for i in range(q):
    p,x = I0()
    counter[p-1]+=x
    
 
dfs(0)
 
print(*counter)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from copy import deepcopy
from collections import deque
def main():
    N, Q = map(int, readline().split())
    m = map(int, read().split())
    n = deepcopy(m)
    to = [[] for _ in range(N)]
    for a, b in [(a-1, b-1) for a, b in zip(m, m)][:N-1]:
        to[a].append(b)
        to[b].append(a)
    score = [0 for _ in range(N)]
    for p, x in [(p-1, x) for p, x in zip(n, n)][N-1:]:
        score[p] += x

    dq = deque()
    dq.append(0)
    done = [0 for _ in range(N)]
    done[0] = 1
    while len(dq)>0:
        node = dq.popleft()
        for nx in to[node]: 
            if done[nx] == 1:
                continue 
            done[nx] = 1
            score[nx] += score[node]
            dq.append(nx)
    for i in score:
        print(i, end=' ')
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#ika tako
import sys
n, q = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
for line in lines[:n - 1]:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
adds = [0] * n
for line in lines[n - 1:]:
    p, x = map(int, line.split())
    p -= 1
    adds[p] += x
ans = [-1] * n
q = [(0, 0)]
while q:
    v, a = q.pop()
    a += adds[v]
    ans[v] = a
    for u in links[v]:
        if ans[u] == -1:
            q.append((u, a))
print(*ans)

Submission status: Accepted

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

from collections import deque
d = deque()
d.append(0)
visited = set([])

while d:
    x = d.popleft()
    for child in graph[x]:
        if child not in visited:
            point_list[child] += point_list[x]
            d.append(child)
        visited.add(x)
print(*point_list)

Submission status: Accepted

Solution code:
import queue
import sys
def input(): return sys.stdin.readline().rstrip()

def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0] * (n + 1)
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    que = queue.Queue()
    visited = [False] * (n+1)

    def bfs(root, base):
        base += counter[root]
        visited[root] = True
        for e in tree[root]:
            if visited[e]:
                continue
            que.put(e)
            counter[e] += base

        while not que.empty():
            x = que.get()
            point = counter[x]
            visited[x] = True
            for e in tree[x]:
                if visited[e]:
                    continue
                que.put(e)
                counter[e] += point

    bfs(1, 0)
    print(*counter[1:])
    return


m()

Submission status: Accepted

Solution code:
from collections import deque
 
N, Q = map(int,input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
P = [0] * N
for _ in range(Q):
    p,q = map(int,input().split())
    P[p-1] += q
 
stack = deque([0])
parent = [-1] * N

while stack:
    v = stack[-1]
    if G[v]:
        w = G[v].pop()
        if not parent[v] == w:
            parent[w] = v
            P[w] += P[v]
            stack.append(w)
    else:
        stack.pop()

print(*P)

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)

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

se = set([1])
stack = [1]
while stack:
    # print(C)
    x = stack.pop()
    for y in graph[x]:
        if y in se:
            continue
        stack.append(y)
        se.add(y)
        # 親x, 子y
        C[y] += C[x]

print(' '.join(str(i) for i in C[1:]))

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)

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

se = set([1])
stack = [1]
while stack:
    # print(C)
    x = stack.pop()
    for y in graph[x]:
        if y in se:
            continue
        stack.append(y)
        se.add(y)
        # 親x, 子y
        C[y] += C[x]

print(' '.join(str(i) for i in C[1:]))

Submission status: Accepted

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

n, q = map(int, input().split())
neighbor = [[] for _ in range(n)]
point = [0]*n

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

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


def dfs(now, past):
    for nv in neighbor[now]:
        if nv == past:
            continue
        point[nv] += point[now]
        dfs(nv, now)


dfs(0, -1)


print(*point)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline 
sys.setrecursionlimit(10 ** 6) 
N,Q = map(int, input().split())

tree = [[] for _ 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)

ans = [0] * N

for i in range(Q):
  p,x = map(int, input().split())
  ans[p - 1] += x
  
def dfs(cur, par):
  for chl in tree[cur]:
    if chl == par:
      continue
    ans[chl] += ans[cur]
    dfs(chl,cur)

dfs(0, -1)

print(*ans)

Submission status: Accepted

Solution code:
from subprocess import *
call(('pypy3','-c',"""
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n,q=map(int,input().split())
    P=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        P[a-1].append(b-1)
        P[b-1].append(a-1)
    X=[0]*n
    for i in range(q):
        p,x=map(int,input().split())
        X[p-1]+=x
    deq=deque([0])
    visited=[False]*n 
    while deq:
        node=deq.popleft()
        if not(visited[node]):
            visited[node]=True
            for p in P[node]:
                if not(visited[p]):
                    X[p]+=X[node]
                    deq.append(p)
    print(*X)

if __name__=='__main__':
    main()
"""))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

# グラフの作成(無向グラフでは#を消す)
n, q = map(int, input().split())
ans = [0]*n
ki = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)
for i in range(q):
    p, q = map(int, input().split())
    ans[p-1] += q

# 深さ優先探索
stack = deque([0])
visited = [-1]*n
while stack:
    ne = stack.popleft()
    if visited[ne] == -1:
        visited[ne] = 1
        for j in ki[ne]:
            if visited[j] == -1:
                ans[j] += ans[ne]
                stack.append(j)
                
print(*ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n,q=map(int,input().split())
    P=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        P[a-1].append(b-1)
        P[b-1].append(a-1)
    X=[0]*n
    for i in range(q):
        p,x=map(int,input().split())
        X[p-1]+=x
    deq=deque([0])
    visited=[False]*n 
    while deq:
        node=deq.popleft()
        if not(visited[node]):
            visited[node]=True
            for p in P[node]:
                if not(visited[p]):
                    X[p]+=X[node]
                    deq.append(p)
    print(*X)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,Q=map(int,input().split())
ans=[0]*N
ki=[[] for _ in range(N)]
for i in range(N-1):
 a,b=map(int,input().split())
 ki[a-1].append(b-1)
 ki[b-1].append(a-1)
for i in range(Q):
 p,q=map(int,input().split())
 ans[p-1]+=q
# dfs
from collections import deque
stack =deque([0])
visited = ["False"] * N
while stack:
 ne = stack.popleft()
 if visited[ne] == "False":
  visited[ne] = "True"
  for j in ki[ne]:
   if visited[j] == "False":
    ans[j]+=ans[ne]
    stack.append(j)
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
N, Q = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [b]
  graph[b] += [a]

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

def dfs(u, pre):
  for v in graph[u]:
    if v != pre:
      cnt[v] += cnt[u]
      dfs(v, u)
  return

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

Submission status: Accepted

Solution code:
# D - Ki
from collections import deque

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

# 各頂点に得点を持たせておく
point = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    point[p] += x

ans = [0] * N

d = deque()
d.append((0,0,0))

while len(d)>0:
    v = d.popleft()
    ans[v[0]] += v[2] + point[v[0]]
    for gi in g[v[0]]:
        if gi!=v[1]:
            d.append((gi, v[0], ans[v[0]]))

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline  # NOQA
sys.setrecursionlimit(10 ** 7)  # NOQA

from collections import deque


def dfs(G, v, p, counter):
    """G: graph, v: vertex, p: parent"""
    parent = [-1] * len(G)
    stack = deque([v])
    while stack:
        v = stack.pop()
        for c in G[v]:
            if c == parent[v]:
                continue
            parent[c] = v
            stack.append(c)
            counter[c] += counter[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
input = sys.stdin.readline  # NOQA
sys.setrecursionlimit(10 ** 7)  # NOQA


def dfs(G, v, p, counter):
    """G: graph, v: vertex, p: parent"""
    # Loop for each child
    counter_v = counter[v]
    for c in G[v]:
        if c == p:
            continue  # Avoid multiple access to parent
        counter[c] += counter_v
        dfs(G, c, v, counter)


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 i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        counter[p] += x

    dfs(G, 0, -1, counter)
    # print(*counter)
    print(" ".join(map(str, counter)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline  # NOQA
sys.setrecursionlimit(10 ** 7)  # NOQA


def dfs(G, v, p, counter):
    """G: graph, v: vertex, p: parent"""
    # Loop for each child
    counter_v = counter[v]
    for c in G[v]:
        if c == p:
            continue  # Avoid multiple access to parent
        counter[c] += counter_v
        dfs(G, c, v, counter)


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)
    print(" ".join(map(str, counter)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline  # NOQA
sys.setrecursionlimit(10 ** 7)  # NOQA


def dfs(G, v, p, counter):
    """G: graph, v: vertex, p: parent"""
    # Loop for each child
    # counter_v = counter[v]
    for c in G[v]:
        if c == p:
            continue  # Avoid multiple access to parent
        # counter[c] += counter_v
        counter[c] += counter[v]
        dfs(G, c, v, counter)


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
input = sys.stdin.readline  # NOQA
sys.setrecursionlimit(10 ** 7)  # NOQA


def dfs(G, v, p, counter):
    """G: graph, v: vertex, p: parent"""
    # Loop for each child
    counter_v = counter[v]
    for c in G[v]:
        if c == p:
            continue  # Avoid multiple access to parent
        counter[c] += counter_v
        dfs(G, c, v, counter)


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:
from collections import deque
N,Q=map(int,input().split())
tr=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    tr[a-1].append(b-1)
    tr[b-1].append(a-1)
k=[0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    k[p-1]+=x
q=deque([0])
v=[True]*N
while q:
    t=q.popleft()
    if v[t]:
        v[t]=False
        for j in tr[t]:
            if v[j]:
                k[j]+=k[t]
                q.append(j)
print(*k)