Problem:


Score : 400 points

Problem Statement

Given is a rooted tree with N vertices numbered 1 to N.
The root is Vertex 1, and the i-th edge (1 \leq i \leq N - 1) connects Vertex a_i and b_i.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0.

Now, the following Q operations will be performed:

Operation j (1 \leq j \leq Q): Increment by x_j the counter on every vertex contained in the subtree rooted at Vertex p_j.

Find the value of the counter on each vertex after all operations.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq Q \leq 2 \times 10^5

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

Sample Input 1

4 3
1 2
2 3
2 4
2 10
1 100
3 1

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:

Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.

Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.

Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Sample Input 2

6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10

Sample Output 2

20 20 20 20 20 20



Sample input:
4 3
1 2
2 3
2 4
2 10
1 100
3 1


Sample output:
100 110 111 110

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
def main():
    class Tree():
        def __init__(self, n, root, connects):
            self._root = root
            self._connects = connects
            self._parents = [0] * n
            self._parents[root] = None
            self._children = [0] * n
            self._children[self._root] = connects[self._root]
            self.make_tree(self._root)

        def make_tree(self, node):
            for child in self._children[node]:
                self._parents[child] = node
                self._children[child] = [c for c in self._connects[child] if c != node]
                if self._children[child] != []:
                    self.make_tree(child)

        def parents(self, node):
            return self._parents[node]

        def children(self, node):
            return self._children[node]

    def add_subtree(i):
        for c in t.children(i):
            ans[c] += ans[i]
            add_subtree(c)

    n, q = map(int, input().split())
    G = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        G[a].append(b)
        G[b].append(a)
    t = Tree(n, root = 0, connects = G)
    ans = [0] * n
    for _ in range(q):
        p, x = map(int, input().split())
        ans[p - 1] += x
    add_subtree(0)
    print(' '.join(list(map(str, ans))))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N, Q = map(int, input().split())
edge = [[] for _ in range(N)]
nord = [0]*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)
for i in range(Q):
    a, b = map(int, input().split())
    nord[a-1] += b

d = deque()
d.append(0)
Done = [-1]*N

while d:
    x = d.popleft()
    for i in edge[x]:
        if Done[i] != -1:
            continue
        nord[i] += nord[x]
        d.append(i)
    Done[x] += 1

for i in nord:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque
N, Q = map(int, input().split())
G = [[] for _ in range(N + 1)]
c = [0] * (N + 1)
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

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

q = deque([1])
seen = [0] * (N + 1)
while q:
    now = q.popleft()
    seen[now] = 1
    for u in G[now]:
        if seen[u]:
            continue
        q.append(u)
        c[u] += c[now]

print(*c[1:])

Submission status: Accepted

Solution code:
from collections import deque
n,q = map(int,input().split())
l = [[] for i in range(n+1)]
pts = [0]*(n+1)
for _ in range(n-1):
  a,b = map(int,input().split())
  l[a].append(b)
  l[b].append(a)
for _ in range(q):
  p,x = map(int,input().split())
  pts[p] += x
Q = deque()
Q.append(1)
ans = [0]*(n+1)
vst = [0]*(n+1)
while Q:
  temp = Q.popleft()
  for n in l[temp]:
    if vst[n]:
      continue
    ans[n] = ans[temp] + pts[temp]
    Q.append(n)
  ans[temp] += pts[temp]
  vst[temp] = 1
print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque

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

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

def bfs(s):
    q = deque([s])
    seen = [False] * N
    
    while(q):
        node = q.popleft()
        seen[node] = True
        for nx in G[node]:
            if seen[nx] == False:
                q.append(nx)
                ans[nx] += (p[nx] + ans[node])

bfs(0)
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,q=map(int,input().split())

d=[[0] for _ in range(n+1)]
d1=[0 for _ in range(n+1)]

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

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

#d 関係性 d1価
vi=[-1 for _ in range(n+1)]

def dfs(x,i):
  vi[x]=i+d1[x]
  for m in d[x]:
    if vi[m]==-1 and m!=0:
      dfs(m,vi[x])    

dfs(1,0)


print(*vi[1:])

Submission status: Accepted

Solution code:
from queue import Queue
def bfs(target, graph, scores):
    visited = [False]*len(graph)
    que = Queue()
    que.put(target)
    visited[target] = True
    while not que.empty():
        root = que.get()
        for dst in graph[root]:
            if visited[dst] is False:
                visited[dst] = True
                que.put(dst)
                scores[dst] += scores[root] 
    return scores 
n, q = map(int, input().split())
graph = {i:[] for i in range(0, n)}
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

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

ans = bfs(0, graph, scores)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def dfs(tree, p, cnt, visited):
    visited[p] = True
    cnt_here = cnt[p]
    for c in tree.get(p):
        if visited[c]:
            continue
        cnt[c] += cnt_here
        dfs(tree, c, cnt, visited)


def main():
    input = sys.stdin.buffer.readline
    sys.setrecursionlimit(10 ** 9)
    n, q = map(int, input().split())
    tree = defaultdict(list)
    for _ in range(n - 1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    tree = dict(tree)
    cnt = [0] * (n + 1)

    for _ in range(q):
        p, x = map(int, input().split())
        cnt[p] += x
    visited = [False] * (n + 1)
    dfs(tree, 1, cnt, visited)
    print(*cnt[1:])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
N, Q = map(int, input().split())

ARR = []

for i in range(N-1):
    ARR.append(list(map(int, input().split())))

BRR = []

for i in range(Q):
    BRR.append(list(map(int, input().split())))


def prepare(n, q, arr, brr):
    nodePoints = [0 for i in range(n)]
    for i in range(q):
        nodeIndex = brr[i][0] - 1
        nodePoints[nodeIndex] += brr[i][1]

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

    for i in range(n - 1):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodePoints


nodes, nodePoints = prepare(N, Q, ARR, BRR)


def dfs(currentNode, nodes, parentNode=-1, parentPoint=0):
    nodePoints[currentNode] = nodePoints[currentNode] + parentPoint
    childNodes = nodes[currentNode]
    for childNode in childNodes:
        if childNode == parentNode:
            continue
        dfs(childNode, nodes, currentNode, nodePoints[currentNode])


dfs(0, nodes)

print(" ".join([str(nodePoints[i]) for i in range(N)]))

Submission status: Accepted

Solution code:
import collections

n,q=map(int,input().split())
cnt=[0]*(n+1)
g=[[] for _ in range(n+1)]
for _ in range(n-1): #木グラフの隣接リストを作成
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
for _ in range(q): #各頂点についてcount[v]を計算
 v,val=map(int,input().split())
 cnt[v]+=val
q=collections.deque()
q.append(1) #DFSのスタックによる実装、まずスタックに始点1を積む
checked=[0]*(n+1) #各頂点を見たかどうかのフラグを持っておく
while q:
 v=q.pop()
 checked[v]=1 #頂点を見たかどうかのフラグを更新する
 for u in g[v]:
   if checked[u]==1: #vの子ノードuについて、まだ見ていない頂点であればcount[u]をcount[u]+=count[v]として更新する
     continue
   cnt[u]+=cnt[v]
   q.append(u) #スタックに子ノードuを積む
print(*cnt[1:]) #各頂点のcountが答えとなる

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]
AB = (tuple(map(int, input().split())) for _ in range(n-1))
PX = (tuple(map(int, input().split())) for _ in range(q))

for a,b in AB:
  Tree[a].append(b)
  Tree[b].append(a)
  
for p,x in PX:
  Counter[p] += x

P = [-1]*(n+1)

nodes = [1]
while nodes:
  parent = nodes.pop()
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter[1:])

Submission status: Accepted

Solution code:
from collections import deque
N, Q = map(int, input().split())
pathes = []
for _ in range(N-1):
    a, b = map(int, input().split())
    pathes.append((a, b))
childs = [[] for i in range(N+1)]
for a, b in pathes:
    childs[a].append(b)
    childs[b].append(a)
cnt = [0]*(N+1)
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x
closed = [False]*(N+1)
nodes = deque()
nodes.append(1)
while len(nodes) != 0:
    node = nodes.popleft()
    closed[node] = True
    for c in childs[node]:
        if closed[c]:
            continue
        nodes.append(c)
        cnt[c] += cnt[node]
for i in range(1, N+1):
    print(cnt[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def val_add(i,con,val):
    if con[i] :
        for j in con[i]:
            val[j]+=val[i]
            val_add(j,con,val)

def tree(i,con):
    if not con[i]: pass
    else :
        for j in con[i]:
            con[j].remove(i)
            tree(j,con)

def main():
    n,q=map(int,input().split())
    con=[[] for _ in range(n)]
    val=[0]*n
    for _ in range(n-1):
        a,b=map(int,input().split())
        con[a-1].append(b-1)
        con[b-1].append(a-1)

    tree(0,con)

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

    val_add(0,con,val)


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

main()

Submission status: Accepted

Solution code:
from collections import defaultdict

N, Q = map(int, input().split())
edges = defaultdict(set)
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a].add(b)
    edges[b].add(a)
PX = []
for _ in range(Q):
    PX.append(list(map(int, input().split())))

direct_score = defaultdict(int)
final_score = {}

for px in PX:
    direct_score[px[0]] += px[1]

stack = [(1, 0)]

while stack:
    node, score = stack.pop()
    if node in final_score:
        continue
    score += direct_score[node]
    final_score[node] = score
    for child in edges[node]:
        stack.append((child, score))

print(' '.join([str(final_score[i]) for i in range(1, N+1)]))

Submission status: Accepted

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

for i in range(N-1):
    f, t = map(int, input().split())
    graph[f].append(t)
    graph[t].append(f)

px = [0] * (N+1)

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

v = [0] * (N+1)
q = [[1, 0]]

while q:
    x, parent = q.pop()
    v[x] += v[parent]
    v[x] += px[x]
    for y in graph[x]:
        if y == parent:
            continue
        q.append([y, x])

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

Submission status: Accepted

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


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

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

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

  # solve
  ans = [0]*(N+1)
  visited = set()
  # temp = PX[1]
  # S = [1] # Stack
  # S = deque([1])

  # while len(S):
  #   now = S[-1]
  #   visited.add(now)

  #   for next_ in G[now]:
  #     if next_ not in visited:
  #       S.append(next_)
  #       temp += PX[next_]
  #       break
  #   else:
  #     S.pop()
  #     ans[now] = temp
  #     temp -= PX[now]

  def dfs(now, sum_):
    visited.add(now)
    for next_ in G[now]:
      if next_ not in visited:
        sum_ += PX[next_]
        sum_ = dfs(next_, sum_)

    ans[now] = sum_
    sum_ -= PX[now]
    return sum_

  dfs(1, PX[1])

  print(*ans[1:], sep=' ')


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
#初期データ、構造
N,Q = (int(x) for x in input().split())
# 隣接リスト表現
connection ={i:set() for i in range(1,N+1)}
for _ in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b)
    connection[b].add(a)

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

def DFS(now,prev = -1):
    for next in connection[now]:
        # 親へのエッジはスキップ
        if next == prev:
            continue
        point[next] += point[now] 
        DFS(next,now)

DFS(1)
print(*point.values())

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,q = map(int,ipt().split())
    way = [[] for i in range(n+1)]
    for i in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)
    pl = [0]*(n+1)
    for i in range(q):
        p,x = map(int,ipt().split())
        pl[p] += x
    ans = [-1]*(n+1)
    ans[0] = 0
    ans[1] = pl[1]
    q = [(1,0)]

    while q:
        qi,qp = q.pop()
        qa = ans[qi]
        for j in way[qi]:
            if j == qp:
                continue
            ans[j] = qa+pl[j]
            q.append((j,qi))

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

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, q = map(int,input().split())
graph = [[] for i in range(n+1)]
for i in range(n-1):
    f, t = map(int,input().split())
    graph[f].append(t)
    graph[t].append(f)

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

v = [0] * (n+1)
q = [[1,0]]
while q:
    x, parent = q.pop()
    v[x] += v[parent]
    v[x] += px[x]
    for y in graph[x]:
        if y == parent:
            continue
        q.append([y,x])

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

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10 ** 6)

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

graph   = [ [] for _ in range(N) ]
queries = { p: 0 for p in range(N) }

for _ in range(N - 1):
    a, b = map(lambda x: int(x) - 1, input().split())

    graph[a].append(b)
    graph[b].append(a)

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

    queries[p - 1] += x

answer = [ 0 ] * N

def dfs(p, p_before, acc):
    acc += queries[p]

    answer[p] = acc

    for child in graph[p]:
        if child == p_before:
            continue

        dfs(child, p, acc)

dfs(0, -1, 0)

print(*answer)

Submission status: Accepted

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

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

#木構造の構築
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

counter = [0]*n
for i in range(q):
    p,x = map(int,input().split())
    counter[p-1] += x#根の部分にカウント

def dfs(now,prev):
    for next in edges[now]:#nowに直接つながる子を順番に参照
        if next == prev: #edgeでは子と親の関係が明示されていないので親につながる情報は無視
            continue
        counter[next] += counter[now]
        dfs(next,now)#行きがかり順にカウント

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

Submission status: Accepted

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

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

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

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

def dfs(now,prev):
    for next in edges[now]:
        if next == prev:
            continue
        counter[next] += counter[now]
        dfs(next,now)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, Q, ABs, PXs):
    tree_map = [[] for _ in range(N + 1)]
    for a, b in ABs:
        tree_map[a].append(b)
        tree_map[b].append(a)

    ans = [0 for _ in range(N + 1)]
    for p, x in PXs:
        ans[p] += x

    def dfs(v, r):  # vertex, root
        ans[v] += ans[r]
        for tm in tree_map[v]:
            if tm == r:
                continue
            dfs(tm, v)

    dfs(1, 0)

    for a in ans[1:]:
        print(a)


if __name__ == '__main__':
    N, Q = map(int, input().split())
    ABs = [[int(i) for i in input().split()] for _ in range(N - 1)]
    PXs = [[int(i) for i in input().split()] for _ in range(Q)]
    solve(N, Q, ABs, PXs)

Submission status: Accepted

Solution code:
def resolve():
    N, Q = list(map(int, input().split()))
    adjs = [set() for _ in range(N)]
    for _ in range(N-1):
        src, dst = list(map(int, input().split()))
        adjs[src-1].add(dst-1)
        adjs[dst-1].add(src-1)
    costs = [0 for _ in range(N)]
    for i in range(Q):
        idx, cost = list(map(int, input().split()))
        idx = idx - 1
        costs[idx] += cost
    
    q = [0]
    visited = set()
    while q:
        node = q.pop()
        for nxt in adjs[node]:
            if nxt in visited:
                continue
            costs[nxt] += costs[node]
            q.append(nxt)
        visited.add(node)
    print(*costs)


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000000)
n,q = map(int, input().split())
graph1 = [[] for _ in range(n+1)]
graph2 = [[] for _ in range(n+1)]
ans=[0]*(n+1)
reached=[0]*(n+1)
def main():
  for i in range(n-1):
    a,b = map(int, input().split())
    graph1[a].append(b)
    graph2[b].append(a)

  for i in range(q):
    p,x = map(int, input().split())
    ans[p] += x
  dfs(1) 
  print(' '.join([str(i) for i in ans[1:]]))

def dfs(i):
  if reached[i] == 1:
    return
  reached[i] = 1
  for g in graph1[i], graph2[i]:
    for j in g:
      if reached[j] == 1:
        continue
      ans[j] += ans[i]
      dfs(j)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
sys.setrecursionlimit(4100000)

def dfs(node):
  visited[node-1] = True
  
  for next_node in tree[node]:
    if visited[next_node-1]:
      continue
    counter[next_node-1] += counter[node-1]
    dfs(next_node)

N, Q = map(int, input().split())
tree = dd(list)
visited = [False] * N
counter = [0] * N
operation = []
for _ in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b) 
  tree[b].append(a) 
for _ in range(Q):
  operation.append(tuple(map(int, input().split())))
  
for p, x in operation:
  counter[p-1] += x
dfs(1)
print(*counter)

Submission status: Accepted

Solution code:
from collections import deque
def MI(): return map(int, input().split())
N,Q=MI()
graph=[[] for i in range(N)]
Point=[0]*N
for i in range(N-1):
  a,b=MI()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
for i in range(Q):
  p,x=MI()
  Point[p-1]+=x
que=deque([])
que.append(0)
check=[0]*N
while que:
  v=que.pop()
  check[v]=1
  for u in graph[v]:
    if check[u]!=1:
      #continue
      Point[u]+=Point[v]
      que.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()
Edge=[[] for _ in range(N)]
Point=[0]*N

for i in range(N-1):
  a,b=MI()
  Edge[a-1].append(b-1)
  Edge[b-1].append(a-1)

for i in range(Q):
  p,x=MI()
  Point[p-1]+=x

def dfs(now,pre=-1):
  for nxt in Edge[now]:
    if nxt==pre:
      continue
    Point[nxt]+=Point[now]
    dfs(nxt,now)
dfs(0)
print(*Point)

Submission status: Accepted

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

import sys
input = sys.stdin.readline
import marshal


class Graph:
    def __init__(self, n, dictated=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [[] for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append(y)
        if self.dictated == False:
            self.edges[y].append(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = list(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = list(adjacent_list)

    def dfs2(self, info, start, goal=-1, time=0, save=False):
        """
        :param info: 各頂点の付加情報
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: ゴール地点までの距離。存在しなければ -1
        """

        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        if self.destroy:
            edge2 = self.edges
        else:
            edge2 = marshal.loads(marshal.dumps(self.edges))

        p, t = start, time
        self.parent[p] = -2
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                if q == goal:
                    """ ゴール時の処理"""
                    # return t + 1
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                info[q] += info[p]
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """

                """"""""""""""""""""
        return info


######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, Q: クエリの数
M = N-1

graph = Graph(N, dictated=False, destroy=True)

for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x,y)

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

print(*graph.dfs2(info, start=1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
edge=[[] for i in range(n)]
a=[0]*n
b=[0]*n
for i in range(n-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
for i in range(q):
    p,x=map(int,input().split())
    a[p-1]+=x
def dfs(node,tmp):
    a[node]+=tmp
    b[node]=1
    for i in edge[node]:
        if b[i]==0:
            dfs(i,a[node])
dfs(0,0)
print(*a)

Submission status: Accepted

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

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

done=[False]*n
q=deque([])
q.append(0)
done[0]=True
while q:
  v=q.popleft()
  done[v]=True
  for c in edge[v]:
    if done[c]==False:
      ans[c]+=ans[v]
      q.append(c)
    
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4000)

def dfs(now):
  v[now]=0
  for i in edge[now]:
    if v[i]:
      point[i]+=point[now]
      dfs(i)

n,q=map(int,input().split())
edge=[[] for _ in range(n)]
point=[0]*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)
for i in range(q):
  p,x=map(int,input().split())
  point[p-1]+=x
v=[1]*n
queue=[0]
v[0]=0
while queue:
  now=queue.pop()
  for i in edge[now]:
    if v[i]:
      v[i]=0
      queue.append(i)
      point[i]+=point[now]
print(*point)

Submission status: Accepted

Solution code:
#<D>
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
def main():
    N, Q = map(int ,input().split())
    link = [[] for n in range(N + 1)]
    for n in range(N - 1):
        a, b = map(int, input().split())
        link[a].append(b)
        link[b].append(a)
    V = [0] * (N + 1)
    for q in range(Q):
        p, x = map(int, input().split())
        V[p] += x
    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:]))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

n,q = map(int,input().split())
ab = [list(map(int,input().split()))for i in range(n-1)]
px = [list(map(int,input().split()))for i in range(q)]

def dfs(m):
    for i in range(len(adj[m])):
        if depth[adj[m][i]] == float('inf'):
            depth[adj[m][i]] = depth[m] + 1
            point[adj[m][i]] += point[m]
            dfs(adj[m][i])


point = [0]*(n+1)
depth = [float('inf')]*(n+1)
adj = [[]for _ in range(n+1)]

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

for i in range(q):
    point[px[i][0]] += px[i][1]

depth[1] = 1
dfs(1)

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










'''
n,q = map(int,input().split())
ab = [list(map(int,input().split()))for i in range(n-1)]
px = [list(map(int,input().split()))for i in range(q)]

def dfs(m):
    if m in vdic:
        for i in range(len(vdic[m])):
            point[vdic[m][i]] += point[m]
            dfs(vdic[m][i])

point = [0]*(n+1)

vdic = {}
for i in range(n-1):
    if ab[i][0] not in vdic:
        vdic[ab[i][0]] = []
    vdic[ab[i][0]].append(ab[i][1])

for i in range(q):
    point[px[i][0]] += px[i][1]

dfs(1)

for i in range(1,len(point)):
    print(point[i],end = ' ')

'''

Submission status: Accepted

Solution code:
import collections
def MI(): return map(int, input().split())
N,Q=MI()
Edge=[[] for _ in range(N)]
Point=[0]*(N)
for _ in range(N-1):
  a,b=MI()
  Edge[a-1].append(b-1)
  Edge[b-1].append(a-1)
for _ in range(Q):
  p,x=MI()
  Point[p-1]+=x
check=[0]*N
que=collections.deque()
que.append(0)
while que:
  v=que.popleft()
  check[v]=1
  for u in Edge[v]:
    if check[u]==1:
      continue    
    Point[u]+=Point[v]
    que.append(u)  
'''
def dfs(now,pre=-1):
  for nxt in Edge[now]:
    if nxt==pre:
      continue
    Point[nxt]+=Point[now]
    #print(*Point)
    dfs(nxt,now)
dfs(0)
'''
print(*Point)

Submission status: Accepted

Solution code:
import collections
def MI(): return map(int, input().split())
N,Q=MI()
Edge=[[] for _ in range(N)]
Point=[0]*(N)
for _ in range(N-1):
  a,b=MI()
  Edge[a-1].append(b-1)
  Edge[b-1].append(a-1)
for _ in range(Q):
  p,x=MI()
  Point[p-1]+=x
check=[0]*N
que=collections.deque()
que.append(0)
while que:
  v=que.pop()
  check[v]=1
  for u in Edge[v]:
    if check[u]==1:
      continue    
    Point[u]+=Point[v]
    que.append(u)  
'''
def dfs(now,pre=-1):
  for nxt in Edge[now]:
    if nxt==pre:
      continue
    Point[nxt]+=Point[now]
    #print(*Point)
    dfs(nxt,now)
dfs(0)
'''
print(*Point)

Submission status: Accepted

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

def MI(): return map(int, input().split())

N,Q=MI()
Edge=[[] for _ in range(N)]
Point=[0]*(N)
for _ in range(N-1):
  a,b=MI()
  Edge[a-1].append(b-1)
  Edge[b-1].append(a-1)
for _ in range(Q):
  p,x=MI()
  Point[p-1]+=x
  #print(p,Point[p-1])
  
def dfs(now,pre=-1):
  for nxt in Edge[now]:
    if nxt==pre:
      continue
    Point[nxt]+=Point[now]
    #print(*Point)
    dfs(nxt,now)
dfs(0)
print(*Point)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
G = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(lambda x: x-1, map(int, input().split()))
    G[a].append(b)
    G[b].append(a)

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

def dfs(v, pre=-1):  
    for nx in G[v]:
        if nx==pre:
            continue
        ans[nx] += ans[v]
        dfs(nx,v)
dfs(0)
print(*ans)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
cnt=[0]*(n+1) #答えのリスト
lst=[[] for _ in range(n+1)] #連結リスト

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

for i in range(q):
    a,val=map(int,input().split())
    cnt[a]+=val

stack=[1]
visited=[None]*(n+1)
visited[1]=1
while stack:
    item=stack.pop()
    for i in lst[item]:
        if visited[i]==1:
            continue
        visited[i]=1
        stack.append(i)
        cnt[i]+=cnt[item]

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