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:
n,q=map(int,input().split())
cnt=[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):
    a , b = map(int,input().split())
    a = a - 1
    cnt[a] += b
import collections
q=collections.deque()
q.append(0)
check=[0]*n
while q:
  v=q.pop()
  check[v]=1
  for u in g[v]:
    if check[u]==1:
      continue
    cnt[u]+=cnt[v]
    q.append(u)
print(*cnt)

Submission status: Accepted

Solution code:
def MI():  return map(int, input().split())
N,Q=MI()
graph=[[] for i in range(N)]
for i in range(1,N):
  a,b=MI()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
point=[0]*N  
for i in range(Q):
  p,x=MI()
  point[p-1]+=x
import collections
q=collections.deque()
q.append(0)
check=[0]*N
check[0]=1
while len(q)>0:
  v=q.pop()
  check[v]=1
  for u in graph[v]:
    if check[u]==1:
      continue
    point[u]+=point[v]
    q.append(u)
print(*point)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def MI():  return map(int, input().split())
N,Q=MI()
graph=[[] for i in range(N)]
for i in range(1,N):
  a,b=MI()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
point=[0]*N  
for i in range(Q):
  p,x=MI()
  point[p-1]+=x
def dfs(now,pre=-1):  
  for next in graph[now]:
    if next==pre:
      continue
    point[next]+=point[now]
    dfs(next,now)
dfs(0)
print(*point)

Submission status: Accepted

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

N, Q = map(int, input().split())
root = [[] for i in range(N)]
ans = [0]*N

for i in range(N-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  root[a].append(b)
  root[b].append(a)
  
for i in range(Q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
visit = [False]*N
def dfs(n):
  visit[n] = True
  for go in root[n]:
    if visit[go]:
      continue
    ans[go] += ans[n]
    dfs(go)
    
dfs(0)
print(*ans)

Submission status: Accepted

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

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')


N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    tree[u-1].append(v-1)
    tree[v-1].append(u-1)
# pprint(tree)
queries = []
for _ in range(Q):
    p, x = map(int, input().split())
    queries.append([p-1, x])

counters = [0] * N
for p, x in queries:
    counters[p] += x
# print(counters)


def dfs(dist, v):
    for v_adj in tree[v]:
        if dist[v_adj] == -1:
            dist[v_adj] = 1
            counters[v_adj] += counters[v]
            dfs(dist, v_adj)


dist = [-1] * N
dist[0] = 1
# print(counters)
dfs(dist, 0)
print(*counters)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
inf = 10**17
mod = 10**9+7

n, q = map(int, input().split())
g = [[] for _ in range(n)]
val = [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 _ in range(q):
    p, x = map(int, input().split())
    val[p - 1] += x

seen = [False] * n
deq = deque()
deq.append(0)
while deq:
    v = deq.pop()
    seen[v] = True
    for nv in g[v]:
        if seen[nv]:
            continue
        deq.append(nv)
        val[nv] += val[v]

print(*val)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
n, q = map(int, input().split())
g = [[] for _ in range(n)]
value = [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 _ in range(q):
    p, x = map(int, input().split())
    value[p-1] += x

seen = [False] * n
def dfs(v):
    seen[v] = True
    for nv in g[v]:
        if seen[nv]:
            continue
        value[nv] += value[v]
        dfs(nv)
dfs(0)
print(*value)

Submission status: Accepted

Solution code:
import heapq as hp

n,q=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
pul=[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())
  pul[p-1]+=x


ans=[0]*n
def dfs():
  val=0
  que=[[0,val]]
  done=[0]*n  

  while(que):
    now,val=que.pop()
    if done[now]==1:
      continue
    val+=pul[now]
    ans[now]=val
    done[now]=1

    for i in l[now]:
      if done[i]==0:
        que.append([i,val])

dfs()
print(*ans)

Submission status: Accepted

Solution code:
n,q=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
ans=[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())
  ans[p-1]+=x

def dfs():
  que=[0]
  done=[0]*n  
  done[0]=1
  while(que):
    now=que.pop()

    for i in l[now]:
      if done[i]==0:
        done[i]=1
        que.append(i)
        ans[i]+=ans[now]

dfs()
print(*ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.readline

setrecursionlimit(10**6)

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

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

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

def DFS(v):
    if not checkedlist[v]:
        checkedlist[v] = True
        
        global point
        point += pointlist[v]
        for neighbor in neighborlist[v]:
            DFS(neighbor)
        
        totallist[v] = point
        point -= pointlist[v]
        
totallist = [0]*(N+1)
checkedlist = [False]*(N+1)
point = 0
for i in range(1,N+1):
    if not checkedlist[i]:
        DFS(i)

print(*totallist[1:])

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N, Q = map(int, input().split())
    g = [[] for _ in range(N)]
    score = [0] * N
    seen = [0] * 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):
        a, b = map(int, input().split())
        score[a-1] += b

    q = deque()
    q.append(0)
    while q:
        v = q.pop()
        seen[v] += 1
        for i in g[v]:
            if seen[i]:
                continue
            q.append(i)
            score[i] += score[v]

    print(*score)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n, q = map(int, input().split())
g = [[] for i in range(n)]
k = []
for i in range(n-1):
  a,b = map(int, input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
for i in range(q):
  a,b = map(int, input().split())
  k.append([a-1,b])
m = [-1]*n
m[0] = 0
m1 = [-1]*n
q = deque()
q.append(0)
while len(q):
  d = q.popleft()
  for i in g[d]:
    if m[i] == -1:
      m[i] = m[d]+1
      m1[i] = d
      q.append(i)
kyori = [[] for i in range(max(m)+1)]
for i,j in enumerate(m):
  kyori[j].append(i)
ans= [0]*n
for i,j in k:
  ans[i]+=j
for i in kyori[1:]:
  for j in i:
    ans[j] = ans[j] + ans[m1[j]]
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
from collections import deque
n, q = map(int, input().split())
g = [[] for i in range(n)]
k = []
for i in range(n-1):
  a,b = map(int, input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
for i in range(q):
  a,b = map(int, input().split())
  k.append([a-1,b])
m = [-1]*n
m[0] = 0
m1 = [-1]*n
m1[0] = 0
q = deque()
q.append(0)
while len(q):
  d = q.popleft()
  for i in g[d]:
    if m[i] == -1:
      m[i] = m[d]+1
    if m1[i] == -1:
      m1[i] = d
      q.append(i)
kyori = [[] for i in range(max(m)+1)]
for i,j in enumerate(m):
  kyori[j].append(i)
ans= [0]*n
for i,j in k:
  ans[i]+=j
for i in kyori[1:]:
  for j in i:
    ans[j] = ans[j] + ans[m1[j]]
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
from collections import deque

N,Q=map(int,input().split())
E={i:set() for i in range(1,N+1)}
for _ in range(N-1):
    a,b=map(int,input().split())
    E[a].add(b)
    E[b].add(a)

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

T=[False]*(N+1)
T[1]=True
R=deque([1])

G=[0]*(N+1)
G[1]=F[1]
while R:
    u=R.popleft()
    for v in E[u]:
        if not T[v]:
            G[v]=G[u]+F[v]
            T[v]=True
            R.append(v)

for i in range(1,N+1):
    print(G[i])

Submission status: Accepted

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

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

value_list = [0]*(N+1)

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


from  collections import deque

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

while que:
    parent,me = que.popleft()
    value_list[me]+=value_list[parent]
    for child in graph[me]:
        if child==parent:
            continue
        else:
            que.append((me,child))


print(*value_list[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000)
n,q=map(int,input().split())
e=[[] for _ in range(n)]
cnt=[0]*n
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a-1].append(b-1)
  e[b-1].append(a-1)
for _ in range(q):
  x,y=map(int,input().split())
  cnt[x-1]+=y
vis=[1]*n
queue=[0]
vis[0]=0
while queue:
  now=queue.pop()
  for i in e[now]:
    if vis[i]:
      queue.append(i)
      cnt[i]+=cnt[now]
      vis[i]=0
print(' '.join(map(str,cnt)))

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
V = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)
s = [0]*(n+1)
for j in range(q):
    p,x = map(int,input().split())
    s[p] += x
from collections import deque
q = deque([])
reach = [-1]*(n+1)
q.append(1)
reach[1] = 0
while q:
    x = q.popleft()
    for v in V[x]:
        if reach[v] == -1:
            reach[v] = 0
            s[v] += s[x]
            q.append(v)
for i in range(1,n+1):
    print(s[i],end="")
    print(" ",end="")
print("")

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(300000)

to = [[] for _ in range(200005)]
ans: list


def dfs(v, p=-1):
    global ans
    for u in to[v]:
        if u == p: continue
        ans[u] += ans[v]
        dfs(u, v)
    return


def main():
    N, Q = map(int, input().split())
    for _ in range(N-1):
        a, b = map(int, input().split())
        to[a-1].append(b-1)
        to[b-1].append(a-1)
    global ans
    ans = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        ans[p-1] += x
    dfs(0)
    print(*ans)


if __name__ == "__main__":
    main()

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)]
c = [0] * n
for _ in range(n-1):
    a,b = inpl()
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)
for _ in range(q):
    x,y = inpl()
    c[x-1] += y
seen = [False] * n
seen[0] = True
q = deque()
q.append(0)
while q:
    now = q.popleft()
    for v in g[now]:
        if seen[v]: continue
        c[v] += c[now]
        seen[v] = True
        q.append(v)
print(*c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
# 解法 累積和とdfsを使うと探索が減ってなんかうまくいく．
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)
    E[b-1].append(a)
dic = {}
for _ in range(Q):
    p,x = map(int,input().split())
    if not p-1 in dic:
        dic[p-1] = x
        continue
    dic[p-1] += x

res = [0 for _ in range(N)]
def dfs(p,s,ans):
    global res
    # 終わり条件　最後まで行ったら，つまりE[k] = []になったら.
    # 再帰 累積和を計算して，自分がつながっているノードに接続している
    if s-1 in dic:
        ans += dic[s-1]

    res[s-1] = str(ans)
    if E[s-1] == [p]:
        return
    for e in E[s-1]:
        if e == p:
            continue
        dfs(s,e,ans)
dfs(1,1,0)
print(' '.join(res))

Submission status: Accepted

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

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

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


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


def dfs(n, parent):
    for to in edge[n]:
        if to == parent:
            continue
        vertex[to] += vertex[n]
        dfs(to, n)


dfs(0, -1)
print(*vertex)

Submission status: Accepted

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

adj = [list() 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)

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

stack = [(None,0)]
while stack:
    p,v = stack.pop()
    for u in adj[v]:
        if u != p:
            memo[u] += memo[v]
            stack.append((v,u))

print(*memo)

Submission status: Accepted

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

adj = [list() 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)

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

stack = [(None,0)]
while stack:
    p,v = stack.pop()
    for u in adj[v]:
        if u == p:
            continue
        memo[u] += memo[v]
        stack.append((v,u))

print(*memo)

Submission status: Accepted

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

adj = [list() 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)

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

result = [0]*N
stack = [(None,0)]
while stack:
    p,v = stack.pop()
    result[v] += memo[v]
    for u in adj[v]:
        if u == p:
            continue
        result[u] += result[v]
        stack.append((v,u))

print(*result)

Submission status: Accepted

Solution code:
# 初期入力 readlineだけで1950ms⇒1234ms
#                           PyPy   ⇒867ms
from collections import defaultdict
from collections import deque
import sys
input = sys.stdin.readline
N,Q = (int(x) for x in input().split())

connection ={i:set() for i in range(1,N+1)}
for i in range(1,N):
    a,b = (int(i) for i in input().split())
    connection[a].add(b)
    connection[b].add(a)
nord_point = defaultdict(lambda: 0)
for i in range(1,Q+1):
    a,b = (int(i) for i in input().split())
    nord_point[a] +=b

#BSF

dq =deque()
start =1
dq.append(start)
passed =set()
counter_dic ={i:0 for i in range(1,N+1)}
counter_dic[start] =nord_point[start]
while len(dq) >0:
    now =dq.popleft()
    passed.add(now)
    for next in connection[now]:
        if next not in passed:
            #頂点のカウンター＝親のカウンター ＋ 頂点のポイント
            counter_dic[next] =counter_dic[now] +nord_point[next]
            dq.append(next)
#出力
print(*counter_dic.values())

Submission status: Accepted

Solution code:
# 初期入力 readlineだけで1950ms⇒1234ms
#                           PyPy   ⇒867ms
from collections import defaultdict
from collections import deque
import sys
input = sys.stdin.readline
N,Q = (int(x) for x in input().split())

connection ={i:set() for i in range(1,N+1)}
for i in range(1,N):
    a,b = (int(i) for i in input().split())
    connection[a].add(b)
    connection[b].add(a)
nord_point = defaultdict(lambda: 0)
for i in range(1,Q+1):
    a,b = (int(i) for i in input().split())
    nord_point[a] +=b

#BSF

dq =deque()
start =1
dq.append(start)
passed =set()
counter_dic ={i:0 for i in range(1,N+1)}
counter_dic[start] =nord_point[start]
while len(dq) >0:
    now =dq.popleft()
    passed.add(now)
    for next in connection[now]:
        if next not in passed:
            counter_dic[next] =counter_dic[now] +nord_point[next]
            dq.append(next)
#出力
print(*counter_dic.values())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, Q = map(int, input().split())
rl = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    rl[a].append(b)
    rl[b].append(a)
cnt = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    cnt[p] += x

def dfs(v, pv):
    for next_v in rl[v]:
        if next_v == pv:
            continue
        cnt[next_v] += cnt[v]
        dfs(next_v, v)
dfs(0, -1)
print(*cnt)

Submission status: Accepted

Solution code:
#%%
#%%
import sys
sys.setrecursionlimit(10 ** 9)

N, Q = [int(i) for i in input().split()]
path = [[] for _ in range(N - 1)]
query = [[] for _ in range(Q)]
for i in range(N - 1):
    path[i] = [int(i) - 1 for i in input().split()]
for i in range(Q):
    query[i] = [int(i) for i in input().split()]
    query[i][0] -= 1
#%%
add = [0] * N
ans = [0] * N
for i, j in query:
    add[i] += j
    
children = [[]  for _ in range(N)]
for i, j in path:
    children[i].append(j)
    children[j].append(i)
    
def DFS(id, parent, value):
    value += add[id]
    ans[id] = value
    for i in children[id]:
        if i == parent:
            continue
        DFS(i, id, value)
    
DFS(0, -1, 0)

for i in ans:
    print(i, end=" ")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline #入力行数が多いから高速化が必要
sys.setrecursionlimit(int(1E+7))
#小さすぎるデフォルト値を変え再起処理の上限を引き上げる(だいたい1000やから)
def main():
    n ,q = map(int,input().split())
    link = [[]  for i in range(n + 1)]
    for  i in range(n - 1):
        a,b = map(int,input().split())
        link[a].append(b)
        link[b].append(a)
    #print(link)
    V = [0] * (n + 1)
    for j in range(q):
        p, x = map(int,input().split())
        V[p] += x
    #print(V)

    def dfs(i, parent, acc): #深さ優先探索なり
        V[i] += acc #親ノードまでの累積値を加算
        for j in link[i]:
            if j != parent: # 親ノードを追加しない
                dfs(j, i, V[i])

    cur = 1
    parent = 0
    acc = 0
    dfs(cur, parent, acc) #親ノードを０としてスタート
    V = [str(i) for i in V]
    print(" ".join(V[1:]))#数字はjoinつかえないので

if __name__ == "__main__":
    main()

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)]
# The directly connecting nodes of each node are written in "graph".
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)
    # graph can be

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

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

dfs(0)
print(*point)

Submission status: Accepted

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

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

score=[0]*n
score[0]=px[0]
from collections import deque
que=deque([0])
while que:
    s=que.popleft()
    for g in es[s]:
        if rank[g]==-1:
            rank[g]=rank[s]+1
            score[g]=score[s]+px[g]
            que.append(g)
print(*score)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
n, q = map(int, input().split())
a = [0 for i in range(n - 1)]
b = [0 for i in range(n - 1)]
p = [0 for i in range(q)]
x = [0 for i in range(q)]
for i in range(n - 1):
    a[i], b[i] = map(int, input().split())
for i in range(q):
    p[i], x[i] = map(int, input().split())

graph = [[] for i in range(n)]
for i in range(n - 1):
    graph[a[i] - 1].append(b[i] - 1)
    graph[b[i] - 1].append(a[i] - 1)
# print("tree =", tree)

cnt = [0 for i in range(n)]
for i in range(q):
    cnt[p[i] - 1] += x[i]
# print("cnt =", cnt)   

ans = [0 for i in range(n)]
queue = deque([[0, 0]])
visited = [0 for i in range(n)]
while queue:
    node, total = queue.popleft()
    if visited[node] == 1:
        continue
    visited[node] = 1
    total += cnt[node]
    ans[node] = total
    for i in graph[node]:
        queue.append([i, total])
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
import sys
N,Q = map(int,input().split())
graph = [[] for _ in range(N)]
#グラフをリストで表現
for _ in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)#リストの番号で頂点を表示するため-1
    graph[b-1].append(a-1)
point = [0]*N
for _ in range(Q):
    a,b = map(int,input().split())
    point[a-1] += b#根にあたる部分にだけコストをプラス


#再帰定義
def dfs(now, prev = -1):#prev,now,nextの三段階を扱う
    for next in graph[now]:#今見ている頂点に連結されているものを見る
        if next == prev:#親だったら飛ばす
            continue
        point[next] += point[now]#子の得点をプラス
        dfs(next,now)#nextが親だけになると自分を呼ぶ前に飛ばされて終わる

dfs(0)#根頂点を指定してスタート
print(*point)

Submission status: Accepted

Solution code:
from collections import deque
# import os
# import io
# input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
# import sys
# input = sys.stdin.readline


def main():
    n, q = map(int, input().split())
    node = [[]for _ in range(n)]
    looked = [1] * n
    for i in range(n - 1):
        a, b = map(int, input().split())
        node[b - 1].append(a - 1)
        node[a - 1].append(b - 1)
    counter = [0] * n
    for i in range(q):
        p, x = map(int, input().split())
        counter[p - 1] += x
    queue = deque([0])
    looked[0] = 0
    while queue:
        now = queue.pop()
        for i in node[now]:
            if looked[i]:
                queue.append(i)
                counter[i] += counter[now]
                looked[i] = 0
    print(*counter)

main()

Submission status: Accepted

Solution code:
from collections import deque
# import os
# import io
# input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import sys
input = sys.stdin.readline


def main():
    n, q = map(int, input().split())
    node = [[]for _ in range(n)]
    looked = [1] * n
    for i in range(n - 1):
        a, b = map(int, input().split())
        node[b - 1].append(a - 1)
        node[a - 1].append(b - 1)
    counter = [0] * n
    for i in range(q):
        p, x = map(int, input().split())
        counter[p - 1] += x
    queue = deque([0])
    looked[0] = 0
    while queue:
        now = queue.pop()
        for i in node[now]:
            if looked[i]:
                queue.append(i)
                counter[i] += counter[now]
                looked[i] = 0
    print(*counter)

main()

Submission status: Accepted

Solution code:
from collections import deque
import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


def main():
    n, q = map(int, input().split())
    node = [[]for _ in range(n)]
    looked = [1] * n
    for i in range(n - 1):
        a, b = map(int, input().split())
        node[b - 1].append(a - 1)
        node[a - 1].append(b - 1)
    counter = [0] * n
    for i in range(q):
        p, x = map(int, input().split())
        counter[p - 1] += x
    queue = deque([0])
    looked[0] = 0
    while queue:
        now = queue.pop()
        for i in node[now]:
            if looked[i]:
                queue.append(i)
                counter[i] += counter[now]
                looked[i] = 0
    print(*counter)

main()

Submission status: Accepted

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

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

for i in range(N-1):
  a, b = map(int, input().split())
  T[a-1].append(b)
  T[b-1].append(a)
PX = [list(map(int, input().split())) for _ in range(Q)]
C = [0 for _ in range(N)]
for p, x in PX:
  C[p-1] += x

def dfs(node, previousNode, previousPoint):
  C[node-1] += previousPoint
  for next in T[node-1]:
    if next != 1 and next != previousNode:
      dfs(next, node, C[node-1])
dfs(1, 0, 0)
print(" ".join(map(str, C)))