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

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

adj = {}
val = [0 for i in range(N+1)]
ans = [0 for i in range(N+1)]
check = [False for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    if a not in adj:
        adj[a] = []
    if b not in adj:
        adj[b] = []
    adj[a].append(b)
    adj[b].append(a)

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

queue = deque([(1,0)])

while len(queue):
    q, c = queue.pop()
    check[q]=True
    ans[q] = val[q] + c
    for nq in adj[q]:
        if check[nq] == False:
            queue.append((nq,ans[q]))
print(*ans[1::])

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
ko=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int, input().split())
    ko[a-1].append(b-1)
ans=[0]*n
for i in range(q):
    a,b=map(int, input().split())
    ans[a-1]+=b
nex=[0]
while nex:
    p=nex.pop()
    for i in ko[p]:
        ans[i]+=ans[p]
    nex+=ko[p]
print(*ans)

Submission status: Accepted

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

queue = [0]

while(len(queue) != 0):
    n = queue.pop()
    for i in range(len(tree[n])):
        s[tree[n][i]] += s[n]
        queue.append(tree[n][i])
# def f(n):
#     global s
#     for i in range(len(tree[n])):
#         s[tree[n][i]] += s[n]
#         f(tree[n][i])
#
# f(0)

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

Submission status: Accepted

Solution code:
N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
node_lst=sorted(node_lst, key=lambda x:x[0])
for l in node_lst:
    src, dst = l[0]-1, l[1]-1
    cnt_lst[dst]+=cnt_lst[src]
print(" ".join([str(c) for c in cnt_lst]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
AB = [None] * (N-1)
for i in range(N-1):
    a, b = map(int, input().split())
    AB[i] = (a, b)
PX = [None] * (Q)
for i in range(Q):
    p, x = map(int, input().split())
    PX[i] = (p, x)
    
edges = AB[:]
vals = PX[:]

from collections import defaultdict
vals_dict = defaultdict(lambda: 0)
for v, n in vals:
    vals_dict[v] += n
#print(vals_dict)

graph = defaultdict(lambda: {})
for a, b in edges:
    graph[a][b] = vals_dict[b]
    graph[b][a] = vals_dict[a]
#print(graph)
    

from heapq import heappush, heappop
def dijkstra(graph, start, N):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shortest = dijkstra(graph, 1, N)
shortest = [s+vals_dict[1] for s in shortest]
#print(shortest)
ans = ' '.join(map(str, shortest[1:]))
print(ans)

Submission status: Accepted

Solution code:
def solve():
    cnt = [0] * int(2 * 1e5 + 10)
    li = []
    n, q = map(int, input().split())
    for _ in range(n - 1):
        a, b = map(int, input().split())
        li.append((a, b))
    for _ in range(q):
        p, x = map(int, input().split())
        cnt[p] += x
    for a, b in sorted(li):
        cnt[b] += cnt[a]
    print(*cnt[1 : n + 1])
solve()

Submission status: Accepted

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

g = [[] for _ in range(n)]

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


l = [0]*n
count = [0]*n

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

p = [True]*n
p[0] = False


q = [0]

while q:
    v = q.pop()
    for w in g[v]:
        if p[w]:
            p[w] = False
            l[w] += l[v]
            q.append(w)

print(*l)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n-1)]
ans = [0 for _ in range(n)]
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
tree = [[]for _ in range(n)]
for a, b in ab:
  tree[a-1].append(b-1)
del ab
for index, i in enumerate(tree):
  for j in i:
    ans[j] += ans[index]
print(" ".join(map(str, ans)))

Submission status: Accepted

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

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

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

res = [0] * (n+1)
queue = [(1, root_value[1])]
while len(queue) > 0:
    pair = queue.pop()
    res[pair[0]] += pair[1]
    if neighbor[pair[0]] != []:
        for i in neighbor[pair[0]]:
            queue.append((i, pair[1] + root_value[i]))
    
for i in res[1:]:
    print(i, end=" ")

Submission status: Accepted

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

dic = {}
lst = [0] * (N+1)

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


for i in range(Q):
  p, x = map(int,input().split())
  lst[p] += x
  
for i in range(1,N+1):
  print(lst[i],end=' ')
  if i in dic.keys():
    tmp_lst = dic[i]
    for j in tmp_lst:
      lst[j] += lst[i]
    
print()

Submission status: Accepted

Solution code:
def main():
    inp = input().split(' ')
    n = int(inp[0])
    q = int(inp[1])
    ab = {}
    tree = [0 for i in range(n)]
    for i in range(n-1):
        inp = input().split(' ')
        ab[int(inp[1])] = int(inp[0])
    for i in range(q):
        inp = input().split(' ')
        tree[int(inp[0])-1] += int(inp[1])
    for i in range(n):
        parent = ab.get(i+1)
        if parent is None:
            continue
        else:
            tree[i] += tree[parent-1]
    str_tree = list(map(lambda x: str(x), tree))
    print(' '.join(str_tree))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
root = []
counter = [0] * N
ans = [0] * N

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

root.sort(key=lambda x:x[1])

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

ans[0] = counter[0]

for k in range(1,N):
    ans[k] = counter[k] + ans[root[k-1][0]-1]

print(*list(ans))

Submission status: Accepted

Solution code:
from collections import deque

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

p = []; x = []
ans = [0]*N
for i in range(Q):
    p0, x0 = map(int, input().split())
    p0 -= 1
    ans[p0] += x0
#print(table)
#print(ans)
visited = [0]*N
q = deque()
q.append(0)
while q:
    v = q.pop()
    x0 = ans[v]
    visited[v] = 1
    for u in table[v]:
        if visited[u]:
            continue
        q.append(u)
        ans[u] += x0
for i in range(N):
    print(ans[i])

Submission status: Accepted

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


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


def recursive(p):
    for c in AB[p]:
        X[c] += X[p]
        recursive(c)


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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
d = {1: [0, 0]}
for i in range(n-1):
    a, b = map(int, input().split())
    d[b] = [a, 0]

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

for i in range(2, n+1):
    d[i][1] += d[d[i][0]][1]

l = []
for i in sorted(d.keys()):
    l.append(d[i][1])
    
print(" ".join(map(str, l)))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
uv = [tuple(map(int, input().split())) for _ in range(n-1)]
colors = [0 for _ in range(n+1)]
for i in range(m):
    p,x = map(int,input().split())
    colors[p] += x
edges = [dict() for _ in range(n+1)]
for u, v in uv:
    edges[u][v] = 0
plan = set((1,))
while len(plan) > 0:
    g = plan.pop()
    for n,w in edges[g].items():
            colors[n] = colors[g] +colors[n]
            plan.add(n)
print(*colors[1:])

Submission status: Accepted

Solution code:
from sys import stdin
#from collections import deque
N,Q = [int(x) for x in stdin.readline().rstrip().split()]
ans = [0] * (N+1)
node = []
for _ in range(N-1):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    node.append((a,b))
for _ in range(Q):
    p,x = [int(x) for x in stdin.readline().rstrip().split()]
    ans[p] += x
    
for i in sorted(node):
    a,b = i
    ans[b] += ans[a]

for j in ans[1:]:
    print(j,end=" ")

Submission status: Accepted

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


def solve(N, Q, a, b, p, x):
    parent = [0] * (N+1)
    for ai, bi in zip(a, b):
        parent[bi] = ai
    plus = [0] * (N+1)
    for pi, xi in zip(p, x):
        plus[pi] += xi
    ans = [0] * (N+1)
    for i in range(1, N+1):
        ans[i] = ans[parent[i]] + plus[i]
    return ans[1:]


if __name__ == '__main__':
    N, Q = map(int, input().split())
    a = [0] * (N-1)
    b = [0] * (N-1)
    for idx in range(N-1):
        a[idx], b[idx] = map(int, input().split())
    p = [0] * Q
    x = [0] * Q
    for idx in range(Q):
        p[idx], x[idx] = map(int, input().split())

    ans = solve(N, Q, a, b, p, x)

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

Submission status: Accepted

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

ab_list = [list(map(int, input().split())) for i in range(n-1)]
ab_list = sorted(ab_list)

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

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

for ab in ab_list:
    ans[ab[1]-1] += ans[ab[0]-1]

print(*ans)

Submission status: Accepted

Solution code:
def main():
    N, Q = [int(x) for x in input().split()]
    edges = [[] for x in range(N)]
    cnt = [0] * N
    for i in range(N-1):
        a, b = [int(x) for x in input().split()]
        edges[a - 1].append(b - 1)
    # print(edges)
    # print(Q)
    for i in range(Q):
        p, x = [int(y) for y in input().split()]
        cnt[p - 1] += x
    # print(cnt)

    stack = [0]
    while len(stack) > 0:
        node = stack.pop()
        for t in edges[node]:
            cnt[t] += cnt[node]
            stack.append(t)
        # print(",".join(map(str, stack)))
    print(" ".join(map(str, cnt)))
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(0, N):
    for child in childrens[i]:
        results[child] += results[i]

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

Submission status: Accepted

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

#print(n,q)
edge=[]
for i in range(n-1):
    a = list(map(int,input().split()))
    edge.append(a)

add_list = []
for i in range(q):
    p = list(map(int,input().split()))
    add_list.append(p)

#print(edge,add_list)

ans = [0] * n
edge_list = [-1] * n

for e in edge:
    edge_list[e[1]-1] = e[0]-1

add_value = [0]*n
for v in add_list:
    add_value[v[0]-1] += v[1]

#print(edge_list)
#print(add_value)


dp = [-1] * n
def get_value(i):
    if(dp[i]!=-1):
        return dp[i]
    tmp = add_value[i]
    if edge_list[i] != -1:
        tmp += get_value(edge_list[i])
    dp[i] = tmp
    return dp[i]

for i in range(n):
    ans[i] = get_value(i)
    #print(i,ans)

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

Submission status: Accepted

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

for i in range(N-1):
    a, b = map(int,input().split())
    nord[b-1].add(a-1)
    
nord_num = [0 for i in range(N)]
for i in range(Q):
    p, x = map(int,input().split())
    nord_num[p-1] = nord_num[p-1] + x
    
for i in range(N):
    for j in nord[i]:
        nord_num[i] = nord_num[j] + nord_num[i]
        
count = 1
for i in nord_num:
    if count == N:
        print(i)
    else:
        print(i, end=" ")
        count += 1

Submission status: Accepted

Solution code:
from collections import deque
N,Q = map(int,input().split(' '))

tree = {i:[] for i in range(1,N+1)}
#sub = {i:[i] for i in range(1,N+1)}
#fin = [False]*(N+1)
vals = [0]*(N+1)
#parent = [0]*(N+1)

for i in [0]*(N-1):
	a,b = map(int,input().split(' '))
	tree[a].append(b)
	#parent[b] = a

for i in [0]*Q:
	p,x = map(int,input().split(' '))
	vals[p] += x

ans = [0]*(N+1)

ans[1] = vals[1]

dq = deque([1])
while(dq):
	n = dq.popleft()
	for t in tree[n]:
		ans[t] = vals[t]+ans[n]
		dq.append(t)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6 + 1000)


words = lambda t : list(map(t, input().split()))
n,q = words(int)
par = [0] * n
for i in range(n-1):
    a,b = words(int)
    par[b-1] = a-1

points = [0] * n
for i in range(q):
    p,x = words(int)
    points[p-1] += x

ans = [0] * n
ans[0] = points[0]
for i in range(1,n):
    ans[i] = ans[par[i]] + points[i]


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

Submission status: Accepted

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

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

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

    P = [None]*N
    S = [0]
    P[0] = -1

    while len(S) > 0:
        parntNode = S.pop()
        for childNode in V[parntNode]:
            if P[childNode] == None:
                P[childNode] = parntNode
                S.append(childNode)


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

    Y = [None]*N
    Y[0] = X[0]
    
    for i in range(1, N):
        if Y[i] != None:
            continue

        T = []
        node = i

        while Y[node] == None:
            T.append(node)
            node = P[node]

        s = Y[node]

        for j in reversed(T):
            s += X[j]
            Y[j] = s
        
    print(' '.join(map(str, Y)))
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

ab = []

link = {} 

for i in range(N-1):

    a,b = map(int,input().split())

    if a-1 not in link : link[a-1] = []
    if b-1 not in link : link[b-1] = []


    link[a-1].append(b-1)
    link[b-1].append(a-1)



plus = [0] * N

for i in range(Q):

    p,x = map(int,input().split())

    plus[p-1] += x


Q = []

ans = [0] * N
end = [0] * N
p = [-1] * N
p[0] = 0

nowq = 0
Q.append(0)

end[0] = 1


while nowq < N:

    nowpo = Q[nowq]
    #print (nowpo)
    ans[ nowpo ] = ans[p[ nowpo ]] + plus[nowpo]

    for i in link[nowpo]:

        if end[i] == 0:

            Q.append(i)
            p[i] = nowpo
            #print (i,nowpo)


            end[i] = 1


    nowq += 1

#print (Q,p,link)

for i in ans:
    print (i)

Submission status: Accepted

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

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

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

ans = [0 for _ in range(N)]

F = [0]
ans[0] = W[0]
while F:
    v = F.pop()
    for c in G[v]:
        ans[c] = ans[v] + W[c]
        F.append(c)

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

Submission status: Accepted

Solution code:
def main():
    n,q = map(int,input().split())
    tree = [1 for _ in range(n+1)]
    for _ in range(n-1):
        a,b = map(int,input().split())
        tree[b]=a

    ls_q = [[int(x) for x in input().split()] for _ in range(q)]

    ans = [0 for _ in range(n+1)]
    for i,j in ls_q:
        ans[i] += j

    for i in range(2,n+1):
        ans[i] += ans[tree[i]]

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

if __name__ =="__main__":
    main()

Submission status: Accepted

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

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n, q = getList()

vtxs = [[] for i in range(n)]
already = [0 for i in range(n)]

for i in range(n - 1):
    a, b = getList()
    vtxs[a-1].append(b -1)
    vtxs[b-1].append(a - 1)

count = [0 for i in range(n)]
for i in range(q):
    x, v = getList()
    count[x-1] += v

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

def rep(vx, val):
    # print(vx,val)
    tgt = vtxs[vx]
    already[vx] = 1
    for tg in tgt:
        if already[tg] == 0:
            app = count[tg]
            ans[tg] = val+app
            rep(tg, val+app)

rep(0, count[0])
# print(vtxs)
ans[0] = count[0]
print(*ans)

Submission status: Accepted

Solution code:
def main():
        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)]
        ab.sort()
        # px.sort()
        plus = [0 for _ in range(N)]

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

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

if __name__ == '__main__':
        main()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N, Q = MAP()
    AB = sorted(MATINT(N-1))
    plus = [0] * N
    ans = [0] * N
    for i in range(Q):
        P, X = MAP()
        plus[P-1] += X
    for ab in AB:
        plus[ab[1]-1] += plus[ab[0]-1]
    print(*plus)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

e = [[] for _ in range(n)]
v = [0]*n

for _ in range(n-1):
  x = list(map(int, input().split()))
  e[x[0]-1].append(x[1]-1)  

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

for i, x in enumerate(e):
    for j in x:
        v[j] += v[i]
        
for x in v:
  print(x, end=" ")

Submission status: Accepted

Solution code:
from collections import defaultdict


def p_d():
    N, Q = map(int, input().split())
    l = defaultdict(list)
    ans = [0] * N

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

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

    for i in range(N):
        for j in l[i]:
            ans[j - 1] += ans[i - 1]

    print(*ans)


if __name__ == '__main__':
    p_d()

Submission status: Accepted

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

qx_pairs = []
for _ in range(q):
    qx_pairs.append([int(i) for i in input().split()])

ab_pairs_sorted = sorted(ab_pairs, key= lambda ab_pair: ab_pair[1])

point_list = [0] * n
for qx_pair in qx_pairs:
    index = qx_pair[0] - 1
    x = qx_pair[1]
    point_list[index] += x

for ab_pair in ab_pairs_sorted:
    a = ab_pair[0]
    b = ab_pair[1]
    point_list[b] += point_list[a]


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

Submission status: Accepted

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

edges = [[] for i in range(n)]

d = [0] * n

for i in range(n-1):
    aa,ba = map(int,input().split())
    edges[aa-1].append(ba-1)
    edges[ba-1].append(aa-1)

for i in range(q):
    pa,xa = map(int,input().split())
    d[pa-1] += xa

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

#print(edges)
#print(d)

def dfs(v):
    q=[v]
    visited = [0] * n
    while q:
        v=q.pop()
        hoga = d[v]
        visited[v] = 1
        for i in edges[v]:
            if not visited[i]:
                d[i] += hoga
                q.append(i)
        #print(visited,d)
    return d

print(*dfs(0))

Submission status: Accepted

Solution code:
import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce


def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

sys.setrecursionlimit(10000)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""


class Tree:
    def __init__(self):
        self.child = []
        self.count = 0

if __name__ == "__main__":
    N, Q = map(int, sys.stdin.readline().split())
    node_list = [Tree() for _ in range(N + 1)]

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

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

    ans = []
    for n in node_list[1::]:
        ans.append(n.count)
        for nc in n.child:
            node_list[nc].count += n.count
    print(*ans)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
tree_dic = {}
count = [0] * (N+1) #count[0]は使用しない
for n in range(N):
    tree_dic[n+1] = []
for n in range(N-1):
    a, b = map(int, input().split())
    tree_dic[a].append(b)
#print(tree_dic)
for n in range(Q):
    p, x = map(int, input().split())
    count[p] += x

#木をたどって数字を伝搬させる
for key in tree_dic:
    l = tree_dic[key]
    for i in l:
        count[i] += count[key]

s = " ".join(map(str, count[1:]))
print(s)

Submission status: Accepted

Solution code:
import sys

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

print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

import sys
input = sys.stdin.readline

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

query = [0] * N
ans = [0] * N

for p,x in px:
    query[p-1] = query[p-1] + x
    
adj_list = [[] for _ in range(N)]
for a,b in ab:
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(b-1)

memo = [True] * N

def dfs(v,val):
    child = adj_list[v]
    memo[v] = False
    val += query[v]
    ans[v] = val
    for s in child:
        if memo[s]:
            dfs(s,val)
    return 
        
dfs(0,0)
print(*ans)

Submission status: Accepted

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

F = [0 for i in range(N)]
T = [[]for i in range(N)]

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

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

ans = [X[i] for i in range(N)]
for i in range(N):
    F[i] = 1
    for j in range(len(T[i])):
        if F[T[i][j]] == 1:
            continue
        ans[T[i][j]] += ans[i]

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

Submission status: Accepted

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

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

for i,bs in enumerate(base_score):
    score[i] = bs
    for j in edge[i]:
        base_score[j] += bs

print(*score)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
a = [0] * (N - 1)
b = [0] * (N - 1)
ab = [0] * (N - 1)
for i in range(N-1):
    ab[i] = list(map(int, input().split()))
ab.sort()

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

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

for i in range(N-1):
    score[ab[i][1]] += score[ab[i][0]]


for i in range(len(score)):
    score[i] = str(score[i])

score.pop(0)

ans = ' '.join(score)

print(ans)

Submission status: Accepted

Solution code:
import sys


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


def main():
    N, Q = map(int, input().split())
    hen = [[int(i)-1 for i in input().split()] for _ in range(N-1)]
    sousa = [[int(i) for i in input().split()] for _ in range(Q)]
    ans = [0]*N
    hen.sort(key=lambda x: x[1])
    hen.sort(key=lambda x: x[0])

    for s in sousa:
        ans[s[0]-1] += s[1]
    for h in hen:
        ans[h[1]] += ans[h[0]]

    # print(hen, sousa)
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


import collections

def first_search(graph, root, actions, ans):
    seen, queue = set([root]), collections.deque([[root, 0],])
    while queue:
        vertex, value = queue.pop()  # popleft: 幅優先探索  /  pop: 深さ優先探索
        ans[vertex] = value + actions[vertex]
        for node in graph[vertex]:
            if node not in seen:
                seen.add(node)
                queue.append([node, ans[vertex]])


def main(): 
    N, Q = LI()
    from collections import defaultdict
    edges = defaultdict(list)
    for _ in range(N-1):
        a, b = LI()
        edges[a].append(b)
        edges[b].append(a)
    actions = defaultdict(int)
    for _ in range(Q):
        p, x = LI()
        actions[p] += x

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

    first_search(edges, 1, actions, ans)

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




main()

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:
n,q=map(int,input().split())
link=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    link[a-1].append(b-1)

under=[[] for i in range(n)]
for i in range(n-1, -1, -1):
    l=link[i]
    for j in l:
        under[i].append(j)

#for i in link:
#    print(i)
#print()
#for i in under:
#    print(i)


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

for i in range(n):
    for j in under[i]:
        ans[j]+=ans[i]
for i in ans:
    print("{} ".format(i), end="")
print()

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = [0] * (N + 1)
queue = deque()
queue.append(1)
visited = [0] * (N + 1)
visited[1] = 1
ans[1] = point[1]
while queue:
    v = queue.pop()
    for u in adj[v]:
        if visited[u] == 0:
            queue.appendleft(u)
            visited[u] = 1
            ans[u] = ans[v] + point[u]

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
# tree = [list(map(int, input().split())) for i in range(n-1)]
edges = [set() for i in range(n)]
for _ in range(n-1):
    a, b= map(int,input().split())
    edges[a-1].add(b-1)
cnt = [0] * n

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

l = [0]
l2 = [cnt[0]]
while len(l) != 0:
    a = l.pop()
    b = l2.pop()
    if a != 0:
        cnt[a] += b
    for i in edges[a]:
        l.append(i)
        l2.append(cnt[a])
print(*cnt)