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:
import collections

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

tree = [[] for _ in range(n)]
edge = collections.deque(edge)
while len(edge) != 0:
    a, b = edge.popleft()
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)

que = collections.deque([0])
flag = [False] * n
while len(que) != 0:
    i = que.popleft()
    flag[i] = True
    for j in tree[i]:
        if flag[j]: continue
        counter[j] += counter[i]
        que.append(j)

print(' '.join([str(c) for c in counter]))

Submission status: Accepted

Solution code:
from queue import Queue
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

n, q = map(int, input().split())
adj = [[] for _ in range(n + 1)]
lazy = [0] * (n + 1)

for _ in range(n - 1):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

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

qu = Queue()
qu.put((1, 0))
while not qu.empty():
    pair = qu.get()
    u = pair[0]
    for v in adj[u]:
        if v == pair[1]: continue
        lazy[v] += lazy[u]
        qu.put((v, u))

for i in range(1, n + 1):
    print(str(lazy[i]) + ' ')

Submission status: Accepted

Solution code:
from collections import deque

n , q = map(int, input().split())
r = [[]for i in range(n)]
s = [0]*n
v = [0]*n
for i in range(n-1):
    a , b = map(int, input().split())
    r[a-1].append(b-1)
    r[b-1].append(a-1)
for i in range(q):
    p , x = map(int, input().split())
    s[p-1]+=x
d= deque()
d.append(0)
def bfs(now):
    v[now]=1
    while d:
        i = d.popleft()
        for j in r[i]:
            if v[j]==0:
                s[j]+=s[i]
                v[j]=1
                d.append(j)
    return
bfs(0)
print(' '.join(list(map(str,s))))

Submission status: Accepted

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

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

res = [0] * N
visited = [False] * N
q = deque([(scores[0], 0)])
while q:
  s,n = q.popleft()
  res[n] = s
  visited[n] = True

  for nei in adj[n]:
    if not visited[nei]:
      q.append((s+scores[nei], nei))

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200010)
def input():
    return sys.stdin.readline()[:-1]
def main():
    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)
    V = [0]*N
    for _ in range(Q):
        p, x = map(int,input().split())
        V[p-1] += x

    def dfs(mae,ima):
        for tsugi in G[ima]:
            if tsugi != mae:
                V[tsugi] += V[ima]
                dfs(ima,tsugi)
    dfs(-1,0)
    print(*V)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,q = map(int,input().split())
v = [[0,0] for i in range(n+1)]
# print(v)
for i in range(n-1):
    a,b = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
for i in range(q):
    p,x = map(int,input().split())
    v[p][1] += x
que = deque([1])
# print(v)
v[1][0] = 1
while que:
    temp = que.popleft()
    for i in v[temp][2:]:
        if v[i][0] == 0:
            v[i][0] = 1
            que.append(i)
            v[i][1] += v[temp][1]
# print(v)
ans = []
for i in v[1:]:
    ans.append(i[1])
    # print(i[1])
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.buffer.readline
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    n, Q = nm()
    G = [list() for _ in range(n)]
    for _ in range(n-1):
        u, v = nm()
        u -= 1; v -= 1
        G[u].append(v)
        G[v].append(u)
    a = [0]*n
    for _ in range(Q):
        p, x = nm()
        a[p-1] += x
    q = deque()
    q.append(0)
    seen = [1] + [0]*(n-1)
    while q:
        v = q.popleft()
        for x in G[v]:
            if not seen[x]:
                seen[x] = 1
                a[x] += a[v]
                q.append(x)
    print(*a)
    return

solve()

# T = ni()
# for _ in range(T):
#     solve()

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 _ in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
ans = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x
def dfs(c, parent):
    for child in tree[c]:
        if child == parent:
            continue
        else:
            ans[child] += ans[c]
            dfs(child, c)
dfs(0, 0)
print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[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_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur] 
      dfs(chl, cur)
dfs(0, -1)
print(*ans)

Submission status: Accepted

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

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

ansl = [0 for _ in range(n)]
ansl[0] = kasan[0]
kaisuu = 0
settansaku = set([])
setmada = {0}
kouho = 1

while kouho != 0:
	kaisuu += 1
	for i in list(setmada):
		settansaku.add(i)
		setmada.remove(i)
		kouho -= 1
		for k in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					kouho += 1
					ansl[k] = ansl[i] + kasan[k]

print(" ".join([str(ansl[i]) for i in range(n)]))

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]
    counter = [0 for _ in range(N)]

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

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

    q = deque()
    q.append(0)
    d = [-1 for _ in range(N)]
    d[0] = 1

    while q:
        v = q.popleft()
        for n_v in edge[v]:
            if d[n_v] == -1:
                counter[n_v] += counter[v]
                d[n_v] = 1
                q.append(n_v)

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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)

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

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

dfs(0, -1)
print(" ".join(map(str, count)))

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

ls = deque([0])
seen = [0 for i in range(N)]
while len(ls) > 0:
    root = ls.popleft()
    seen[root] = 1

    for next_v in G[root]:
        if not seen[next_v]:
            count[next_v] += count[root]
            ls.append(next_v)

for i in range(N):
    print(count[i], end=" ")

Submission status: Accepted

Solution code:
edge = []
n, q = map(int, input().split())
for _ in range(n+100):
    edge.append([])
for _ in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)
res = [0] * (n+1)
cost = [0] * (n+1)
for _ in range(q):
    a,b = map(int, input().split())
    res[a] += b

import collections
q = collections.deque([[1, 0]])
used = [False] * (n+1)
while len(q) > 0:
    #print(q)
    curnode, cost = q.popleft()
    res[curnode] += cost
    used[curnode] = True
    for i in range(len(edge[curnode])):
        nnext = edge[curnode][i]
        if used[nnext] is True:
            continue
        else:
            q.append([nnext, res[curnode]])
res=res[1:]
print(" ".join(list(map(str, res))))

Submission status: Accepted

Solution code:
n,q=list(map(int,input().split()))
GR=[[] for _ in range(n)]
for i in range(n-1):
  a,b=list(map(int,input().split()))
  GR[a-1].append(b)
  GR[b-1].append(a)
 
ans=[0 for _ in range(n)]
for i in range(q):
  p,x=list(map(int,input().split()))
  ans[p-1] += x
  
gr=[1]
parent=[0 for _ in range(n)]
while gr:
  po=gr.pop()
  for no in GR[po-1]:
    if no == parent[po-1]:
      continue
    gr.append(no)
    parent[no-1]=po
    ans[no-1] += ans[po-1]
      
print(' '.join(map(str,ans)))

Submission status: Accepted

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

G = [[] for i in range(N)]
for i in range(N-1):
    A,B = list(map(int,input().split()))
    G[A-1].append(B-1)
    G[B-1].append(A-1)

QL = [0]*N
for i in range(Q):
    P,X = list(map(int,input().split()))
    QL[P-1] += X

from collections import deque
values = [None]*N
que = deque([0])
values[0] = QL[0]
while que:
    v = que.popleft()
    d = values[v]
    for w in G[v]:
        if values[w] is not None:
            continue
        values[w] = d + QL[w]
        que.append(w)

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

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict

if __name__ == '__main__':
    n, q = map(int, stdin.readline().rstrip().split())
    ab = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n - 1)]
    px = [list(map(int, stdin.readline().rstrip().split())) for _ in range(q)]

    g = defaultdict(list)
    for a, b in ab:
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    adder = defaultdict(int)
    for p, x in px:
        p -= 1
        adder[p] += x

    ans = [float('inf')] * n
    ans[0] = adder[0]
    qu = [0]

    while qu:
        cur = qu.pop()

        for target in g[cur]:
            if ans[target] == float('inf'):
                ans[target] = ans[cur] + adder[target]
                qu.append(target)

    for _ans in ans:
        print(_ans)

Submission status: Accepted

Solution code:
from collections import deque
n,q = map(int,input().split())
data = [[] for i in range(n)]
counter = [0]*n
visited = [0]*n
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x = map(int,input().split())
    p -= 1
    counter[p] += x
dq =deque([0])
while dq:
    r = dq.pop()
    visited[r] = 1
    if data[r]:
        for i in data[r]:
            if not visited[i]:
                counter[i] += counter[r]
                dq.append(i)
print(" ".join(map(str,counter)))

Submission status: Accepted

Solution code:
import collections
n,k = map(int, raw_input().split(' '))



###
#get the data
###
adj = collections.defaultdict(list)
for ii in range(n-1):
	u,v  = map(int,raw_input().split(' '))
	adj[u].append(v)
	adj[v].append(u)

queries = collections.Counter()
for iii in range(k):
	u,v  = map(int,raw_input().split(' '))
	queries[u] += v

###
#BFS 
###
res = collections.Counter()
q = collections.deque([(1,0)])
vis = set([])
while(q):
	uu,count = q.popleft()
	count += queries[uu]
	res[uu] = count
	vis.add(uu)
	for vv in adj[uu]: 
		if vv not in vis:
			vis.add(vv)
			q.append((vv,count))

print ' '.join([ str(res[u]) for u in range(1,n + 1)])

Submission status: Accepted

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

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

graph = defaultdict(set)

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

arr = [0] * (n + 1)

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


def solve():
    stack = [1]
    visited = [True] * 2 + [False] * (n - 1)

    while stack:
        curr = stack.pop()
        for leaf in graph[curr]:
            if visited[leaf]:
                continue
            stack.append(leaf)
            visited[leaf] = True
            arr[leaf] += arr[curr]

    return arr


arr = solve()

print(*arr[1:])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
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)
p=[0]*n
for i in range(q):
  pp,x=map(int,input().split())
  p[pp-1]+=x
from collections import deque
d=deque()
d.append(0)
visited=[False]*n
visited[0]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    p[i]+=p[g]
print(*p)

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,q = readInts()
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(lambda x: int(x) - 1,input().split())
    G[a].append(b)
    G[b].append(a)
val = [0] * n
for i in range(q):
    p,x = readInts()
    p -= 1
    val[p] += x
stack = [(0,-1)]
while stack:
    v,p = stack.pop()
    for nv in G[v]:
        if nv == p:
            continue
        val[nv] += val[v]
        stack.append((nv,v))
# def dfs(v,p):
#     if p != -1:
#         val[v] += val[p]
#     for nv in G[v]:
#         if nv == p:
#             continue
#         dfs(nv,v)
#
# dfs(0,-1)
print(*val)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
edges = [[] for _ in range(N)]
count = [0]*N

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

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

not_yet = [1]*N
not_yet[0] = 0
stack = [0]

while stack:
    parent = stack.pop()
    # print(parent)
    
    for child in edges[parent]:
        if not_yet[child]:
            count[child] += count[parent]
            not_yet[child] = 0
            stack.append(child)

print(*count)

Submission status: Accepted

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

edge = [[] for _ in range(N)]
counter = [0 for _ in range(N + 1)]

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

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

stack = [(0, -1)]
while stack:
    s, parent = stack.pop()
    counter[s] += counter[parent]
    for n in edge[s]:
        if n == parent:
            continue
        stack.append((n, s))

ans = " ".join(map(str, counter[:N]))
print(ans)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
edge = [[] for _ in range(n)]
count = [0] * n

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

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

not_yet = [True] * n
not_yet[0] = False
stack = [0]
while stack:
    parent = stack.pop()
    for child in edge[parent]:
        if not_yet[child]:
            count[child] += count[parent]
            not_yet[child] = False
            stack.append(child)
print(*count)

Submission status: Accepted

Solution code:
import sys


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


def solve():
    N, Q = map(int, input().split())
    g = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add(b)
        g[b].add(a)
    counter = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1
        counter[p] += x

    stack = [0]
    visited = [False] * N
    visited[0] = True
    while stack:
        v = stack.pop()
        for nv in g[v]:
            if visited[nv]:
                continue
            stack.append(nv)
            visited[nv] = True
            counter[nv] += counter[v]
    return counter


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

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)


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


def solve():
    def dfs(v):
        for nv in g[v]:
            if visited[nv]:
                continue
            visited[nv] = True
            counter[nv] += counter[v]
            dfs(nv)

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

    visited = [False] * N
    visited[0] = True
    dfs(0)
    return counter


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

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)


def solve():
    def dfs(v):
        print(counter)
        for nv in g[v]:
            if nv in visited:
                continue
            visited.add(nv)
            counter[nv] += counter[v]
            dfs(nv)

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

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

    stack = [0]
    visited = {0}
    while stack:
        v = stack.pop()
        for nv in g[v]:
            if nv in visited:
                continue
            stack.append(nv)
            visited.add(nv)
            counter[nv] += counter[v]
    return counter


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

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)


def dfs(v):
    print(counter)
    for nv in g[v]:
        if nv in visited:
            continue
        visited.add(nv)
        counter[nv] += counter[v]
        dfs(nv)


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


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

stack = [0]
visited = {0}
while stack:
    v = stack.pop()
    for nv in g[v]:
        if nv in visited:
            continue
        stack.append(nv)
        visited.add(nv)
        counter[nv] += counter[v]
print(" ".join(map(str, counter)))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    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)
    counts = [0] * n
    for _ in range(q):
        p, x = map(int, input().split())
        counts[p - 1] += x

    q = deque()
    q.append(0)
    seen = [False] * n
    seen[0] = True

    while q:
        v = q.popleft()

        for n_v in g[v]:
            if seen[n_v]:
                continue
            seen[n_v] = True
            counts[n_v] += counts[v]
            q.append(n_v)

    print(*counts)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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

ans=[0 for _ in range(n)]
for i in range(q):
  p,x=list(map(int,input().split()))
  ans[p-1] += x
  
gr=[1]
parent=[0 for _ in range(n)]
while gr:
  po=gr.pop()
  for no in GR[po-1]:
    if no == parent[po-1]:
      continue
    gr.append(no)
    parent[no-1]=po
    ans[no-1] += ans[po-1]
      
print(' '.join(map(str,ans)))

Submission status: Accepted

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

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

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

    ans_q = deque([(0, ans[0])])
    while len(ans_q) > 0:
        start = ans_q.popleft()
        cost = start[1]
        ans[start[0]] = cost
        for e in edge[start[0]]:
            if checked[e] == 0:
                checked[e] = 1
                ans_q.append((e, cost+ans[e]))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def dfs(v, pv):
    for nv in g[v]:
        if nv == pv:
            continue
        cnt[nv] += cnt[v]
        dfs(nv, v)


(N, Q), *ABPX = [list(map(int, s.split())) for s in open(0)]
g = [set() for _ in range(N)]
for a, b in ABPX[:N - 1]:
    g[a - 1].add(b - 1)
    g[b - 1].add(a - 1)

cnt = [0] * N
for p, x in ABPX[N - 1:]:
    cnt[p - 1] += x
dfs(0, -1)
print(*cnt)

Submission status: Accepted

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

# graph = [[] for _ in range(N)]
# for i, (ai, bi) in enumerate(ab):
#     graph[ai - 1].append(bi - 1)
#     graph[bi - 1].append(ai - 1)

from collections import deque
    
# c = [0] * N
# for j, (pj, xj) in enumerate(px):
#     c[pj - 1] += xj

graph = [[] for _ in range(N)]
for _ in range(N - 1):
    ai, bi = map(int, input().split())
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)
    
c = [0] * N
for _ in range(Q):
    pj, xj = map(int, input().split())
    c[pj - 1] += xj
    
ans = [None] * N
q_0 = deque([(0, 0)])
while len(q_0) > 0:
    score, src = q_0.popleft()
    # print("#", score, src)
    score_tmp = score + c[src]
    ans[src] = score_tmp
    for dst in graph[src]:
        if ans[dst] == None:
            q_0.append((score_tmp, dst))

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200010)
input = sys.stdin.readline
def main():
    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)
    V = [0]*N
    for _ in range(Q):
        p, x = map(int,input().split())
        V[p-1] += x

    def dfs(mae,ima):
        for tsugi in G[ima]:
            if mae != tsugi:
                V[tsugi] += V[ima]
                dfs(ima,tsugi)
    dfs(-1,0)
    print(*V)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N,Q = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
A = [0 for _ in range(N+1)]
for _ in range(Q):
    p,x = map(int,input().split())
    A[p] += x
que = deque([1])
hist = [0 for _ in range(N+1)]
hist[1] = 1
while que:
    i = que.popleft()
    for j in G[i]:
        if hist[j]==0:
            A[j] += A[i]
            que.append(j)
            hist[j] = 1
print(*A[1:])

Submission status: Accepted

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

n, q = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(x) for x in input().split()]
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
cnt = [0]*n
for _ in range(q):
    p, x = [int(x) for x in input().split()]
    cnt[p - 1] += x
def dfs(x):
    stack = [x]
    used = [0]*n
    used[x] = 1
    while stack:
        u = stack.pop()
        for v in g[u]:
            if not used[v]:
                cnt[v] += cnt[u]
                stack.append(v)
                used[v] = 1
dfs(0)
print(*cnt)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    n,q=map(int,readline().split())
    G=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(lambda x:int(x)-1,readline().split())
        G[a].append(b)
        G[b].append(a)

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

    cnts=[0]*n
    flags=[False]*n
    flags[0]=True
    d=deque([[0,p[0]]])
    while len(d)>0:
        tmp=d.popleft()
        now=tmp[0]
        p_now=tmp[1]
        cnts[now]=p_now
        for nex in G[now]:
            if flags[nex]==False:
                flags[nex]=True
                d.append([nex,p_now+p[nex]])

    print(*cnts)
if __name__=="__main__":
    main()

Submission status: Accepted

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

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

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

s = []
visited = [-1]*n
s.append(0)
visited[0] = 0
while s:
    v = s.pop()
    for u in g[v]:
        if visited[u] == -1:
            X[u] += X[v]
            visited[u] = 0
            s.append(u)
print(*X)

Submission status: Accepted

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

def bfs():
    q = deque([0])
    visited = [False]*N
    visited[0] = True
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if not visited[nv]:
                add[nv] += add[v]
                q.append(nv)
                visited[nv] = True

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)

add = [0]*N

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

bfs()
print(*add)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
T=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
C=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    C[p-1]+=x
S=[0]
P=[0]*n
while S:
    s=S.pop()
    for t in T[s]:
        if t==P[s]:
            continue
        P[t]=s
        S.append(t)
        C[t]+=C[s]
print(' '.join(map(str,C)))

Submission status: Accepted

Solution code:
# ＢＦＳ, グラフ, 全探索, 親の情報を自身に加算
 # ※ 要削除

from collections import deque

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

pic = [[] for _ in range(n+1)] # ダミーのノード '0' を含む
for _ in range(n-1): # 絵の取り込み
    x, y = map(int, input().split())
    pic[x].append(y)
    pic[y].append(x)
    
cnts = [0] * (n+1) # カウンター初期化
for _ in range(q): # 初期情報取り込み
    x, y = map(int, input().split())
    cnts[x] += y

visited = [0] * (n+1) # 訪問の記録、初期化
visited[0], visited[1] = 1, 1 # 開始時情報記録

queue = deque([])
queue.append(1)

#print(n, q) # ※
#print(pic) # ※
#print(cnts)
#print(visited) # ※

while queue:
    tmp = queue.popleft() # 探索候補を popleft して...
    for i in pic[tmp]: # 次の探索候補を探索
        if visited[i] != 0: # 未訪問かどうかを確認...
            continue
        else: # 未訪問の場合...
            visited[i] = 1 # 現在地の訪問を記録
            cnts[i] += cnts[tmp] # 親の 'cnt' を自身の 'cnt' に加える
            queue.append(i) # 現在地を探索候補に積む

print(*cnts[1:])