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 ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,Q = II()
a = [0]*(N-1)
b = [0]*(N-1)
p = [0]*Q
x = [0]*Q

for i in range(N-1):
    a1,b1 = II()
    a[i] = a1-1
    b[i] = b1-1

for i in range(Q):
    p1,x1 = II()
    p[i] = p1-1
    x[i] = x1


parent = defaultdict(list)
for i in range(N-1):
    parent[b[i]].append(a[i])

val = [0]*N
for i in range(Q):
    val[p[i]] += x[i]

for i in range(1,N):
    val[i] += val[parent[i][0]]

print(*val)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
A = [set([]) for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    A[a].add(b)
C = [0]*(n+1)
for _ in range(q):
    p, x = map(int, input().split())
    C[p] += x
for i in range(1, n+1):
    c = C[i]
    for a in A[i]:
        C[a] += c
print(*C[1:])

Submission status: Accepted

Solution code:
from collections import deque

N, Q = list(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)]

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

# print(g)

for p, x in PX:
    points[p] += x

q = deque([1])
while q:
    node = q.popleft()
    for child in g[node]:
        points[child] += points[node]
        q.append(child)

print(*points[1:])

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
N,Q = map(int,input().split())
route = [[] for _ in range(N)]
ans = [0] * N
for i in range(N - 1):
    a,b = map(int,input().split())
    route[a - 1].append(b)
    route[b - 1].append(a)
for i in range(Q):
    p,x = map(int,input().split())
    ans[p - 1] += x
W = [(0,1)]
A = [1] * N
while W:
    de,nod = heappop(W)
    A[nod - 1] = 0
    for i in route[nod - 1]:
        if A[i - 1] == 1:
            heappush(W,(de + 1,i))
            ans[i - 1] += ans[nod - 1]
print(*ans)

Submission status: Accepted

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

N, Q = [int(x) for x in input().strip().split()]
res = [0 for _ in range(N)]
tree = [[] for _ in range(N)]
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    tree[a-1].append(b)

for q in range(Q):
    p, x = [int(x) for x in input().strip().split()]
    res[p-1] += x

q = deque([1])
cq = deque([0])
while q:
    n = q.popleft()
    c = cq.popleft()
    res[n-1] += c
    if len(tree[n-1])!=0:
        for num in tree[n-1]:
            q.append(num)
            cq.append(res[n-1])

print(*res)

Submission status: Accepted

Solution code:
n, q = map(int,input().split())
tree = [[] for i in range(n)]
v = [0]*n
for i in range(n-1):
    a1,b1 = [int(i) for i in input().split()]
    tree[a1-1].append(b1)
for i in range(q):
    p1,x1 = [int(i) for i in input().split()]
    v[p1 - 1] += x1
for i in range(n):
    for j in range(len(tree[i])):
        v[tree[i][j]-1] += v[i]
for i in range(n):
    print(str(v[i]) +" ",end="")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)

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

for _ in range(n-1):
    a, b = map(int, input().split())
    ab[a].append(b)
for _ in range(q):
    p, x = map(int, input().split())
    p_num[p] += x

def dfs(num, cur_count):
    cur_count += p_num[num]
    ans[num] = cur_count
    if len(ab[num]) <= 0:
        return
    for v in ab[num]:
        dfs(v, cur_count)

dfs(1, 0)

out = []
for i in range(1, n+1):
    out.append(str(ans[i]))
print(" ".join(out))

Submission status: Accepted

Solution code:
n, q = list(map(int, input().split()))
edge = []
for i in range(n-1):
    tempa, tempb = list(map(int, input().split()))
    edge.append((tempa-1, tempb-1))
 
node = [0] * n
 
## 自分のところだけ、カウンターを更新
for i in range(q):
    p, x = list(map(int, input().split()))
    node[p-1] += x
 
edge.sort()
for e in edge:
    node[e[1]] += node[e[0]]


for n in node:
    print(n)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
ki = [0] * (n + 1)
for i in range(n - 1):
    a, b = map(int, input().split())
    ki[b] = a
# print("ki=",ki)

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

for i in range(1, n + 1):
    c[i] += c[ki[i]]
# print(c)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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


for i in range(2, N + 1):
    values[i] += values[parent[i]]
values = map(str, values[1:])
print(" ".join(values))

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
rl = [0] * n
scores = [0] * n
for i in range(n-1):
    a,b = map(int,input().split())
    rl[b-1] = a-1
for j in range(q):
    p,x = map(int,input().split())
    scores[p-1] += x
for k in range(1,n):
    scores[k] += scores[rl[k]]
print(*scores)

Submission status: Accepted

Solution code:
N,Q = (int(i) for i in input().split())
X = []
for i in range(N-1):
    Y = [int(n) for n in input().split()]
    X.append(Y)
X = sorted(X, key=lambda x:x[1])
Z = []
for i in range(N):
    Z.append(0)
    
for i in range(Q):
    Z_1,Z_2 = (int(i) for i in input().split())
    Z[Z_1-1] = Z[Z_1-1] + Z_2

#print(X)
#print(Z)


ans=[Z[0]]

for i in range(1,N):
    ans.append(Z[i])
    ans[i] += ans[X[i-1][0]-1]
    
#print(ans)
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
rl = [0] * n
al = [0] * n
for i in range(n-1):
    a,b = map(int,input().split())
    rl[b-1] = a -1
for j in range(q):
    p,x = map(int,input().split())
    al[p-1] += x
for k in range(n):
    if k == 0:
        pass
    else:
        al[k] += al[rl[k]]
print(*al)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

G = defaultdict(list)

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

parents = [0] * (N + 1)
values = [0] * (N + 1)
values_sum = [-1] * (N + 1)

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

# solve
values_sum[1] = values[1]

queue = [1]
while len(queue) > 0:
    p = queue.pop()
    for q in G[p]:
        if values_sum[q] == -1:
            values_sum[q] = values_sum[p] + values[q]
            queue.append(q)

print(*values_sum[1:])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
ab=[]
for i in range(n-1):
	x,y=map(int,input().split())
	ab.append([x,y])
ab.sort()
ans=[0]*n
cnt=[0]*n
for i in range(q):
	x,y=map(int,input().split())
	ans[x-1]+=y
for i in range(n-1):
	ans[ab[i][1]-1]+=ans[ab[i][0]-1]
print(*ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import Counter

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

d = {}

for i in range(n-1):
    _a,_b = map(int,input().split())
    d[_b] = _a

ans = [0]*n

for i in range(q):
    _p,_x = map(int,input().split())
    ans[_p-1]+=_x


for i in range(1,n):
    ans[i] += ans[d.get(i+1)-1]

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

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

# N <= 2*10^5
# Q <= 2*10^5
N, Q = [int(x) for x in 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)]

node_value = [0] * (N+1)
parent = [-1] * (N+1)

for a, b in ab:
    parent[b] = a

for p, x in px:
    node_value[p] += x

#print(parent)

ans = [0] * (N+1)

for i in range(1, N+1):
    ans[i] = node_value[i]
    if parent[i] != -1:
        ans[i] += ans[parent[i]]

print(*ans[1:], sep=" ")

Submission status: Accepted

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

n, q = [ int(v) for v in input().split() ]
value_list = [ 0 for i in range(n) ]
connect_list = [ [] for i in range(n) ]
for i in range(n-1):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_list[a].append(b)
    connect_list[b].append(a)
for i in range(q):
    c, p = [ int(v)-1 for v in input().split() ]
    value_list[c] += p + 1


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

search_list= connect_list[0]
serached_list[0] = 1
for i in connect_list[0]:
    value_list[i] += value_list[0] 


while search_list != []:
    new_search_list = []
    for i in search_list:
        serached_list[i] = 1
        for j in connect_list[i]:
            if serached_list[j] == 0:
                value_list[j] += value_list[i] 
                new_search_list.append(j)
    search_list = new_search_list
print(*value_list)

Submission status: Accepted

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

dic = defaultdict(list)
n, q = map(int, input().split())

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

tree = [0]*n

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

todo = deque([1])
while todo:
    root = todo.popleft()
    count = tree[root-1]
    children = dic[root]
    for to in children:
        tree[to-1] += count
        todo.append(to)

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

Submission status: Accepted

Solution code:
n,q = (int(num) for num in input().split())
par = [n] * n
visited = [0] * n
val = [0] * n
ab = []
for i in range(n-1):
    a,b = (int(num)-1 for num in input().split())
    par[b] = a
    
for _ in range(q):
    p,x = (int(num) for num in input().split())
    p -= 1
    val[p] += x

for i in range(1,n):
    val[i] += val[par[i]]
    
ans = ""
for num in val:
    ans += str(num) + " "
print(ans)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
link = dict()
counter = list([0]*n)
for i in range(n-1):
    a,b = map(int, input().split())
    link[b-1] = a-1
        
for i in range(q):
  p,pp = map(int, input().split())
  counter[p-1] += pp

for i in range(n):
    if i in link:
        counter[i] += counter[link[i]]

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

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

neigh = {}

ans = [0] * n
#print(neigh)
#print(neigh)

for i in range(q) :
    ans[px[i][0] - 1] += px[i][1]

for i in range(n - 1) :
    neigh.setdefault(ab[i][0], []).append(ab[i][1])

sortKey = sorted(neigh.keys())

for k in sortKey :
    for e in neigh[k] :
        ans[e - 1] += ans[k - 1]

print(*ans)

'''
    ans[sortKey]

for i in range(len(sortKey)) :
    for j in range(i + i, len(sortKey)) :
        if sortKey[i] in neigh[sortKey[j]] :
            neigh[sortKey[j]] += neigh[sortKey[i]]
            break

    if px[i][0] in neigh :
        for e in neigh[px[i][0]] :
            ans[e - 1] += px[i][1]


print(*ans)
'''

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
c=[0 for i in range(n)]
tree=sorted([list(map(int,input().split())) for i in range(n-1)])
for j in range(q):
    p,x=map(int,input().split())
    c[p-1]+=x
for i in range(n-1):
    c[tree[i][1]-1]+=c[tree[i][0]-1]
for i in range(n):
    c[i]=str(c[i])
print(' '.join(c))

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

for i in range(0, n):
	for x in ds[i]:
		ws[x] += ws[i]

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

Submission status: Accepted

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

n,q = map(int, input().split())
child = defaultdict(list)
parent = defaultdict(int)
query = defaultdict(int)
for _ in range(n - 1):
	a, b = map(int, input().split())
	child[a].append(b)
	parent[b] = a
for _ in range(q):
	a, b = map(int, input().split())
	query[a] += b
ans = [-1 for _ in range(n)]
for i in range(1, n + 1):
	if parent[i] == 0:
		break
l = deque([i])
while l != deque([]):
	i = l[0]
	ans[i - 1] = query[i]
	if child[i] != []:
 		for x in child[i]:
 			query[x] += query[i]
 			l.append(x)
	l.popleft()
print(*ans)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
arr_ab = [[] for j in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    arr_ab[a-1].extend([b])
arr_px = [0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    arr_px[p-1]+=x

ans = [0]*N

for i in range(N-1):
    for j in arr_ab[i]:
        arr_px[j-1]+=arr_px[i]
print(' '.join(list(map(str, arr_px))))

Submission status: Accepted

Solution code:

N, Q = map(int, input().split())
a = []
p = []
x = [0]*(N)
A = [0]*(N)

for i in range(N-1):
    t=list(map(int,input().split()))
    if t[0]>t[1]:
        swap = t[1]
        t[1] = t[0]
        t[0] =swap
    a.append((int(t[0]),int(t[1])))
for i in range(Q):
    t=list(map(int,input().split()))
    p.append((int(t[0]),int(t[1])))

a =sorted(a, key=lambda x: x[0])
p =sorted(p, key=lambda x: x[0])

#print(a)
for i in range(Q):
    x[p[i][0]-1] += p[i][1]
for i in range(N):
    A[i] = x[i]
for i in range(N-1):
    La = a[i][0]-1
    Lb = a[i][1]-1

    A[Lb] = A[La]+x[Lb]

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

Submission status: Accepted

Solution code:
n, q = list(map(int, input().split()))

ab_list = []
is_ab = True
done_list = []

# while is_ab:
#     a, b = list(map(int, input().split()))
#     ab_list.append((a, b))
#     done_list.append(a)
#     done_list.append(b)
#     if set(done_list) == set(range(1, n+1)):
#         break

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

px_total_dict = {node_id: 0 for node_id in range(1, n+1)}
for _ in range(q):
    p, x = list(map(int, input().split()))
    px_total_dict[p] += x

ab_list = sorted(ab_list, key=lambda x: x[0])

count_list = [0] * n
next_child_list = []

# 子供ではなく親を覚える方式は？
# parent2children_dict = {i: [] for i in range(1, n+1)}

# for i, ab in enumerate(ab_list):
#     a, b = ab
#     next_child_list.append(b)

#     if i != len(ab_list) - 1 and ab_list[i+1][0] == a:
#         # 次の辺も同じノードが始点だったら
#         continue
#     else:
#         parent2children_dict[a] = next_child_list
#         next_child_list = []

ch2pa_dict = {}

for i, ab in enumerate(ab_list):
    a, b = ab
    ch2pa_dict[b] = a

root_id = list(set(list(range(1, n+1))) - set(list(ch2pa_dict.keys())))[0]
# print('root_id: {}'.format(root_id))

# for i, ab in enumerate(ab_list):
#     a, b = ab
#     next_child_list.append(b)

#     if i != len(ab_list) - 1 and ab_list[i+1][0] == a:
#         # 次の辺も同じノードが始点だったら
#         continue
#     else:
#         parent2children_dict[a] = next_child_list
#         next_child_list = []

# print(parent2children_dict)

for node_id in range(1, n+1):
    # print('node_id: {}'.format(node_id))
    count = px_total_dict[node_id]
    count_list[node_id-1] += count
    if node_id != root_id:
        parent_id = ch2pa_dict[node_id]
        count_list[node_id-1] += count_list[parent_id-1]
    # print(child_list)
    # print(count_list)

ans = ' '.join([str(x) for x in count_list])
print(ans)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
sco = [0]*(n+1)
edge = [[i] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    edge[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    sco[p]+=x
for i in range(1,n+1):
    E=edge[i]
    for e in E:
        if(e==i):continue
        sco[i]+=sco[e]
print(*sco[1:])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
rl = [0] * n
al = [0] * n
for i in range(n-1):
    a,b = map(int,input().split())
    rl[b-1] = a -1
for j in range(q):
    p,x = map(int,input().split())
    al[p-1] += x
for k in range(n):
    if k == 0:
        pass
    else:
        al[k] += al[rl[k]]
print(*al)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
l = [[] for i in range(n+1)]
for i in range(n-1):
	a,b = map(int,input().split())
	#print(l,l[a])
	l[a].append(b)
c = [0 for i in range(n+1)]
for i in range(q):
	a,b = map(int,input().split())
	c[a] += b

for i in range(n+1):
	if(l[i] != []):
		for x in l[i]:
			c[x] += c[i]
for i in range(1,len(c)):
	print(c[i],end = ' ')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
dic = {}

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

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

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

key_list = list(dic.keys())
key_list.sort()

for a in key_list:
    for b in dic[a]:
        v_list[b-1] = v_list[a-1] + v_list[b-1]

print(*v_list)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,q=map(int,input().split())
a=[[0,0] for _ in range(n-1)]
for i in range(n-1):
    a[i][0],a[i][1]=map(int,input().split())
a.sort()
p=[[0,0] for _ in range(q)]
for k in range(q):
    p[k][0],p[k][1]=map(int,input().split())
p.sort()
t=[[i] for i in range(1,n+1)]
ans=[0 for _ in range(n)]
for i in range(q):
    ans[p[i][0]-1]+=p[i][1]
for i in range(n-1):
    ans[a[i][1]-1]+=ans[a[i][0]-1]  
print(' '.join(map(str,ans)))

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)
# print(G)

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

# BFS
que = deque([])
que.append((0, DP[0]))
while que:
    p = que.popleft()
    v = p[1]
    for i in G[p[0]]:
        DP[i] += v
        que.append((i, DP[i]))

print(*DP)

Submission status: Accepted

Solution code:
import sys
from collections import deque

N,Q=map(int, sys.stdin.readline().split())

 
al=[ [] for i in range(N+1) ]
 
for _ in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	al[a].append(b)
	al[b].append(a)

Visit=[ None for i in range(N+1) ] 
score=[ 0 for i in range(N+1) ] 

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


q=deque()
q.append(1)

while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in al[fro]:
		if Visit[to] is None:
			score[to]+=score[fro]
			q.append(to)


for i,ans in enumerate(score):
	if i==0:	continue
	print ans,

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
l=[[] for i in range(N)]
ans=[0 for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
#print(l)

dic=[0 for i in range(N)]

for i in range(Q):
  a,b=map(int,input().split())
  dic[a-1]+=b
#print(dic)

nex=[0]
no=[0]
an=0

while an<N:
  no=nex
  nex=[]
  #print("no",no,"ans",ans)
  for j in no:
    ans[j]+=dic[j]
    an+=1
    for i in l[j]:
      l[i].remove(j)
      ans[i]=ans[j]
      #ans[j]=str(ans[j])
      nex.append(i)
      #print(j,"i",i,"l[i]",l[i],ans,nex,an)
      

for i in range(N):
  ans[i]=str(ans[i])
  
print(" ".join(ans))

Submission status: Accepted

Solution code:
import sys
import queue
#+++++
		
def main():
	n,q = map(int, input().split())
	tree=[[] for _ in range(n+1)]
	hh=[0 for _ in range(n+1)]
	ret=[0 for _ in range(n+1)]
	
	for i in range(n-1):
		pa,ch = map(int, input().split())
		tree[pa].append(ch)
		
	for v in range(q):
		nd, hv = map(int, input().split())
		hh[nd] += hv
		
	ol = queue.Queue(n+1)
	ret[1]=hh[1]
	vv=hh[1]
	for cc in tree[1]:
		ol.put((vv,cc))
		
	while not ol.empty():
		ph,nd=ol.get()
		ret[nd]=hh[nd]+ph
		vv=ret[nd]
		for cc in tree[nd]:
			ol.put((vv,cc))

	rets=' '.join([str(v) for v in ret[1:]])
	print(rets)
	
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[17]:


from sys import stdin
input = stdin.readline

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


# In[18]:


class Node:
    def __init__(self, nb, data): #コンストラクタ
        self.nb = nb
        self.data = data #ノードがもつ数値
        self.parent = -1 # nodeがrootのとき-1、それ以外番号
        #self.childs = [] # childになるnode classが入る
        
    #def connect_childs(self, child_class_):
    #    self.childs.append(child_class_)


# In[19]:


nodes = [Node(_+1, 0) for _ in range(N)]


# In[12]:


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


# In[13]:


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


# In[14]:


def sum_data_to_childs(nodes):
    datas = [0]*N
    
    datas[0] = nodes[0].data
    
    for i in range(1, N):
        nodes[i].data += nodes[nodes[i].parent].data
        #print(nodes[i].data)
        datas[i] = nodes[i].data
        
    return datas


# In[15]:


datas = sum_data_to_childs(nodes)


# In[16]:


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


# In[20]:


#datas = [0] * N


# In[21]:


#child = [[]] * N


# In[22]:


#print(child)


# In[ ]:

Submission status: Accepted

Solution code:
n, q = map(int, input().split())

childs = [[] for _ in range(n+1)]
parent = [-1 if i == 1 else None for i in range(n+1)]
plus = [0 for i in range(n+1)]

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

for _ in range(q):
  p, x = map(int, input().split())
  plus[p] += x
  
nodes = [1]
while nodes:
  node = nodes.pop()
  if childs[node]:
    for cn in childs[node]:
      plus[cn] += plus[node]
      nodes.append(cn)

print(' '.join([str(num) for num in plus[1:n+1]]))

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

from collections import defaultdict

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

parent_map = {b: a for a, b in ab}
child_map = defaultdict(list)
for parent, child in ab:
    child_map[parent].append(child)

operation_map = defaultdict(int)
for p, x in px:
    operation_map[p] += x

counter = [0] * N

counter[0] = operation_map[1]
stack = list(child_map[1])
node_no = 0
while True:
    try:
        node_no = stack.pop()
    except IndexError:
        break

    parent_no = parent_map[node_no]
    counter[node_no - 1] = counter[parent_no - 1] + operation_map[node_no]
    stack += list(child_map[node_no])

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

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
Ki_p = [0 for i in range(N+1)]
Ki_c = [[] for i in range(N+1)]
Ki_co = [0 for i in range(N+1)]
 
for i in range(N-1):
    a,b = map(int,input().split())
    Ki_p[b] = a
    Ki_c[a] += [b]
 
for i in range(Q):
    p,x = map(int,input().split())
    Ki_co[p] += x
 
ans = [0 for i in range(N+1)]
q = {1}
for i in range(N):
    vi = q.pop()
    ans[vi] = Ki_co[vi] + ans[Ki_p[vi]]
    q |= set(Ki_c[vi])
    
print(' '.join(map(str,ans[1:N+1])))

Submission status: Accepted

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

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

    if a not in tree_dict:
        tree_dict[a] = [b]
    else:
        tree_dict[a].append(b)

value_list = list(set(ab_list))

px_dict = {}
for i in range(Q):
    p, x = map(int, input().split())
    if p in px_dict:
        px_dict[p] += x
    else:
        px_dict[p] = x

out = ""
for v in value_list:
    if v in px_dict:
        x = px_dict[v]
        if v in tree_dict:
            tree_list = tree_dict[v]
            for t in tree_list:
                if t in px_dict:
                    px_dict[t] += x
                else:
                    px_dict[t] = x
        o = str(px_dict[v])
    else:
        o = str(0)
    out += o + " "

print(out[:-1])

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


def dfs(tree: dict, count: list) -> list:
    res = [0] * (N + 1)

    stack = [1]
    while stack:
        label = stack.pop()
        res[label] = count[label]
        if tree[label] != []:
            for next_label in tree[label]:
                count[next_label] += count[label]
            stack += tree[label]

    return res


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

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

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

ans = dfs(tree, count)
print(*ans[1:])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
nodes = [[] for _ in range(2*(10**5)+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    nodes[a] += [b]

PX = [0 for _ in range(2*(10**5)+1)]
for _ in range(Q):
    p, x = map(int, input().split())
    PX[p] += x


node_cnts = [0] * (2*(10**5)+1)

q = [(1, PX[1])]
while q:
    node, count = q.pop()
    node_cnts[node] = count
    for n in nodes[node]:
        subtree_nodes = q.append((n, count + PX[n]))


print(*node_cnts[1:N+1], sep=' ')

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq


N, Q = list(map(int, input().split()))
eda = [[] for i in range(N)]
ope = [0]*N
score = [0]*N
parent = [-1]*N


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

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


que = []
que.append(0)
score[0] = ope[0]
for ss in range(N - 1):
	loc = que.pop()
	for edge in eda[loc]:
		if parent[loc] != edge:
			score[edge] += score[loc] + ope[edge]
			que.append(edge)
			parent[edge] = loc

for i in range(N - 1):
	print(score[i], end = "")
	print(" ", end = "")
print(score[N - 1])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())

hen = [[0,0]]*(n-1)
for i in range(n-1) :
    hen[i] = list(map(int,input().split()))

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

#---

hen = sorted(hen, key=lambda x:x[1])
hen = sorted(hen, key=lambda x:x[0])

for i in range(n-1) :
    xlist[hen[i][1]-1] += xlist[hen[i][0]-1]

y = xlist.copy()

c = str(y[0])
for i in range(1,n) :
    c += ' ' + str(y[i])

print(c)

Submission status: Accepted

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

for i in range(len(lis)):
    kotae[i-1] += c_list[i-1]
    for m in lis[i-1]:
        kotae[m-1] += kotae[i-1]

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

Submission status: Accepted

Solution code:
from collections import deque

R = lambda: map(int, input().split())

n, q = R()
g = [[1]] + [[] for _ in range(n)]
c = [0] * (n + 1)
for _ in range(1, n):
    a, b = R()
    g[a].append(b)
    g[b].append(a)
for _ in range(q):
    p, x = R()
    c[p] += x

vis = [False] * (n + 1)
r = [0] * n
qe = deque([0])
while qe:
    u = qe.popleft()
    for v in g[u]:
        if not vis[v]:
            vis[v] = True
            r[v - 1] = r[u - 1] + c[v]
            qe.append(v)
print(*r)

Submission status: Accepted

Solution code:
import sys
import collections


def main():
    [n, q] = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [-1] * (n-1)
    b = [-1] * (n-1)
    tree = collections.defaultdict(set)
    for i in range(n-1):
        a[i], b[i] = [int(s) for s in sys.stdin.readline().strip().split()]
        tree[a[i]-1].add(b[i]-1)
        tree[b[i]-1].add(a[i]-1)

    p = [-1] * q
    x = [-1] * q
    adds = [0] * n
    for i in range(q):
        p[i], x[i] = [int(s) for s in sys.stdin.readline().strip().split()]
        adds[p[i]-1] += x[i]

    results = [0] * n
    seen = set()

    # def rec_add(node, cur, c):
    #     if c > 1000:
    #         return
    #     cur += adds[node]
    #     results[node] = cur
    #     seen.add(node)
    #     for child in tree[node]:
    #         if child in seen:
    #             continue
    #         rec_add(child, cur, c+1)
    #
    # rec_add(0, 0, 0)

    for i in range(n):
        results[i] = adds[i]
        for child in tree[i]:
            adds[child] += results[i]
    print(' '.join([str(n) for n in results]))


main()