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 math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s):
    if 'LOCAL' in os.environ:
        print(s)

def main():
    global AB, PX, T
    if 'BIG' in os.environ:
        N = 2* 10** 5
        Q = 2 * 10 ** 5
        AB = [[i, i + 1] for i in range(1, N)]
        PX = [[i, 10] for i in range(Q)]
    else:
        N, Q = LI()
        #  AB = []
        T = [[] for _ in range(N+1)]
        PX = [0] * (N+1)
        for i in range(N-1):
            a, b = LI()
            #  AB += (a, b)
            T[a].append(b)
            T[b].append(a)

        for i in range(Q):
            p, x = LI()
            PX[p] += x
        dfs(1, -1)
        print(' '.join(map(lambda x: str(x), PX[1:])))
        #  for i in PX[1:]:
        #      print(i, end=' ')
        #  ans = [0 for _ in range(N)]

def dfs(parent, parent_parent):
    for node in T[parent]:
        if node != parent_parent:
            PX[node] += PX[parent]
            dfs(node, parent)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

ans = []
lines_dict =None
d=None
def main():
    global AB, PX, T
    if 'LOCAL' in os.environ:
        N = 2* 10** 5
        Q = 2 * 10 ** 5
        AB = [[i, i + 1] for i in range(1, N)]
        PX = [[i, 10] for i in range(Q)]
    else:
        N, Q = LI()
        T = [[] for _ in range(N+1)]
        PX = [0] * (N+1)
        for i in range(1, N+1):
            PX[i] = 0
        for i in range(N-1):
            a, b = LI()
            T[a] += [b]
            T[b] += [a]

        for i in range(Q):
            p, x = LI()
            PX[p] += x

        dfs(1, -1)
        for i in PX[1:]:
            print(i, end=' ')
        #  ans = [0 for _ in range(N)]

def dfs(parent, parent_parent):

    for node in T[parent]:
        if node != parent_parent:

            PX[node] += PX[parent]
            dfs(node, parent)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

ans = []
lines_dict =None
d=None
def main():
    global AB, PX, T
    if 'LOCAL' in os.environ:
        N = 2* 10** 5
        Q = 2 * 10 ** 5
        AB = [[i, i + 1] for i in range(1, N)]
        PX = [[i, 10] for i in range(Q)]
    else:
        N, Q = LI()
        #  AB = []
        T = [[] for _ in range(N+1)]
        PX = [0] * (N+1)
        for i in range(N-1):
            a, b = LI()
            #  AB += (a, b)
            T[a] += [b]
            T[b] += [a]

        for i in range(Q):
            p, x = LI()
            PX[p] += x
        #  perr(AB)
        perr(PX)
        dfs(1, -1)
        for i in PX[1:]:
            print(i, end=' ')
        #  ans = [0 for _ in range(N)]

#  def dfs(parent: int, parent_parent: int) -> None:
def dfs(parent, parent_parent):
    for node in T[parent]:
        if node != parent_parent:
            PX[node] += PX[parent]
            dfs(node, parent)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

ans = []
lines_dict =None
d=None
def main():
    global AB, PX, T
    if 'LOCAL' in os.environ:
        N = 2* 10** 5
        Q = 2 * 10 ** 5
        AB = [[i, i + 1] for i in range(1, N)]
        PX = [[i, 10] for i in range(Q)]
    else:
        N, Q = LI()
        #  AB = []
        T = [[] for _ in range(N+1)]
        PX = [0] * (N+1)
        for i in range(N-1):
            a, b = LI()
            #  AB += (a, b)
            T[a] += [b]
            T[b] += [a]

        for i in range(Q):
            p, x = LI()
            PX[p] += x
        #  perr(AB)
        perr(PX)
        dfs(1, -1)
        for i in PX[1:]:
            print(i, end=' ')
        #  ans = [0 for _ in range(N)]

def dfs(parent: int, parent_parent: int) -> None:
    for node in T[parent]:
        if node != parent_parent:
            PX[node] += PX[parent]
            dfs(node, parent)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def wi(): return list(map(int, sys.stdin.readline().split()))
def i(): return int(sys.stdin.readline())
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def mip(n): return [wip() for _ in range(n)]

def main():
    n, q = wi()
    ab = mip(n - 1)
    px = mip(q)
    for i in range(q):
        px[i][1] += 1


    cost = [0] * n
    for i in range(q):
        cost[px[i][0]] += px[i][1]

    son = [[] for _ in range(n)]
    for i in range(n - 1):
        son[ab[i][0]].append(ab[i][1])
        son[ab[i][1]].append(ab[i][0])

    flagli = [0] * n
    flagli[0] = 1
    queue = []
    queue.append(0)
    while queue != []:
        po = queue.pop()
        for kk in son[po]:
            if flagli[kk] == 0:
                flagli[kk] = 1
                queue.append(kk)
                cost[kk] += cost[po]

    for i in range(n):
        print(cost[i],"" , end="")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
input = sys.stdin.readline

def dfs(lst, start, ans):
    queue = [start]
    visited = [False] * len(ans)
    visited[start] = True

    while queue:
        parent = queue.pop()
        for child in lst[parent]:
            if visited[child]:
                continue
            visited[child] = True
            ans[child] += ans[parent]
            queue.append(child)

    print(*ans)

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

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

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

def dfs(lst, start, ans):
    queue = [start]
    visited = [False] * len(ans)
    visited[start] = True

    while queue:
        parent = queue.pop()
        for child in lst[parent]:
            if visited[child]:
                continue
            visited[child] = True
            ans[child] += ans[parent]
            queue.append(child)

    print(*ans)

import sys
input = sys.stdin.readline
n,q = map(int, input().split())
start = 0

tree = [[] for i in range(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)

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

def dfs(lst, start, ans):
    queue = [start]
    visited = [False] * len(ans)
    visited[start] = True

    while queue:
        parent = queue.pop()
        for child in lst[parent]:
            if visited[child]:
                continue
            visited[child] = True
            ans[child] += ans[parent]
            queue.append(child)

    print(*ans)

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

tree = [[] for i in range(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)

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def dfs(lst, start, ans):
    queue = deque([])
    queue.append(start)
    visited = [False] * len(ans)
    visited[start] = True

    while queue:
        parent = queue.pop()
        for child in lst[parent]:
            if visited[child]:
                continue
            visited[child] = True
            ans[child] += ans[parent]
            queue.append(child)

    print(*ans)

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

tree = [[] for i in range(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)

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

Submission status: Accepted

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

n,q = map(int,input().split())
score = [0]*(n+1)
tree = [[] for i in range(n+1)]
check = [0]*(n+1)
check[1] = 1

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

que = deque([1])
qappend = que.append
qpop = que.pop

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

while que:
  n = qpop()
  for i in tree[n]:
    if check[i]:continue
    check[i] = 1
    score[i] += score[n]
    qappend(i)

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

Submission status: Accepted

Solution code:
import sys
#sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

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

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

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

st = [(0, 0, -1)]
while st:
	l = st.pop()
	ans[l[0]] = l[1] + queries[l[0]]
	for v in adj[l[0]]:
		if v != l[2]:
			st.append((v, ans[l[0]], l[0]))

print(*ans)

Submission status: Accepted

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

n,q = map(int,input().split())
score = [0]*(n+1)
tree = [[] for i in range(n+1)]
check = [0]*(n+1)
check[1] = 1

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

que = deque([1])
qappend = que.append
qpop = que.pop

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

while que:
  n = qpop()
  for i in tree[n]:
    if check[i]:continue
    check[i] = 1
    score[i] += score[n]
    qappend(i)

print(*score[1:])

Submission status: Accepted

Solution code:
from collections import deque

n, q = map(int, input().split())
ans = [0 for x in range(n)]
g = [list() for x in range(n)]
for i in range (n - 1) :
    v, u = map(int, input().split())
    v -= 1
    u -= 1
    g[v].append(u)
    g[u].append(v)
for i in range (q):
    p, x = map(int, input().split())
    p -= 1;
    ans[p] += x
dq = deque()
dq.append((0, -1))
while (len(dq)) :
    v, p = dq.pop()
    for u in g[v]:
        if (u != p) :
            ans[u] += ans[v]
            dq.append((u, v))
print(*ans)

Submission status: Accepted

Solution code:
# ABC138D - Ki
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(v: int, p: int) -> None:
    for u in T[v]:
        if u != p:  # p: parent -> skip
            cnt[u] += cnt[v]  # cumulative sum
            dfs(u, v)


def main():
    # Ai (A[i][0]) may be not a parent of Bi (A[i][1])
    global T, cnt
    N, Q = tuple(map(int, input().split()))  # vertices and queues
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    P = tuple(tuple(map(int, input().split())) for _ in range(Q))
    T = [[] for _ in range(N + 1)]  # tree, (N+1: 1-idx -> 0-idx)
    for a, b in E:
        T[a] += [b]
        T[b] += [a]
    cnt = [0] * (N + 1)
    for p, x in P:
        cnt[p] += x  # increase vertex p by x
    dfs(1, -1)
    print(*cnt[1:])


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 _ in range(n)]

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

counter = [0] * n

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

query = deque([(0, -1)]) # current, parent
while query:
    current, parent = query.popleft()
    value = counter[current]
    for node in tree[current]:
        if node == parent:
            continue
        else:
            counter[node] += value
            query.append((node, current))

print(*counter)

Submission status: Accepted

Solution code:
i=lambda:map(int,input().split())
N,Q=i()
adj=[[] for _ in range(N)]
for _ in range(N-1):
  a,b=i()
  adj[a-1].append(b-1)
  adj[b-1].append(a-1)
V = [0 for _ in range(N)]
for _ in range(Q):
  p,x=i()
  V[p-1]+=x
par = [-1 for _ in range(N)]
q = [0]
for cur in q:
  if par[cur] != -1: V[cur] += V[par[cur]]
  for nxt in adj[cur]:
    if nxt == par[cur]: continue
    par[nxt] = cur
    q.append(nxt)
print(' '.join(map(str, V)))

Submission status: Accepted

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

n, q = (int(i) for i in input().split())
tree = [[] for _ in range(n)]

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

ans = [0] * n

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

query = deque([(0, -1)])
while query:
    current_node, parent_node = query.popleft()
    current_value = ans[current_node]
    for node in tree[current_node]:
        if node == parent_node:
            continue
        else:
            ans[node] += current_value
            query.append([node, current_node])

print(*ans)

Submission status: Accepted

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

n, q = map(int, input().split())
tree = [[] for _ in range(n)]

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

ans = [0] * n

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

query = deque([(0, -1)]) # current, parent
while query:
    current_node, parent_node = query.popleft()
    current_value = ans[current_node]
    for node in tree[current_node]:
        if node == parent_node:
            continue
        else:
            ans[node] += current_value
            query.append([node, current_node])

print(*ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import deque
N,Q = map(int,input().split())
tree = {}
px = []
counter = [0 for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = [b]
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = [a]
for _ in range(Q):
    ip,ix = map(int,input().split())
    counter[ip-1] += ix


oya = deque([1])

while oya:
    oyai = oya.popleft()
    for ko in tree[oyai]:
        tree[ko].remove(oyai)
        counter[ko-1] += counter[oyai-1]
        oya.append(ko)




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

Submission status: Accepted

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

def bfs():
    st = deque([(0,-1)])
    while st:
        n,par = st.popleft()
        val = cnt[n]   
        for node in A[n]:
            if node == par:
                continue
            else:
                cnt[node] += val
                st.append([node,n])

N,Q = (int(i) for i in input().split())
A = [[] for _ in range(N)]

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

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

bfs()

print(*cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = lambda: sys.stdin.readline()[:-1]
n,q=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
px=[tuple(map(int,input().split())) for i in range(q)]
# ab.sort(key=lambda tup:(tup[0],tup[1]))

cnt=[0]*(n+1)
data=[[] for i in range(n+1)]

for i in ab:
	data[i[0]].append(i[1])
	data[i[1]].append(i[0])
for j in px:
	cnt[j[0]]+=j[1]


stack=[(1,0)]

while stack:
	v,parent=stack.pop()
	for to in data[v]:
		if to == parent:
			continue
		cnt[to]+=cnt[v]
		stack.append((to,v))

	
print(*cnt[1:])

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
        
N,Q = (int(i) for i in input().split())
A = [[] for _ in range(N)]

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

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

st = deque([(0,-1)])
while st:
    n,par = st.popleft()
    val = cnt[n]   
    for node in A[n]:
        if node == par:
            continue
        else:
            cnt[node] += val
            st.append([node,n])

print(*cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = lambda: sys.stdin.readline()[:-1]
n,q=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
px=[tuple(map(int,input().split())) for i in range(q)]
# ab.sort(key=lambda tup:(tup[0],tup[1]))
visited=[0]*(n+1)
cnt=[0]*(n+1)
data=[[] for i in range(n+1)]

for i in ab:
	data[i[0]].append(i[1])
	data[i[1]].append(i[0])
for j in px:
	cnt[j[0]]+=j[1]

visited[1]=1
stack=[1]

while stack:
	v=stack.pop()
	for to in data[v]:
		if visited[to]:
			continue
		visited[to]=1
		cnt[to]+=cnt[v]
		stack.append(to)

	
print(*cnt[1:])