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 sys,resource
from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (256*1024*1024,hard))

n,q = inm()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
v = [0]*n
for i in range(q):
    p,x = inm()
    p -= 1
    v[p] += x
y = [0]*n

d = deque([])
d.append(0)
while len(d)>0:
    i = d.popleft()
    for j in dst[i]:
        v[j] += v[i]
        d.append(j)

for i in range(n):
    printn((' ' if i>0 else '') + str(v[i]))
print("")

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
parentNodes = [1] * (N + 1)  # parentNodes[i] = i番目ノードの親番号

ans = [0] * (N + 1)
for _ in range(N - 1):
    a, b = map(int, input().split())  # 接続ノード
    parentNodes[b] = a

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

for i in range(2, N + 1):
    ans[i] += ans[parentNodes[i]]

ans.pop(0)
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:

import numpy as np

N, Q = (int(x) for x in input().split())

dic = {}

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

#SUM = np.zeros(N, dtype=np.int)
SUM = [0]*N

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

for i in range(N-1) :
    SUM[i+1] += SUM[dic.get(i+2)-1]

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

Submission status: Accepted

Solution code:
def main():
  _map = map
  _range = range
  _int = int
  n, q = _map(_int, input().split())
  values = [0] * (n + 1)
  parents = [0] * (n + 1)
  results = [0] * (n + 1)
  for i in _range(n - 1):
    a, b = _map(_int, input().split())
    parents[b] = a
  for _ in _range(q):
    p, x = _map(_int, input().split())
    values[p] += x
  for i in _range(1, n + 1):
    results[i] = values[i]
    if parents[i] != 0:
      results[i] += results[parents[i]]
  print(*[results[i] for i in range(1, n + 1)])
main()

Submission status: Accepted

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

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
PX = [list(map(int,input().split())) for _ in [0]*Q]

E = [[] for _ in [0]*N]
for a,b in AB:
    a-=1
    b-=1
    E[a].append(b)
    E[b].append(a)

V = [0]*N
for p,x in PX:
    p-=1
    V[p] += x

q = [0]
done = [False]*N
while q:
    i = q.pop()
    done[i] = True
    for j in E[i]:
        if done[j] : continue
        V[j] += V[i]
        q.append(j)

print(*V)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
value = [0]*(N+1)
ab_list = []
for i in range(N-1):
  a, b = map(int, input().split())
  ab_list.append([a, b])
ab_list.sort(key=lambda x:x[0])
for i in range(Q):
  p, q = map(int, input().split())
  value[p] += q
for a, b in ab_list:
  value[b] += value[a]
print(' '.join(map(str, value[1:])))

Submission status: Accepted

Solution code:

N,Q=map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PQ = [list(map(int,input().split())) for _ in range(Q)]
#AB.sort()
#PQ.sort()
l=[[] for _ in range(N)]
ans=[0]*N
for a,b in AB:
	l[a-1].append(b-1)
for p,q in PQ:
	ans[p-1]+=q
for i in range(N-1):
	for j in l[i]:
		ans[j]+=ans[i]
	
print(*ans)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
values = [0] * (n + 1)
parents = [0] * (n + 1)
results = [0] * (n + 1)
for i in range(n - 1):
  a, b = map(int, input().split())
  parents[b] = a
for _ in range(q):
  p, x = map(int, input().split())
  values[p] += x
for i in range(1, n + 1):
  results[i] = values[i]
  if parents[i] != 0:
    results[i] += results[parents[i]]
print(*[results[i] for i in range(1, n + 1)])

Submission status: Accepted

Solution code:

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

# 木
G = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))

## クエリを覚えておく
scores = [0]*N
for i in range(Q):
    p,x = map(int, input().split())
    scores[p-1] += x 

# 和をとっていく
ans = [0]*N
ans[0] = scores[0]
used = [False] * N

"""
dfs TLEする。なんで
"""
# import sys
# sys.setrecursionlimit(100000)
# def dfs(G, v):
#    # vを訪問済みにする
#    used[v] = True
#    #グラフ中の次のVについて
#    for next_v in G[v]:
#        if used[next_v]: continue
#        ans[next_v] = ans[v] + scores[next_v]
#        dfs(G, next_v)
# dfs(G,0)
# print(*ans)

# 木をBFSをする
from collections import deque
used = [False] * N
used[0] = True # 始めどこから行くか
q = deque([0])
while len(q) > 0:
    v = q.popleft()
    Vs = G[v]
    for next_v in Vs: 
        if not used[next_v]:
            q.append(next_v)
            ans[next_v] = ans[v] + scores[next_v]
            used[next_v] = True
print(*ans)

Submission status: Accepted

Solution code:

def solve(N, Q, ABs, PXs):
    values = {i: 0 for i in range(N + 1)}
    ans = [-1 for i in range(N + 1)]
    vertexes = {}
    for a, b in ABs:
        vertexes.setdefault(a, []).append(b)
        vertexes.setdefault(b, []).append(a)

    for p, x in PXs:
        values[p] += x

    queue = []
    queue.append((1, 0))
    while queue:
        index, parent_value = queue.pop()
        value = parent_value + values[index]
        ans[index] = value
        for child in vertexes[index]:
            if ans[child] == -1:
                queue.append((child, value))
    return " ".join([str(a) for a in ans[1:]])


if __name__ == "__main__":
    N, Q = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    PXs = [tuple(map(int, input().split(" "))) for _ in range(Q)]
    print(solve(N, Q, ABs, PXs))

Submission status: Accepted

Solution code:
N, Q = (int(i) for i in input().split())
ab = [[int(i) for i in input().split()] for i in range(N-1)] 
px = [[int(i) for i in input().split()] for i in range(Q)] 
ab.sort()

weight = [0]*N
for i in range(len(px)):
	weight[px[i][0]-1]+=px[i][1]

for g in range(len(ab)):
	weight[ab[g][1]-1] += weight[ab[g][0]-1]

print(*weight)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(5 * 10**5)
input=sys.stdin.readline
 
N, Q = list(map(int, input().split()))
 
M = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    M[a-1].append(b-1)
    M[b-1].append(a-1)
 
ans = [0] * N
for _ in range(Q):
    p, x = list(map(int, input().split()))
    ans[p-1] += x
 
def setAnswer(parent, number):
    ans[number] += ans[parent]
 
    for i in M[number]:
        if i != parent:
            setAnswer(number, i)

ans.append(0)
setAnswer(N, 0)
ans.pop(N)
 
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
#D解説実装
n,q = map(int,input().split())
l = [0 for i in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    l[b-1] = (a-1)
ans = [0 for _ in range(n)]
p = [list(map(int,input().split())) for i in range(q)]
for p1 in p:
    ans[p1[0]-1] += p1[1]
for i in range(1,n):
    ans[i] += ans[l[i]]
print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
from collections import defaultdict

N, Q = map(int, input().split())
E = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
ans = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

for i in range(N):
    for t in E[i]:
        ans[t] += ans[i]
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
n, q = map(int, input().split())

edge = [[] 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)

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

q = deque([(0, -1)])
while q:
    v, p = q.pop()
    for u in edge[v]:
        if u == p:
            continue
        imos[u] += imos[v]
        q.append((u, v))

print(' '.join([str(x) for x in imos]))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
na = lambda: map(int, stdin.readline().split())

def main():
  N, Q = na()

  ab = []
  for _ in range(N-1):
    a, b = na()
    ab.append([a, b])
  ab.sort()

  counter = [0] * (N+1)
  for _ in range(Q):
    p, x = na()
    counter[p] += x
  for i in range(N - 1):
    counter[ab[i][1]] += counter[ab[i][0]]
  print(*counter[1:])

if __name__ == "__main__":
  main()

Submission status: Accepted

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

tree = [[] for _ in range(N)]
result = [0]*N

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

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

for i in range(N - 1):
    for j in tree[i]:
        result[j-1] += result[i]

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

Submission status: Accepted

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

edge = []
for _ in range(N-1):
    edge.append(list(map(int, input().split())))
edge = sorted(edge)
n2w = [0]*(N+1)
for _ in range(Q):
  tmp = list(map(int,input().split()))
  n2w[tmp[0]] += tmp[1]

for a,b in edge:
  n2w[b] += n2w[a]

print(*n2w[1:])

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
from collections import deque
M=lambda:map(int,input().split())
n,q=M()
s=[[]for _ in range(n)]
for i in range(n-1):
  a,b=M()
  s[a-1].append(b-1)
  s[b-1].append(a-1)
p=[0]*n
for i in range(q):
  a,b=M()
  p[a-1]+=b
v=[1]+[0]*(n-1)
d=deque([(0,0)])
while d:
  b,c=d.popleft()
  c+=p[b]
  p[b]=c
  for i in s[b]:
    if v[i]:continue
    v[i]=1
    d.append((i,c))
print(*p)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(1000000)


def main():
    def read_tree(n):
        parents = [0 for _ in range(n + 1)]
        for _ in range(n - 1):
            a, b = [int(x) for x in input().split()]
            parents[b] = a
        return parents

    n, q = [int(x) for x in input().split()]

    parents = read_tree(n)
    cnt = [0] * (n + 1)

    for _ in range(q):
        p, x = [int(x) for x in input().split()]
        cnt[p] += x
    
    for i in range(1, n + 1):
        cnt[i] += cnt[parents[i]]

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


main()

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 = {}
 
scores = [0] * n
 
for i in range(q) :
    scores[px[i][0] - 1] += px[i][1]
#print(*scores) 
for i in range(n - 1) :
    neigh.setdefault(ab[i][0], []).append(ab[i][1])
#print(neigh)

sortKey = sorted(neigh.keys())
 
for k in sortKey :
    for e in neigh[k]:
        scores[e-1]+=scores[k-1]
 
print(*scores)

Submission status: Accepted

Solution code:
from collections import deque
n, q = map(int, input().split())

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

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

q = deque([(0, -1)])
while q:
    v, p = q.pop()
    for u in edge[v]:
        if u == p:
            continue
        imos[u] += imos[v]
        q.append((u, v))

print(' '.join([str(x) for x in imos]))

Submission status: Accepted

Solution code:
from collections import defaultdict as de
n,q=map(int,input().split())
s=[[]for i in range(n+1)]
a=de(int)
for i in range(n-1):
    o,b=map(int,input().split())
    s[o].append(b)
    s[b].append(o)
for i in range(q):
    p,x=map(int,input().split())
    a[p]=a[p]+x
t=[0]*(n+1)
g=[[1,0,0]]
while g:
    w=[]
    for i in g:
        t[i[0]]=i[1]+a[i[0]]
        for j in s[i[0]]:
            if j!=i[2]:
                w.append([j,t[i[0]],i[0]])
    else:
        g=w
print(*t[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())

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

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

q = [(0, -1)]
while q:
    v, p = q.pop()
    for u in edge[v]:
        if u == p:
            continue
        imos[u] += imos[v]
        q.append((u, v))

print(' '.join([str(x) for x in imos]))

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
d = {}
ans = [0]*(n+1)
for i in range(n-1):
    sta,gol = map(int,input().split())
    d[gol] = sta

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

for i in range(n):
    gol = i+1
    if gol in d:
        ans[gol]+=ans[d[gol]]
    

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
from functools import lru_cache

def main():
    n, q = map(int, input().split())
    ab = [[],[]]
    
    for i in range(n-1):
        na,nb = map(int, input().split())
        ab[0].append(na)
        ab[1].append(nb)

    px = [[],[]]
    for i in range(q):
        np,nx = map(int, input().split())        
        px[0].append(np)
        px[1].append(nx)
    
    # print(n,q,ab,px)
    count = [0 for i in range(n)]

    oya_list = [0 for i in range(n)]
    for i in range(len(ab[1])):
        oya_list[ab[1][i]-1] = ab[0][i]
    
    for i in range(len(px[1])):
        count[px[0][i]-1] += px[1][i]
        
    for i in range(1,n):

        count[i] += count[oya_list[i]-1]
    
    print(' '.join(map(str,count)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
tree = [[] for i in range(n)]
counter = [0] * n
visited = [False] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
queue = deque([0])
visited[0] = True
while queue:
    now = queue.pop()
    for j in tree[now]:
        if visited[j]:
            continue
        counter[j] += counter[now]
        visited[j] = True
        queue.append(j)
print(*counter)

Submission status: Accepted

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

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

S = [1]
while len(S) > 0:
    p = S.pop()
    for c in AB[p]:
        X[c] += X[p]
        S.append(c)

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

Submission status: Accepted

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

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

branches = []
for j in range(N - 1):
    parent, child = map(int, input().split())
    branches.append([parent, child])

for _ in range(Q):
    parent, number = map(int, input().split())
    nodes[parent] += number

branches.sort()

for branch in branches:
    parent = branch[0]
    child = branch[1]
    nodes[child] += nodes[parent]

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
tree = [[] for i in range(n)]
counter = [0] * n
visited = [False] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    # tree[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
queue = deque([0])
visited[0] = True
while queue:
    now = queue.pop()
    for j in tree[now]:
        if visited[j]:
            continue
        counter[j] += counter[now]
        visited[j] = True
        queue.append(j)
print(*counter)

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)]
parent = [0] * n
ans = [0] * n

for i in ab:
  a,b=i[0],i[1]
  parent[b-1] = a-1
  
for j in px:
  p,x = j[0], j[1]
  ans[p-1] += x

for key, i in enumerate(ans[1:]):
  key += 1
  ans[key] += ans[parent[key]]
print(*ans)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
 
children_map = [None] * n
vals = [0] * n
 
for i in range(1, n):
    a, b = map(int, input().split())
    children_map[b - 1] = a - 1
 
for j in range(q):
    p, x = map(int, input().split())
    vals[p - 1] += x
 
res = []
for i in range(n):
    parent = children_map[i]
    if parent is not None:
        vals[i] += vals[parent]
    res.append(str(vals[i]))
 
print(" ".join(res))

Submission status: Accepted

Solution code:
#これ計算量一次やけどACにならんかった

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

point_array.sort()
solution = [0]*n

for i in range(q):
    solution[action_array[i][0]-1] += action_array[i][1]

for i in range(n-1):
    solution[point_array[i][1]-1] += solution[point_array[i][0]-1]
    
print(*solution)

Submission status: Accepted

Solution code:
# def add_node(tree, counter, ope, node, value):
#     if node in ope:
#         value += ope[node]
#     counter[node - 1] += value

#     if node in tree:
#         for i in tree[node]:
#             add_node(tree, counter, ope, i, value)


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

tree = {}

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

ope = {}
for j in range(q):
    p, x = map(int, input().split())
    if p not in ope:
        ope[p] = x
    else:
        ope[p] += x

counter = [0] * n

# print(tree, ope)

# for k in ope:
for i in range(1, n + 1):
    if i in ope:
        counter[i - 1] += ope[i]
    if i in tree:
        for j in tree[i]:
            counter[j - 1] += counter[i - 1]
    
# add_node(tree, counter, ope, 1, 0)

print(*counter)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
d = [0 for i in range(N)]

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

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

for i in range(1, N):
    ans[i] += ans[d[i]]

print(*ans)

Submission status: Accepted

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

N, Q = list(map(int, readline().split()))
T = defaultdict(list)
for _ in range(N-1):
    a, b = list(map(int, readline().split()))
    T[a].append(b)

P = defaultdict(int)
for _ in range(Q):
    p, x = list(map(int, readline().split()))
    P[p] += x

q = deque()
ans = [0] * (N+1)
ans[1] = P[1]

for t in T[1]:
    q.append([1, t])
while q:
    a, b = q.popleft()
    ans[b] += ans[a] + P[b]
    for c in T[b]:
        q.append([b, c])

print(*ans[1:])

Submission status: Accepted

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

children_map = [None] * n
vals = [0] * n

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

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

res = []
for i in range(n):
    parent = children_map[i]
    if parent is not None:
        vals[i] += vals[parent]
    res.append(str(vals[i]))

print(" ".join(res))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,Q = inpl()

lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    a,b = a-1,b-1
    lines[a].add(b)

adds = [0]*N
for _ in range(Q):
    p,x = inpl()
    adds[p-1] += x

visited = [False]*N
ans = [0]*N

q = queue.LifoQueue()
q.put([0,0])

while not q.empty():
    x,cnt = q.get()
    cnt += adds[x]
    ans[x] += cnt
    for t in lines[x]:
        q.put([t,cnt])

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

Submission status: Accepted

Solution code:
from operator import itemgetter
n, q = map(int, input().split())
abab = [list(map(int, input().split())) for _ in range(n-1)]
pxpx = [list(map(int, input().split())) for _ in range(q)]
abab.sort(key=itemgetter(0))

ans = [0 for _ in range(n)]
for p, x in pxpx :
    ans[p-1] += x
for a, b in abab :
    ans[b-1] += ans[a-1]
print(*ans)

Submission status: Accepted

Solution code:
import sys

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

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

parent = [0] * n
stack = [0]
while len(stack) > 0:
    i = stack.pop()
    for j in adj[i]:
        res[j] += res[i]
        stack.append(j)

print(' '.join([str(x) for x in res]))

Submission status: Accepted

Solution code:
from collections import defaultdict
n,q=map(int,input().split())
Edges=defaultdict(list)
for _ in range(n-1):
    a,b=map(int,input().split())
    Edges[a-1].append(b-1)
Nodes = [0]*n
for _ in range(q):
    p,x=map(int,input().split())
    Nodes[p-1] += x

def dfs(Edges,Nodes,visited):
    stack = []
    visited = set()
    stack.append((0, 0))

    while len(stack)>0:
        current, preval = stack.pop()
        if current in visited:
            continue
        visited.add(current)
        Nodes[current] += preval
        preval = Nodes[current]
        for i in Edges[current]:
            stack.append((i, preval))
    return Nodes

visited = [False]*(len(Nodes))
Nodes = dfs(Edges,Nodes,visited)

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

Submission status: Accepted

Solution code:
N, Q = map(int, input().split(" "))
points = [0 for _ in range(N+1)]
g = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split(" "))
    g[a].append(b)
for _ in range(Q):
    p, x = map(int, input().split(" "))
    points[p] += x

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

print(*points[1:])

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
tree = [[] for i in range(N)]

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

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

for i in range(N-1):
  for j in tree[i]:
    nodes[j-1]+=nodes[i]
print(" ".join(list(map(str, nodes))))

Submission status: Accepted

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

# 各ノードのリンクを記録
link_set = [set() for _ in range(n-1)]
for i in range(n-1):
  a, b = map(int, input().split())
  link_set[a - 1].add(b)

# カウンターの計算を実施 (O(QN)の計算を避けることがポイント)

## O(Q)の計算
counters = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  counters[p - 1] += x
  
## O(N)の計算
for i in range(n - 1):
  for node in link_set[i]:
    counters[node - 1] += counters[i]

str_counters = [str(c) for c in counters]
print(' '.join(str_counters))

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
edge = [[] for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edge[u].append(v)
cost = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    cost[p] += x
for idx, e in enumerate(cost):
    if e == 0:
        continue
    for f in edge[idx]:
        cost[f] += e
print(*cost)

Submission status: Accepted

Solution code:
def main():
  n,q=map(int,input().split())
  a=[0]*(n-1)
  c=[0 for i in range(n)]
  for i in range(n-1):
    a[i]=list(map(int,input().split()))

  a.sort()

  for i in range(q):
    x,y=map(int,input().split())
    c[x-1]+=y
  for i in range(n-1):
    c[a[i][1]-1]+=c[a[i][0]-1]
  print(*c)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
ans = [0]*N
ab = []
for i in range(1,N):
    ab.append(list(map(int,input().split())))
for j in range(Q):
    pj,xj = map(int,input().split())
    ans[pj-1] += xj
ab.sort()
for i in range(N-1):
    ans[ab[i][1]-1]+=ans[ab[i][0]-1]
print(' '.join(map(str,ans)))

Submission status: Accepted

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

cost=[0]*(N+1)

for _ in range(Q):
	a,b=map(int,input().split())
	cost[a]+=b

for a in A:
	cost[a[1]] += cost[a[0]]
print(*cost[1:])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):
    dedges = [set() for i in range(N+1)]
    uedges = [set() for i in range(N+1)]
    score = [0] * (N+1)

    for i in range(N-1):
        dedges[a[i]].add(b[i])
        # uedges[b[i]].add(a[i])

    # 自分以下のすべての子ノードを記録するようにする
    for i in range(Q):
        score[p[i]] += x[i]

    for i in range(1, N+1):
        for j in dedges[i]:
            score[j] += score[i]

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


    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]" 
    x = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def solve():
	N, Q = MAP()
	ab = [LIST() for _ in range(N-1)]
	tree = defaultdict(list)
	par = [-1]*N
	par[0] = 0
	for a, b in ab:
		tree[a-1].append(b-1)
		tree[b-1].append(a-1)
		par[b-1] = a-1

	px = [LIST() for _ in range(Q)]

	ans = [0] * N  # 答え入れる

	for p, x in px:
		ans[p-1] += x

	
	for i in range(1, N):
		ans[i] += ans[par[i]]

	print(*ans, sep=" ")

if  __name__ == "__main__":
	solve()

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split())
n,q=I()
e=[[]for _ in range(n)]
d=[0]*n
for _ in range(n-1):
    a,b=I()
    e[a-1]+=b-1,
    e[b-1]+=a-1,
for _ in range(q):
    p,x=I()
    d[p-1]+=x
f=[1]+[0]*n
q=[0]
while q:
    v=q.pop()
    for w in e[v]:
        if f[w]:continue
        f[w]=1
        d[w]+=d[v]
        q+=w,
print(*d)

Submission status: Accepted

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

trees = {}
for _ in range(N - 1):
    id1, id2 = map(int, input().split())
    if id1 not in trees:
        trees[id1] = []
    trees[id1].append(id2)

from collections import defaultdict
values = defaultdict(int)
for _ in range(Q):
    nid, val = map(int, input().split())
    values[nid] += val

counters = defaultdict(int)
stack = [[1, 0]] # id, value from parent
while len(stack) > 0:
    myid, parent_val = stack.pop()
    current_val = parent_val + values[myid]
    counters[myid] = current_val
    if myid in trees:
        for cid in trees[myid]:
            stack.append([cid, current_val])

print(' '.join(map(str, [counters[myid] for myid in range(1, N + 1)])))

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
parents = [set() for _ in range(n)]
nodes = [0 for _ in range(n)]

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

for _ in range(q):
    i, k = map(int, input().split())
    nodes[i - 1] += k

for i, p in enumerate(parents):
    nodes[i] += sum([nodes[j] for j in p])

print(*nodes)