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**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## DFS

def main():

    #入力受け取り
    N, Q = mi()
    x = li2(N-1)

    cnt = [0]*N
    for i in range(Q):
        p0, p1 = mi()
        cnt[p0-1] += p1

    #隣接リスト作成
    adj = [[] for i in range(N)]
    for i in range(N-1):
        #x[i][0] -= 1
        #x[i][1] -= 1
        adj[x[i][0]-1].append(x[i][1]-1)
        adj[x[i][1]-1].append(x[i][0]-1)

    #DFS
    global ans
    ans = [0]*N

    def dfs(fr, nx):
        ans[nx] += ans[fr] + cnt[nx]
        for v in adj[nx]:
            if v != fr:
                dfs(nx, v)

    dfs(0, 0)
    '''
    for i in range(N):
        print(ans[i], '', end='')
    '''
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## BFS

#入力受け取り
N, Q = mi()
x = li2(N-1)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    #x[i][0] -= 1
    #x[i][1] -= 1
    adj[x[i][0]-1].append(x[i][1]-1)
    adj[x[i][1]-1].append(x[i][0]-1)

global ans
ans = [0]*N

def dfs(fr, nx):
    ans[nx] += ans[fr] + cnt[nx]
    for v in adj[nx]:
        if v != fr:
            dfs(nx, v)

dfs(0, 0)
'''
for i in range(N):
    print(ans[i], '', end='')
'''
print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in 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)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(que!=deque()):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            que.append(e)


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

from collections import deque
sys.setrecursionlimit(10**9)

#入力受け取り
N, Q = mi()
x = li2(N-1)
#p = li2(Q)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])
    adj[x[i][1]].append(x[i][0])

que = deque()
ans = [0]*N

#for a in range(N):
que.append((0, 0))
num = 0
while que!=deque():
    v = que.popleft()
    ans[v[1]] = ans[v[0]] + cnt[v[1]]
    for next in adj[v[1]]:
        if next != v[0]:
            que.append((v[1], next))

for k in ans:
    print(k, '', end='')

Submission status: Accepted

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

def input():
    return sys.stdin.readline()

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

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

def dfs(now, prev):
    for target in adj[now]:
        if target == prev:
            continue
        score[target] += score[now]
        dfs(target, now)

dfs(1, 0)

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

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split());
n,q=I();r=[0]*n;e=[[]for _ in range(n)];y=[0]+[1]*n;s=[0]
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();r[p-1]+=x;
while s:
  u=s.pop();v=r[u];
  for c in e[u]:
    if y[c]:y[c]=0;r[c]+=v;s+=c,;
print(*r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N,Q = [int(i) for i in input().split()] #N個の頂点、Q回の操作
aaabbb = [[int(i) for i in input().split()] for j in range(N-1)] #木の辺
pppxxx = [[int(i) for i in input().split()] for j in range(Q)] #操作

tree = [[] for i in range(N+1)]

for a,b in aaabbb:
    tree[a].append(b)
    tree[b].append(a)

#print(tree)

counter = [0 for i in range(N+1)]

for p,x in pppxxx:
    counter[p] += x

#print(counter)

def dfs(pos,parent,add):
    counter[pos] += add
    for next_pos in tree[pos]:
        if not next_pos == parent:
            dfs(next_pos,pos,counter[pos])

dfs(1,0,0)

#print(counter)

print(" ".join([str(i) for i in counter[1:]]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(i) for i in input().split()] for _ in range(N-1)]
PX = [[int(j) for j in 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)
    
counters = [0] * (N+1)
for p,x in PX:
    counters[p] += x
    
def dfs(v,parent,add):
    counters[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,counters[v])

dfs(1,0,0)

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

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(N-1):
  x, y = map(int, input().split())
  graph[x].append(y)
  graph[y].append(x)
  
for i in range(Q):
  p, x = map(int, input().split())
  ans[p] += x
  
flag = [0] * (N+1)
flag[1] = 1
q = deque([1])
while q:
  parent = q.popleft()
  for child in graph[parent]:
    if(flag[child] == 0):
      ans[child] += ans[parent]
      flag[child] = 1
      q.append(child)
      
ans = ans[1:]
print(*ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    cnt = [0]*N
    for i in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x

    stk = []
    stk.append((0, -1))
    while len(stk):
        v, par = stk.pop()
        if v>0:
            cnt[v] += cnt[par]
        for i in edge[v]:
            if i!=par:
                stk.append((i, v))

    print(*cnt)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    cnt = [0]*N
    for i in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x

    stk = []
    # visited = set()
    stk.append((0, -1))
    while len(stk):
        # print(stk, visited)
        v, par = stk.pop()
        # if not v in visited:
        #     visited.add(v)
        if v>0:
            cnt[v] += cnt[par]
        for i in edge[v]:
            if i!=par:
            # if not i in visited:
                stk.append((i, v))
        # par = v

    print(*cnt)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**6)

def resolve():
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    cnt = [0]*N
    for i in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x

    def dfs(v, par):
        if v>0:
            cnt[v] += cnt[par]
        for i in edge[v]:
            if i!=par:
                dfs(i, v)

    dfs(0, -1)

    print(*cnt)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
n,q = map(int,input().split())
v = [0]*n
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)
for _ in range(q):
    p,x = map(int,input().split())
    v[p-1] += x
que = deque([(0, -1)])
while que:
    now, pre = que.pop()
    for j in g[now]:
        if j==pre:
            continue
        else:
            v[j] += v[now]
            que.append((j, now))
print(*v)

Submission status: Accepted

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

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

for _ in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    
for _ in range(q):
    a,b = map(int,input().split())
    a -= 1
    point[a] += b
    
def dfs(now, prev = -1):
    for next in tree[now]:
        if next == prev:
            continue
        point[next] += point[now]
        
        dfs(next, now)
        
dfs(0)
print(*point)

Submission status: Accepted

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

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

for _ in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    
for _ in range(q):
    a,b = map(int,input().split())
    a -= 1
    point[a] += b
    
def dfs(now, prev = -1):
    for next in tree[now]:
        if next == prev:
            continue
        point[next] += point[now]
        
        dfs(next, now)
        
dfs(0)
print(*point)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,q=f()
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=f()
  g[a-1]+=[b-1]
  g[b-1]+=[a-1]
c=[0]*n
for i in range(q): v,x=f(); c[v-1]+=x
b=[1]*n
s=[0]
b[0]=0
while s:
  t=s.pop()
  for i in g[t]:
    if b[i]: c[i]+=c[t]; s+=[i]; b[i]=0
print(*c)

Submission status: Accepted

Solution code:
import sys
f=lambda:map(int,sys.stdin.readline().split())
n,q=f()
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=f()
  g[a-1]+=[b-1]
  g[b-1]+=[a-1]
c=[0]*n
for i in range(q):
  v,x=f()
  c[v-1]+=x
b=[0]+[1]*(n-1)
s=[0]
while s:
  t=s.pop()
  for i in g[t]:
    if b[i]:
      c[i]+=c[t]
      s+=[i]
      b[i]=0
print(*c)

Submission status: Accepted

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

count = [0]*N
for i in range(Q):
  p,x = map(int, input().split())
  count[p-1] += x
que = deque([0])
used = [0]*N
used[0] = 1
while que:
  q = que.popleft()
  for p in AB[q]:
    if used[p] == 1:
      continue
    count[p] += count[q]
    used[p] = 1
    que.append(p)
print(*count)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
edge=[[] for _ in range(N)]
cnt=[0]*N
for _ in range(N-1):
  a,b=map(int,input().split())
  edge[a-1]+=(b-1),
  edge[b-1]+=(a-1),
for _ in range(Q):
  p,x=map(int,input().split())
  cnt[p-1]+=x
done=[False]*N
done[0]=True
stack=[0]
while stack:
  par=stack.pop()
  for child in edge[par]:
    if not done[child]:
      done[child]=True
      cnt[child]+=cnt[par]
      stack.append(child)
print(*cnt)

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    Graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        Graph[a].add(b)
        Graph[b].add(a)

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

    root = 0
    visited = [False] * N
    visited[root] = True

    dq = deque()
    dq.append(root)

    while dq:
        v = dq.pop()
        x = ctr[v]
        for u in Graph[v]:
            if visited[u]:
                continue
            visited[u] = True
            ctr[u] += x
            dq.append(u)

    print(*ctr)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys

    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

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

    Graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        Graph[a].add(b)
        Graph[b].add(a)

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

    root = 0
    visited = [False] * N
    visited[root] = True

    def dfs(v):
        x = ctr[v]
        for u in Graph[v]:
            if visited[u]:
                continue
            visited[u] = True
            ctr[u] += x
            dfs(u)

    dfs(root)

    print(*ctr)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
import sys
inp = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

def resolve():
    def dfs(v, parent):
        for nv in G[v]:
            if nv == parent:
                continue
            value[nv] += value[v]
            dfs(nv, v)

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

    value = [0]*(N+1)
    for _ in range(Q):
        v, score = map(int, inp().split())
        value[v] += score

    dfs(1, 0)
    return print(*value[1:])

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
node = [[] for _ in range(n)]
ans = [0] * n

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

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

not_yet = [True] * n
not_yet[0] = False
stack = [0]
while stack:
    parent = stack.pop()
    for child in node[parent]:
        if not_yet[child]:
            ans[child] += ans[parent]
            not_yet[child] = False
            stack.append(child)

print(*ans)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
edge=[[] for _ in range(N)]
cnt=[0]*N
for _ in range(N-1):
  a,b=map(int,input().split())
  edge[a-1]+=(b-1),
  edge[b-1]+=(a-1),
for _ in range(Q):
  p,x=map(int,input().split())
  cnt[p-1]+=x
done=[False]*N
done[0]=True
stack=[0]
while stack:
  par=stack.pop()
  for child in edge[par]:
    if not done[child]:
      done[child]=True
      cnt[child]+=cnt[par]
      stack.append(child)
print(*cnt)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
edge=[[] for _ in range(n)] #木
cnt=[0]*n #出力用
for i in range(n-1): #辺の本数は頂点数-1
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
for _ in range(q):
  p,x=map(int,input().split())
  p-=1
  cnt[p]+=x
done=[False]*n #到達
par=0 #0からスタート
done[par]=True
stack=[par]
while stack:
  par=stack.pop()
  for chi in edge[par]:
    if done[chi]:
      None
    else:
      done[chi]=True
      cnt[chi]+=cnt[par]
      stack.append(chi)
    
print(*cnt)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
edge=[[] for _ in range(n)] #木
cnt=[0]*n #出力用
for i in range(n-1): #辺の本数は頂点数-1
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
for _ in range(q):
  p,x=map(int,input().split())
  p-=1
  cnt[p]+=x
done=[False]*n #到達
par=0 #0からスタート
done[par]=True
stack=[par]
while stack:
  par=stack.pop()
  for chi in edge[par]:
    if done[chi]:
      None
    else:
      done[chi]=True
      cnt[chi]+=cnt[par]
      stack.append(chi)
    
print(*cnt)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**9)


def main():
    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        edges[a].append(b)
        edges[b].append(a)

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

    visited = [False]*N
    visited[0] = True
    q = deque([0])
    while q:
        v = q.pop()
        for n in edges[v]:
            if visited[n]:
                continue
            visited[n] = True
            cnt[n] += cnt[v]
            q.append(n)
    print(*cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


def bfs(tree, start, n, query):
    visited = [False] * n
    visited[start] = True
    que = deque([start])
    while que:
        node = que.popleft()
        cost = query[node]
        for n in tree[node]:
            if not visited[n]:
                query[n] += cost
                visited[n] = True
                que.append(n)

bfs(tree, 0, n, query)
print(*query)

Submission status: Accepted

Solution code:
import sys
inp = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

def resolve():
    N, Q = map(int, inp().split())

    AB = [[int(x) for x in inp().split()] for _ in range(N - 1)]
    PX = [[int(x) for x in inp().split()] for _ in range(Q)]

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

    value = [0] * (N + 1)
    for p, x in PX:
        value[p] += x

    def dfs(v, parent):
        for i in graph[v]:
            if i == parent:
                continue
            value[i] += value[v]
            dfs(i, v)

    dfs(1, 0)
    ans = ' '.join(map(str, value[1:]))
    return print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

ans = [0] * (N + 1)

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

st = [(0, N)]
while st:
    now, pr = st.pop()

    ans[now] += ans[pr]
    for to in edges[now]:
        if to == pr:
            continue
        st.append((to, now))
print(*ans[:N])

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 138
# D - Ki
# https://atcoder.jp/contests/abc138/tasks/abc138_d
import sys
sys.setrecursionlimit(10**6)

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

G = [[] for _ in [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)

counter = [0]*N

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

visited = [False]*N


def dfs(v=0, x=0):
    visited[v] = True
    counter[v] += x
    for u in G[v]:
        if visited[u]:
            continue
        dfs(u, counter[v])


dfs()
print(*counter)

Submission status: Accepted

Solution code:
def examA():
    def calc_L(x1,y1,x2,y2):
        return ((x2-x1)**2 + (y2-y1)**2)**0.5
    N = I()
    X = [LI()for _ in range(N)]
    ans = 0
    for x in itertools.permutations(X):
        cur = 0
        for i in range(1,N):
            cur += calc_L(x[i-1][0],x[i-1][1],x[i][0],x[i][1])
        #print(x,cur)
        ans += cur
    for i in range(1,N+1):
        ans /= i
    print(ans)
    return

def examB():
    def judge(n):
        sn = 0
        for i in n:
            sn += int(i)
        if int(n)%sn==0:
            return "Yes"
        return "No"
    N = SI()
    ans = judge(N)
    print(ans)
    return

def examC():
    N, K = LI()
    P = LI()
    ans = 0
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+(P[i]+1)/2
    for i in range(N-K+1):
        cur = S[i+K] - S[i]
        if cur>ans:
            ans = cur
    print(ans)
    return

def examD():
    def bfs(n,V,s,W):
        visited = [False]*n
        que = deque()
        que.append(s)
        while(que):
            now = que.pop()
            visited[now] = True
            for ne in V[now]:
                if visited[ne]:
                    continue
                W[ne] += W[now]
                que.append(ne)
        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)
    W = [0] * N
    for _ in range(Q):
        p, x = LI()
        W[p-1] += x
    ans = bfs(N,V,0,W)
    print(" ".join(map(str,ans)))
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
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)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

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

work_q = deque([1])
used = set()
used.add(1)
ans[1] = cost[1]
cnt = 0
while work_q:
    here = work_q.popleft()
    cnt = ans[here]
    for i in edge[here]:
        if i not in used:
            work_q.append(i)
            used.add(i)
            ans[i] = cnt + cost[i]
print(*ans[1:])

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
G=[[] for i 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)

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

from collections import deque
visited=[False]*n
q=deque()
q.append(0)
while q:
    cur=q.popleft()
    visited[cur]=True
    for nx in G[cur]:
        if visited[nx]:continue
        c[nx]+=c[cur]
        q.append(nx)
print(*c)

Submission status: Accepted

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

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

d = collections.defaultdict(int)

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

q = collections.deque()

r = [-1]*N
r[0] = d[0]
q.append(0)
while(q):
    x = q.popleft()
    c = r[x]
    for y in G[x]:
        if r[y] < 0:
            r[y] = c+d[y]
            q.append(y)

print(*r)

Submission status: Accepted

Solution code:
import sys #追加
sys.setrecursionlimit(10**6) 
input = sys.stdin.readline

n,q = map(int,input().split())
from collections import defaultdict
dic = defaultdict(list)
for _ in range(n-1):
    a,b = map(int,input().split())
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)

from collections import defaultdict
dicp = defaultdict(int)

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


ansl = [0 for i in range(n)]
used = [0 for i in range(n)]
def dfs(pos, point):
    point += dicp[pos]
    used[pos] = 1
    ansl[pos] = point
    for p in dic[pos]:
        if used[p] == 0:
            dfs(p, point)

dfs(0, 0)

for a in ansl:
    print(a)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
G = [[] for i 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)
C = [0 for i in range(n)]
for j in range(q):
    p, x = map(int, input().split())
    C[p-1] += x
s = 0
Q = [s]
V = [False for i in range(n)]
while Q:
    x = Q.pop()
    V[x] = True
    for y in G[x]:
        if not V[y]:
            Q.append(y)
            C[y] += C[x]
print(*C)

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = [-1] * N
que = deque([0])
ans[0] = cnt[0]
while que:
    v = que.popleft()
    for w in edge[v]:
        if ans[w] < 0:
            ans[w] = ans[v] + cnt[w]
            que.append(w)

print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,q = inpl()
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = inpl()
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)
c = [0] * n
for i in range(q):
    a,b = inpl()
    c[a-1] += b
q = deque()
q.append(0)
fin = [False] * n
fin[0] = True
while q:
    v = q.popleft()
    for nv in g[v]:
        if fin[nv]:continue
        c[nv] += c[v]
        fin[nv] = True
        q.append(nv)
print(*c)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0 for _ in range(n)]
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        counter[p] += x
    q = deque([0])
    checked = [False for _ in range(n)]
    checked[0] = True
    while q:
        now = q.pop()
        for next_v in tree[now]:
            if not checked[next_v]:
                counter[next_v] += counter[now]
                checked[next_v] = True
                q.append(next_v)
    print(" ".join(map(str, counter)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

seen = [False]*(n+1)
def dfs(v):
  seen[v] = True
  for nv in T[v]:
    if seen[nv]:
      continue
    dp[nv] += dp[v]
    dfs(nv)
dfs(1)
print(*dp[1:])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline
def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')
#import numpy as np

from collections import deque

def main():
	n,q=MI()
	E=[[] for _ in range(n+1)]
	X=[0]*(n+1)

	for _ in range(n-1):
		a,b=MI()
		E[a].append(b)
		E[b].append(a)
	for _ in range(q):
		p,x=MI()
		X[p]+=x
	#print(E)

	Q=deque([1])

	while Q:
		#print(Q)
		now=Q.popleft()
		#print(now)
		if E[now]!=[]:
			for i in E[now]:
				if E[i]!=[]:
					Q.append(i)
					X[i]+=X[now]
			E[now]=[]
	print(*X[1:])


if __name__ == "__main__":
	main()