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
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
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)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
ex = [0] * N
for p,x in PX:
    ex[p-1] += x

ans = [None] * N
def dfs(v=0,c=0,p=-1):
    c += ex[v]
    ans[v] = c
    for to in es[v]:
        if to==p: continue
        dfs(to,c,v)

dfs()
print(*ans)

Submission status: Accepted

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

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

score = [0] * (N + 1)
for n, p in query:
    score[n] += p

seen = [0] * (N + 1)
seen[1] = 1
node = deque([1])
while node:
    s = node.popleft()
    for t in edge[s]:
        if not seen[t]:
            seen[t] = 1
            score[t] += score[s]
            node.append(t)

print(*score[1:])

Submission status: Accepted

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

from collections import deque
q = deque()
q.append((0, C[0]))
ans = [-1]*N
ans[0] = C[0]
while q:
    temp = q.pop()
    u = temp[0]
    c = temp[1]
    for v in E[u]:
        if ans[v] == -1:
            ans[v] = c+C[v]
            q.append((v, c+C[v]))

print(*ans)

Submission status: Accepted

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

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

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

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

cnt = [0]*N

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

bfs()

print(*cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
n,q=map(int,input().split())
l=[[] 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)
ans=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x
def dsf(index,u):
  for i in l[index]:
    if i==u:continue
    ans[i]+=ans[index]
    dsf(i,index)
dsf(0,-1)
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
n,q=map(int,input().split())
l=[[] 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)
px=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  px[p-1]+=x
ans=[0]*n
def dsf(index,u):
  ans[index]=ans[u]+px[index]
  for i in l[index]:
    if i==u:continue
    dsf(i,index)
dsf(0,-1)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
E=[[]for _ in range(n)]
P=[0]*n
V=[False]*n
for i in range(n-1):
   a,b=map(int,input().split())
   E[a-1].append(b-1)
   E[b-1].append(a-1)
for i in range(q):
   p,x=map(int,input().split())
   P[p-1]+=x
que=deque([0])
while que:
   s=que.popleft()
   V[s]=True
   for ni in E[s]:
      if V[ni]==False:
         P[ni]+=P[s]
         que.append(ni)
print(*P)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

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

def dfs(now , prev = -1):
    for next in graph[now]:
        if next == prev:
            continue
        point[next] += point[now]
        dfs(next , now)

dfs(0)
print(*point)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
E=[[]for _ in range(n+1)]
P=[0]*(n+1)
V=[False]*(n+1)
for i in range(n-1):
   a,b=map(int,input().split())
   E[a].append(b)
   E[b].append(a)
for i in range(q):
   p,x=map(int,input().split())
   P[p]+=x
que=deque([1])
while que:
   s=que.popleft()
   V[s]=True
   for ni in E[s]:
      if V[ni]==False:
         P[ni]+=P[s]
         que.append(ni)
print(*P[1:])

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
K=[[]for _ in range(n)]
P=[0]*n
V=[False]*n
for i in range(n-1):
   a,b=map(int,input().split())
   K[a-1].append(b-1)
   K[b-1].append(a-1)
for i in range(q):
   p,x=map(int,input().split())
   P[p-1]+=x
que=deque([0])
while que:
   s=que.popleft()
   V[s]=True
   for ni in K[s]:
      if V[ni]==False:
         P[ni]+=P[s]
         que.append(ni)
print(*P)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
L=[[]for _ in range(n)]
V=[False]*n
P=[0]*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)
for i in range(q):
   p,x=map(int,input().split())
   P[p-1]+=x
que=deque([0])
while que:
   s=que.popleft()
   V[s]=True
   for ni in L[s]:
       if V[ni]==False:
           P[ni]+=P[s]
           que.append(ni)
print(*P)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
K=[[] for _ in range(n)]
V=[False]*n
P=[0]*n
for i in range(n-1):
   a,b=map(int,input().split())
   K[a-1].append(b-1)
   K[b-1].append(a-1)
for i in range(q):
   q,x=map(int,input().split())
   P[q-1]+=x
que=deque([0])
while que:
   s=que.popleft()
   V[s]=True
   for ni in K[s]:
      if V[ni]==False:
         P[ni]+=P[s]
         que.append(ni)
print(*P)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
E=[[] for _ in range(n)]
visited=[False]*n
point=[0]*n
for i in range(n-1):
   a,b=map(int,input().split())
   E[a-1].append(b-1)
   E[b-1].append(a-1)
for i in range(q):
   p,x=map(int,input().split())
   point[p-1]+=x

que=deque([0])
while que:
   v=que.popleft()
   visited[v]=True
   for nv in E[v]:
      if visited[nv]==True:
         continue
      point[nv]+=point[v]
      que.append(nv)
print(*point)

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
eage=[[] for i in range(n)]
visited=[False]*n
point=[0]*n
for i in range(n-1):
    a,b=map(int,input().split())
    eage[a-1].append(b-1)
    eage[b-1].append(a-1)
for i in range(q):
    p,x=map(int,input().split())
    point[p-1]+=x

q=deque([0])
while q:
    v=q.popleft()
    visited[v]=True
    for nv in eage[v]:
        if visited[nv]==True:
            continue
        point[nv]+=point[v]
        q.append(nv)
print(*point)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, sys.stdin.readline().split(" "))
    # print(a, b)
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
# print(edges)
# sys.exit()

points = [0] * N
for _ in range(Q):
    p, x = map(int, sys.stdin.readline().split(" "))
    points[p-1] += x


visited = set()
counted = [0] * N
q = deque([(0, points[0])])
while q:
    node, point = q.popleft()
    # print(node, point)
    if node in visited:
        continue
    counted[node] = str(point)
    visited.add(node)
    for edge in edges[node]:
        q.appendleft((edge, point + points[edge]))

print(" ".join(counted))

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
PX = [list(map(int, input().split())) for _ in range(Q)]
 
graph = [[] for _ in range(N + 1)]
for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)
  
cost = [0] * (N + 1)
for p, x in PX:
  cost[p] += x
  
check = [0] * (N + 1)
stack = [1]
check[1] = 1
 
while stack:
  s = stack.pop()
  for g in graph[s]:
    if check[g] == 0:
      check[g] = 1
      cost[g] += cost[s]
      stack.append(g)
      
print(*cost[1:])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
T = [0 for _ in range(N+1)]
for _ in range(Q):
    p,x = map(int,input().split())
    T[p] += x
hist = [0 for _ in range(N+1)]
stack = [1]
hist[1] = 1
while stack:
    x = stack.pop()
    for y in G[x]:
        if hist[y]==0:
            T[y] += T[x]
            stack.append(y)
            hist[y] = 1
print(*T[1:])

Submission status: Accepted

Solution code:
N, Q, *ABPX = map(int, open(0).read().split())
AB, PX = ABPX[:2 * (N - 1)], ABPX[2 * (N - 1):]

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

ans = [0] * (N + 1)
for p, x in zip(*[iter(PX)] * 2):
    ans[p] += x


stack = [(1, 0)]
while stack:
    v, p = stack.pop()
    for c in E[v]:
        if c == p:
            continue
        ans[c] += ans[v]
        stack.append((c, v))

print(*ans[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)

N, Q, *ABPX = map(int, open(0).read().split())
AB, PX = ABPX[:2 * (N - 1)], ABPX[2 * (N - 1):]

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

ans = [0] * (N + 1)
for p, x in zip(*[iter(PX)] * 2):
    ans[p] += x

def dfs(v, p):
    for c in E[v]:
        if c == p:
            continue
        ans[c] += ans[v]
        dfs(c, v)

dfs(1, 0)

print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque

N, Q, *ABPX = map(int, open(0).read().split())
AB, PX = ABPX[:2 * (N - 1)], ABPX[2 * (N - 1):]

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

C = [0] * (N + 1)
for p, x in zip(*[iter(PX)] * 2):
    C[p] += x

ans = [0] * (N + 1)
visited = [False] * (N + 1)

Q = deque([(1, 0)])
while Q:
    v, c = Q.popleft()
    visited[v] = True

    ans[v] = c + C[v]

    for u in E[v]:
        if visited[u]:
            continue
        Q.append((u, c + C[v]))

print(*ans[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)

N, Q, *ABPX = map(int, open(0).read().split())
AB, PX = ABPX[:2 * (N - 1)], ABPX[2 * (N - 1):]

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

C = [0] * (N + 1)
for p, x in zip(*[iter(PX)] * 2):
    C[p] += x


ans = [0] * (N + 1)
def dfs(v, p, acc):
    ans[v] = acc + C[v]
    for c in E[v]:
        if p != c:
            dfs(c, v, acc + C[v])

dfs(1, 0, 0)

print(*ans[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().rstrip()

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

    ans = [0 for _ in range(N + 1)]
    for p, x in PX:
        ans[p] += x
    visited = set()
    def dfs(i):
        visited.add(i)
        for j in ki[i]:
            if j in visited:
                continue
            ans[j] += ans[i]
            dfs(j)
    dfs(1)
    print(*ans[1:])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def main():
    N, Q = map(int, input().split())

    tree = defaultdict(list)
    counter = defaultdict(int)
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    for _ in range(Q):
        p, x = map(int, input().split())
        counter[p] += x

    # bfs
    q = deque([1])
    visited = {1}

    while q:
        i = q.popleft()

        for j in tree[i]:
            if j not in visited:
                q.append(j)
                counter[j] += counter[i]
                visited.add(j)

    counts = [counter[i] for i in range(1, N+1)]
    ans = " ".join(map(str, counts))
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
A=[[] for i in range(n)] #繋がっている頂点
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  A[a].append(b)
  A[b].append(a)
B=[0]*n #コスト
for i in range(q):
  p,q=map(int,input().split())
  p=p-1
  B[p]=B[p]+q
#BFSの時間じゃああああ!!!!!!
C=deque([0])
D=[0]*n #visited枠
while len(C)>0:
  c=C[0]
  C.popleft()
  D[c]=1
  for i in range(len(A[c])):
    if D[A[c][i]]==0:
      C.append(A[c][i])
      B[A[c][i]]+=B[c]
for i in range(n):
  print(B[i],end=" ")
print()

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
	ta,tb = map(int, input().split())
	E[ta].append(tb)
	E[tb].append(ta)

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

for _ in range(Q):
	tp, tx = map(int, input().split())
	cnt[tp] += tx

q = [[1,0]]
flg = [0 for _ in range(N+1)]
flg[0] = 1

while q:
	cp, cost = q.pop()
	cnt[cp] += cost
	flg[cp] = 1
	for np in E[cp]:
		if flg[np] == 1:
			continue
		q.append([np, cnt[cp]])

print(*cnt[1:])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import deque

def main():
  n, q = map(int, input().strip().split())
  tree = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    
  
  counter = [0] * n
  for _ in range(q):
    p, x = map(int, input().strip().split())
    p -= 1
    counter[p] += x

  def bfs(root):
    visited = [False] * n
    dq = deque()
    dq.append(0)
    visited[0] = True
    while dq:
      inode = dq.popleft()
      for ichild in tree[inode]:
        if visited[ichild]:
          continue
        counter[ichild] += counter[inode]
        visited[ichild] = True
        dq.append(ichild)
    
  bfs(tree[1])
  print(' '.join(map(str, counter)))

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def ABC106_B():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
        # divisors.sort()
        return divisors
    N = I()
    ans = 0
    for i in range((N+1)//2):
        cur = i*2+1
        if len(make_divisors(cur))==8:
            ans += 1
    print(ans)
    return

def ABC122_B():
    S = SI()
    ans = 0
    cur = 0
    d = {"A","C","G","T"}
    for s in S:
        if s in d:
            cur += 1
        else:
            ans = max(ans,cur)
            cur = 0
    ans = max(ans,cur)
    print(ans)
    return

def paken2019_C():
    N, M = LI()
    A = [LI()for _ in range(N)]
    T = [i for i in range(M)]
    ans = 0
    for t1,t2 in itertools.permutations(T,2):
        cur = 0
        for i in range(N):
            cur += max(A[i][t1],A[i][t2])
        ans = max(ans,cur)
    print(ans)
    return

def ABC95_C():
    A, B, C, X, Y = LI()
    if A+B<=C*2:
        ans = A*X+B*Y
    else:
        if X>Y:
            ans = Y*C*2 + min(A,C*2)*(X-Y)
        else:
            ans = X*C*2 + min(B,C*2)*(Y-X)
    print(ans)
    return

def SMTB_D():
    def flag(n,s):
        for l in range(n,N):
            if S[l]==str(s):
                return l
        return N
    N = I()
    S = SI()
    ans = 0
    for i in range(10):
        L1 = flag(0,i)
        for j in range(10):
            L2 = flag(L1+1,j)
            for k in range(10):
                L3 = flag(L2+1,k)
                if L3<N:
                    ans += 1
                    #print(i,j,k)
    print(ans)
    return

def JOI2007_3():
    N = I()
    V = [LI() for _ in range(N)]
    D = set()
    for vx,vy in V:
        D.add((vx,vy))
    ans = 0
    for i in range(N):
        a1, b1 = V[i]
        for j in range(i+1,N):
            a2, b2 = V[j]
            va, vb = a2 - a1, b2 - b1
            if (a1 + vb, b1 - va) in D and (a2 + vb, b2 - va) in D:
                ans = max(ans, va ** 2 + vb ** 2)
            if (a1 - vb, b1 + va) in D and (a2 - vb, b2 + va) in D:
                ans = max(ans, va ** 2 + vb ** 2)
    print(ans)
    return
"""
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
"""# 10

def square869120Contest():
    def length(a,b,x,y):
        if x>y:
            x,y = y,x
        rep = 0
        if a<x:
            rep += (x-a)*2
        if y<b:
            rep += (b-y)*2
        rep += (y-x)
        return rep
    N = I()
    AB = [LI()for _ in range(N)]
    ans = inf
    for i in range(N):
        s = AB[i][0]
        for j in range(N):
            g = AB[j][1]
            cur = 0
            for k in range(N):
                cur += length(AB[k][0],AB[k][1],s,g)
            ans = min(ans,cur)
    print(ans)
    return

def JOI7_D():
    M = I()
    S = [LI()for _ in range(M)]
    Ss = [(0,0)]
    curx,cury = S[0]
    for sx,sy in S[1:]:
        Ss.append((sx-curx,sy-cury))
        curx = sx; cury = sy
    #print(Ss)
    N = I()
    X = [LI()for _ in range(N)]
    D = set()
    for i in range(N):
        cur = (X[i][0],X[i][1])
        D.add(cur)
    for i in range(N):
        flag = True
        curx, cury = X[i]
        for k in range(M):
            curx += Ss[k][0]
            cury += Ss[k][1]
            #print(curx,cury)
            if not (curx, cury) in D:
                flag = False
                break
        if flag:
            #print(i,X[i])
            ansx = X[i][0] - S[0][0]
            ansy = X[i][1] - S[0][1]
            print(ansx,ansy)
            return
    return

def ABC128_C():
    N, M = LI()
    S = [[]for _ in range(N)]
    for i in range(M):
        s = LI()
        for j in s[1:]:
            S[j-1].append(i)
    P = LI()
    #print(S)
    loop = 2**N
    ans = 0
    for i in range(loop):
        p = [0]*M
        cur = []
        for j in range(N):
            if (1<<j)&i==(1<<j):
                cur.append(j)
        for k in cur:
            for l in S[k]:
                p[l] += 1
        flag = True
        for j in range(M):
            if p[j]%2!=P[j]:
                flag = False
        if flag:
            ans += 1
    print(ans)
    return

def ABC2_D():
    N, M = LI()
    V = set()
    for _ in range(M):
        x,y = LI()
        V.add((x,y))
    loop = 2**N
    ans = 0
    #print(V)
    for i in range(loop):
        cur = []
        for j in range(N):
            if (1<<j)&i==(1<<j):
                cur.append(j+1)
        flag = True
        for k1,k2 in itertools.permutations(cur,2):
            if not ((k1,k2) in V or (k2,k1) in V):
                flag = False
                break
        if flag:
            ans = max(ans,len(cur))
    print(ans)
    return

def JOI7_E():
    R, C = LI()
    A = [LI()for _ in range(R)]
    loop = 2**R
    ans = 0
    for i in range(loop):
        rev = set()
        for j in range(R):
            if (1<<j)&i==(1<<j):
                rev.add(j)
        cur = 0
        for j in range(C):
            s = 0
            for k in range(R):
                if k in rev and A[k][j]==0:
                    s += 1
                elif (not k in rev) and A[k][j]==1:
                    s += 1
            cur += max(s,R-s)
        ans = max(ans,cur)
    print(ans)
    return

def square869120Contest4_B():
    N, K = LI()
    A = LI()
    ans = inf
    loop = 2**(N-1)
    for i in range(loop):
        look = set()
        for j in range(N-1):
            if (1<<j)&i==(1<<j):
                look.add(j+1)
        if len(look)<K-1:
            continue
        high = A[0]
        cur = 0
        flag = True
        for j in range(1,N):
            if not (j in look):
                if A[j]>high:
                    flag = False
                    break
            else:
                if high >= A[j]:
                    cur += (high - A[j] + 1)
                    high += 1
                else:
                    high = A[j]
        #print(look,cur)
        if not flag:
            continue
        ans = min(ans,cur)
    print(ans)
    return

def ABC145_C():
    N = I()
    X = [LI()for _ in range(N)]
    ans = 0
    c = 0
    for x in itertools.permutations(X):
        cur = 0
        c += 1
        for i in range(N-1):
            cur += ((x[i+1][0]-x[i][0])**2 + (x[i+1][1]-x[i][1])**2)**0.5
        ans += cur
    ans /= c
    print(ans)
    return

def ABC150_C():
    N = I()
    T = [i+1 for i in range(N)]
    P = LI()
    Q = LI()
    for i,t in enumerate(itertools.permutations(T)):
        flag_P = True
        flag_Q = True
        for j in range(N):
            if t[j]!=P[j]:
                flag_P = False
            if t[j]!=Q[j]:
                flag_Q = False
        if flag_P:
            a = i
        if flag_Q:
            b = i
    ans = abs(a-b)
    print(ans)
    return

def JOI2009_2():
    d = I()
    N = I()
    M = I()
    D = [I()for _ in range(N-1)]
    K = [I()for _ in range(M)]
    D.append(0)
    D.sort()
    D.append(d)
    ans = 0
    for i in range(M):
        cur = bisect.bisect_right(D,K[i])
        ans += min(K[i]-D[cur-1],D[cur]-K[i])
    print(ans)
    return
"""
20 
4 
4 
12
8 
16 
7 
7 
11 
8
"""#3

def ARC37_C():
    N, K = LI()
    A = LI()
    B = LI()
    B.sort()
    l = 0; r = inf
    while(r-l>1):
        cur = 0
        now = (l+r)//2
        for a in A:
            if a==0:
                cur += N
            else:
                cur += bisect.bisect_right(B,now//a)
        if cur<K:
            l =now
        else:
            r = now
    ans = r
    print(ans)
    return

def ABC27_D():
    def judge(h):
        D = [0]*N
        for i in range(N):
            if h<H[i][0]:
                return False
            cur = (h-H[i][0])//H[i][1]
            if cur>=N:
                cur = N-1
            D[cur] += 1
        s = 0
        #print(D,h)
        for i in range(N):
            s += D[i]
            if s>i+1:
                return False
        return True
    N = I()
    H = [LI()for _ in range(N)]
    l = 0; r = inf
    while(r-l>1):
        now = (l+r)//2
        if judge(now):
            r = now
        else:
            l = now
    ans = r
    print(ans)
    return

def JOI2008_3():
    N, M = LI()
    P = [I()for _ in range(N)]
    P_2 = set()
    for i in range(N+1):
        if i==N:
            p1 = 0
        else:
            p1 = P[i]
        for j in range(N+1):
            if j==N:
                p2 = p1
            else:
                p2 = p1+P[j]
            P_2.add(p2)
    P_2 = list(P_2)
    P_2.sort()
    ans = 0
    for p2 in P_2:
        if M<p2:
            continue
        cur = P_2[bisect.bisect_right(P_2,M-p2)-1]+p2
        ans = max(ans,cur)
    print(ans)
    return
"""
3 21 
16 
11 
2
"""#20

def ABC138_D():
    def bfs(n,edges,s,C):
        W = [-1]*n
        que = deque()
        que.append(s)
        W[s] = C[s]
        rep = W[s]
        while(que):
            now = que.pop()
            nowW = W[now]
            for i in edges[now]:
                if W[i]==-1:
                    que.append(i)
                    W[i] = nowW + C[i]
                    rep += W[i]
        return W
    N, Q = LI()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a,b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    C = [0]*N
    for _ in range(Q):
        p,x = LI()
        C[p-1] += x
    ans = bfs(N,V,0,C)
    print(" ".join(map(str,ans)))
    return


import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    ABC138_D()

"""
3 21 
16 
11 
2
"""#20

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    from collections import defaultdict
    MOD = 10**9+7

    N,Q = LMIIS()
    edge = defaultdict(list)
    E = defaultdict(list)

    X = [0]*N
    counts = [0]*N
    for _ in range(N-1):
        a,b=LMIIS()

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

    visited = [False]*N




    for _ in range(Q):
        p,x = LMIIS()
        X[p-1] += x

    # def f(o):
    #     visited[o] = True
    #     counts[o] += X[o]
    #     for d in E[o]:
    #         if visited[d] != True:
    #             counts[d] += counts[o]
    #             f(d)
    # f(0)
    
    origins = [0]
    while len(origins) > 0:
        o = origins.pop()
        visited[o] = True
        counts[o] += X[o]
        for d in E[o]:
            if visited[d] != True:
                counts[d] += counts[o]
                origins.append(d)



    
    for i in counts:
        write(str(i))
        write(' ')

            





    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
edges = [[] for _ in range(n)]

for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

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

stack = []
stack.append((0,-1))
while stack:
    v,p = stack.pop()
    for u in edges[v]:
        if u == p:
            continue
        lst[u] += lst[v]
        stack.append((u,v))
print(*lst)

Submission status: Accepted

Solution code:

from collections import deque

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

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

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

checked = [False] * N
q = deque()
q.append(0)
while q:
    node = q.popleft()
    checked[node] = True
    for nxt in es[node]:
        if not checked[nxt]:
            ans[nxt] += ans[node]
            q.append(nxt)
        

print(*ans)

Submission status: Accepted

Solution code:
def main():
  import sys
  sys.setrecursionlimit(500000)
  input = sys.stdin.readline

  N, Q = map(int, input().split())
  G = [[] for _ in range(N)]
  cnt = [0]*N
  visited = [0]*N

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

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

  visited[0]=1
  st = [0]
  while st:
      v = st.pop()
      for u in G[v]:
          if visited[u]:
              continue
          visited[u] = 1
          cnt[u] += cnt[v]
          st.append(u)    

  print(*cnt)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)

    N, Q = map(int, input().split())
    G = [set() for _ in range(N)]
    cnt = [0]*N
    visited = [0]*N

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

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

    visited[0]=1
    st = [0]
    while st:
        v = st.pop()
        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = 1
            cnt[u] += cnt[v]
            st.append(u)    

    print(*cnt)

if __name__ == '__main__':
    main()