Problem:


Score : 400 points

Problem Statement

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

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

Now, the following Q operations will be performed:

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

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

Constraints

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

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

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

100 110 111 110

The tree in this input is as follows:

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

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

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

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

Sample Input 2

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

Sample Output 2

20 20 20 20 20 20



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


Sample output:
100 110 111 110

Submission status: Accepted

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

n, q = map(int, input().split())
t = [[] for i in range(n)]# 空の2次元配列を作る
for i in range(n-1):
    a, b = map(int, input().split())
    t[a - 1].append(b -1)
    t[b - 1].append(a -1)
# 配列は０から始まるから１、２、３、４の木を０、１、２、３として扱ってる
# 配列の０番目（つまり頂点０）が持つ値がその頂点が持つリンクとなる

v = [0] * (n) #空の配列を作る
for j in  range(q):# 0からqまで
    a, b = map(int, input().split())
    v[a-1] += b


def csum(now, bef):  # 累積和
    for nxt in t[now]:
        if nxt != bef:
            v[nxt] += v[now]
            csum(nxt, now)

csum(0, -1)
print(*v)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

c = [0] * (N + 1)

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

ans = [0] * (N + 1)

go = deque([1])
went = [False] * (N + 1)
went[1] = True
ans[1] = c[1]
while len(go) > 0:
    now = go.popleft()
    for child in tree[now]:
        if went[child]:
            continue
        go.append(child)
        ans[child] = ans[now] + c[child]
        went[child] = True

print(*ans[1:])

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
    
q = [(1,0)]
while q:
    x,parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y,x))
 
answer = ' '.join(map(str,value[1:]))
print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input=sys.stdin.readline
n,q=map(int,input().split())
edges=[[] for i in range(n)]
cnt=[0]*n
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1;b-=1
  edges[a].append(b)
  edges[b].append(a)
for i in range(q):
  x,c=map(int,input().split())
  x-=1
  cnt[x]+=c
visited=[False]*n
check=deque([0])
visited[0]=True
while check:
  a=check.popleft()
  for i in edges[a]:
    if visited[i]==True:continue
    check.append(i)
    visited[i]=True
    cnt[i]+=cnt[a]
print(" ".join(map(str,cnt)))

Submission status: Accepted

Solution code:

#WA aiはbiの親であるとは限らない
#有向グラフかと思ったけど違かった無向グラフ
#訪れたことのあるとこにはフラグをたてる
#グラフの隣接リストによる実装

import collections

class edge:
#    def __init__(self,to,cost):
    def __init__(self,to):
        self.to = to
        #self.cost = cost

#N個の頂点、N-1個の辺、Q操作回数
N,Q = map(int,(input().split()))
 
#添字と入力が1ずれるので注意
#グラフ (iがグラフの頂点、G[i]に隣接するグラフが入っている)
G = [ [] for row in range(N)]
for i in range(N-1):
    #sからtへ辺を張る
    s,t = map(int,input().split())
    #添字調整
    s -= 1
    t -= 1
    G[s].append(edge(t))
    #無向グラフなので逆にも張る
    G[t].append(edge(s))
 
#各頂点以下に加算する重み
ans = [0] * N
for i in range(Q):
    #頂点pにxの重みをつける
    p,x = map(int,input().split())
    #添字調整
    p -= 1
    ans[p] += x

#DFSのスタックによる実装、まずスタックに始点1を積む
q=collections.deque()
q.append(0) 

#訪れたことのあるとこにはいかないようにチェックする
check = [0] * N

while q:
    v=q.pop()
    #頂点を見たかどうかのフラグを更新する
    check[v]=1 
    for i in G[v]:
        #vの子ノードuについて、まだ見ていない頂点であればcount[u]をcount[u]+=count[v]として更新する
        if check[i.to]==1: 
            continue
        ans[i.to]+=ans[v]
        q.append(i.to) #スタックに子ノードuを積む
 
print(" ".join(map(str,ans)))

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:
from collections import deque
N, Q = map(int, input().split())

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

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

c = [0] * (N+1)

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


ans = [0] * (N+1)

go = deque([1])
went = [False] * (N+1)
went[1] = True
ans[1] = c[1]
while len(go) > 0:
    now = go.popleft()
    for child in tree[now]:
        if went[child]:
            continue
        go.append(child)
        ans[child] = ans[now] + c[child]
        went[child] = True

print(*ans[1:])

Submission status: Accepted

Solution code:
tmp = list(map(int, (input().split())))
n = tmp[0]
q = tmp[1]

#edge = defaultdict(list)
edge = [[] for i in range(n+1)]
fixed = [False] * (n + 1)
fixed[1] = True
point = [0] * (n + 1)

for i in range(1, n):
  tmp = list(map(int, (input().split())))
  edge[tmp[0]].append(tmp[1])
  edge[tmp[1]].append(tmp[0])

for i in range(1, q+1):
  tmp = list(map(int, (input().split())))
  point[tmp[0]] += tmp[1]

que = []
que += edge[1]
frm = 1

while len(que) != 0:
  cur = que.pop()
  for i in edge[cur]:
    if fixed[i]:
      point[cur] += point[i]
    else:
      que.append(i)
  fixed[cur] = True

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

Submission status: Accepted

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

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

s = [(0, -1)]
while s:
    i, p = s.pop()
    for j in links[i]:
        if j == p:
            continue
        values[j] += values[i]
        s.append((j, i))
print(*values)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

L=[list(map(int,input().split())) for i in range(q)]
ctL=[0]*n
for i in range(q):
  ctL[L[i][0]-1]+=L[i][1]

def bfs(v):
  distance=[-1]*n
  distance[v]=ctL[v]
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            distance[connection[next[i]][j]]=distance[next[i]]+ctL[connection[next[i]][j]]
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

x=bfs(0)
for i in range(n):
  x[i]=str(x[i])
print(' '.join(x))

Submission status: Accepted

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

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

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

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

def dsf(ci,pi):
  for i in t[ci]:
    if i != pi:
      c[i] += c[ci]
      dsf(i, ci)

dsf(0,-1)

print(*c)

Submission status: Accepted

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

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)
    edge[b-1].append(a)

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


def dfs(now, bef):
    for nxt in edge[now-1]:
        if nxt != bef:
            cnt[nxt-1] += cnt[now-1]
            dfs(nxt, now)


dfs(1, -1)
print(*cnt)

Submission status: Accepted

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


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)
    edge[b-1].append(a)

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


def dfs(now, bef):
    for nxt in edge[now-1]:
        if nxt != bef:
            cnt[nxt-1] += cnt[now-1]
            dfs(nxt, now)


dfs(1, -1)
print(*cnt)

Submission status: Accepted

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


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


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

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


def dfs(p, par):
  for i in ab[p-1]:
    if i != par:
      P[i-1] += P[p-1]
      dfs(i, p)


dfs(1, -12345)
print(" ".join(map(str, P)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
def solve():
    n, q = map(int, input().split())


    ab = [tuple(map(int, input().split())) for i in range(n-1)]
    px = [tuple(map(int, input().split())) for i in range(q)]
    # ab.sort(key=lambda tup:(tup[0],tup[1]))

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

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


    stack = [(1, 0)]

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


    print(*cnt[1:])
    return

def main():
    solve()
    return
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n, q = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(list)
    for i in range(n-1):
        a, b = list(map(int, input().rstrip('\n').split()))
        d[a] += [b]
        d[b] += [a]

    score = collections.defaultdict(int)
    for i in range(q):
        p, x = list(map(int, input().rstrip('\n').split()))
        score[p] += x

    ql = collections.deque()
    ql.append(1)
    fq = collections.defaultdict(list)
    fq[1]
    while True:
        if len(ql) != 0:
            p = ql.popleft()
            for v in d[p]:
                if v not in fq:
                    score[v] += score[p]
                    fq[v]
                    ql.append(v)
        else:
            break
    print(*[score[i] for i in range(1, n + 1)])


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
from collections import*
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,q=map(int,input().split())
    d=defaultdict(list)
    cost=[0]*(n+10)
    
    TF=[1]+[0]*(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):
        a,b=map(int,input().split())
        cost[a]+=b
    
    def dfs(cost,point):
        if len(d[point])==0:
            return 0
        for i in d[point]:
            if TF[i-1]:
                continue
            TF[i-1]=1
            cost[i]+=cost[point]
            dfs(cost,i)
            TF[i-1]=0

    dfs(cost,1)
    print(*cost[1:n+1])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

if __name__ == "__main__":
    n, q = map(int, input().split())
    incidenceGraph = [[] for j in range(0, n)]
    for i in range(0, n - 1):
        a, b = map((lambda x: int(x) - 1), input().split())
        incidenceGraph[a].append(b)
        incidenceGraph[b].append(a)

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

    visited = [False]*n
    stack = deque([0])
    while stack:
        i = stack.popleft()
        ans[i] += operationTuples[i]
        visited[i] = True
        for j in incidenceGraph[i]:
            if visited[j] is False:
                ans[j] += ans[i]
                stack.append(j)
    print(*ans)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
tree={}
for i in range(N-1):
  a,b=map(int,input().split())
  if (a-1) in tree:
    tree[a-1].append(b-1)
  else:
    tree[a-1]=[b-1]
  if (b-1) in tree:
    tree[b-1].append(a-1)
  else:
    tree[b-1]=[a-1]

point=[0]*N

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

ans=[0]*N
stack=[]
stack.append([0,0,-1])
while len(stack)>0:
  nodes=stack.pop()
  node=nodes[0]
  sump=nodes[1]
  parent=nodes[2]
  sump=sump+point[node]
  ans[node]=sump
  if node in tree:
      childs=tree[node]
      for child in childs:
        if child!=parent:
          stack.append([child,sump,node])

print(*ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
import re
import math
import functools

def s_raw():
    return input().rstrip("\r")

def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return list(map(int, ss_raw()))


INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    
def ZAlgo(s):
    l = len(s)
    A = [0]*l
    i =1
    j =0
    A[0]=l
    while i<l:
        while i+j<l and s[j] == s[i+j]:
            j+=1
        if j==0:
            i+=1
            continue
        A[i]=j
        k=1
        while (i+k<l) and (k+A[k]<j):
            A[i+k] =A[k]
            k+=1
        i+=k
        j-=k
    return A


def main():
    
    n,q = ints_raw()
    graph = [[] for _ in range(n)] 
    counters = [0 for _ in range(n)]
    for _ in range(n-1):
        a,b = ints_raw()
        a = a-1
        b = b-1
        graph[a].append(b)
        graph[b].append(a)
    for _ in range(q):
        p,x = ints_raw()
        p = p-1
        counters[p]+=x
    ans = [-1 for _ in range(n)]
    qu = deque()
    qu.append((0,0))

    while len(qu) != 0:
        node,parC = qu.popleft()
        curC = counters[node]+ parC
        ans[node]=curC
        for toN in graph[node]:
            if ans[toN] == -1:
                qu.append((toN,curC))
    return " ".join([str(a) for a in ans])


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
N, Q = [int(nq) for nq in input().split()]
AB = []
for i in range(N):
  AB.append([])
for i in range(N - 1):
  a, b = [int(ab) for ab in input().split()]
  AB[a - 1].append(b)
  AB[b - 1].append(a)

P, X = [], []
for j in range(Q):
  p, x = [int(px) for px in input().split()]
  P.append(p)
  X.append(x)

Score = [0] * N
for j in range(Q):
  Score[P[j] - 1] += X[j]

Exists = [0] * N

Now = []
Next = [1]
Exists[1 - 1] = 1

while Next != []:
  Now = Next
  Next = []
  for nw in Now:
    for nxt in AB[nw - 1]:
      if Exists[nxt - 1] == 0:
        Exists[nxt - 1] = 1
        Score[nxt - 1] += Score[nw - 1]
        Next.append(nxt)

print(*Score)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
ans = [0 for _ in range(n)]
for _ in range(q):
  p,x = map(int,input().split())
  p -= 1
  ans[p] += x
ect = [0 for _ in range(n)]
ect[0] = 1
now = [0]
while now != []:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if ect[y] == 0:
        ect[y] = 1
        now.append(y)
        ans[y] += ans[x]
print(' '.join(list(map(str,ans))))

Submission status: Accepted

Solution code:
# 頂点n個 辺iは頂点aiとbiを結ぶ 各頂点には初期値0のカウンターがある
# 操作j: 頂点pjを根とする部分木に含まれるすべてのカウンターにxj足す
# Q回の操作のあと各カウンターの数値を求める

# 方針: 操作の際に最初に部分木の根にだけ点を加え最後に親の点を子に与えていく
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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


def dfs(now=0, prev=-1):
    kids = connect[now]
    for kid in kids:
        if kid == prev:
            continue
        count[kid] += count[now]
        dfs(kid, now)


dfs()

for i in range(n):
    print(count[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
input=lambda :sys.stdin.readline()
N,Q=map(int, input().split())
tree_dist={}
for i in range(N):
    tree_dist[i+1] = []
for i in range(N-1):
    a,b = map(int, input().split())
    tree_dist[a].append(b)
    tree_dist[b].append(a)
    
z=[0]*N
for i in range(Q):
    p,x = map(int, input().split())
    z[p-1] += x

def saiki(i,p):
    L = list(tree_dist[i])
    for l in L:
        if l != p:
            z[l-1] += z[i-1]
            saiki(l,i)
saiki(1,0)
print(" ".join(map(str,z)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input=lambda :sys.stdin.readline()
N,Q=map(int,input().split())
ab=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)

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

def dfs(p,par):
  for i in ab[p-1]:
    if i!=par:
      P[i-1]+=P[p-1]
      dfs(i,p)

dfs(1,-12345)
print(" ".join(map(str,P)))

Submission status: Accepted

Solution code:
from collections import deque

n, q = map(int, input().split( ))
Edg=[[] for i in range(n+1)]
Done = [0 for _ in range(n+1)]

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


Ans=[0 for i in range(n+1)]
Pls = [0 for i in range(n+1)]


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

root=1

Task=deque()

Task.append(root)

while len(Task)>0:
    p_=Task.popleft()
    tmp = Pls[p_]
    Ans[p_]+=tmp
    Done[p_] = 1
    for child in Edg[p_]:
        if not Done[child]:
            Task.append(child)
            Pls[child]+=tmp


print(*Ans[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline


def dfs(v, par):
    for nv in tree[v]:
        if nv == par:
            continue
        add[nv] += add[v]
        dfs(nv, v)


n, q = map(int, input().split())
tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[b].append(a)
    tree[a].append(b)
add = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    add[p] += x
dfs(0, -1)
print(*add)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200010)

def main():
    def input():
        return sys.stdin.readline()[:-1]

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


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

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

    V = [0 for k in range(N)]
    V[0] = 1
    def dfs(ima):
        for tsugi in G[ima]:
            if V[tsugi] == 0:
                V[tsugi] = 1
                ans[tsugi] += ans[ima]
                dfs(tsugi)
    dfs(0)

    print(*ans,sep=" ")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class Node(object):
    def __init__(self, num: int):
        self.num = num
        self.cnt = 0
        self.visited = False

def dfs(init_node: Node, graph: list):
    stack = [init_node]
    init_node.visited = True
    while stack:
        cur = stack.pop()
        for nex in graph[cur.num]:
            if nex.visited:
                cur.cnt += nex.cnt
                cur.visited = True
            else:
                stack.append(nex)

n, q = li()
nodes = [Node(i) for i in range(n)]
graph = [[] for _ in range(n)]

for _ in range(n-1):
    ai, bi = li_()
    graph[ai].append(nodes[bi])
    graph[bi].append(nodes[ai])

for _ in range(q):
    pi, xi = li()
    pi -= 1
    nodes[pi].cnt += xi

dfs(nodes[0], graph)

ans = [nodes[i].cnt for i in range(n)]
print(*ans)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())

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

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

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

qux = [0]
flag = [False] * n
flag[0] = True

while qux:
    x = qux.pop()
    for ko in ki[x]:
        if not flag[ko]:
            counter[ko] += counter[x]
            qux.append(ko)
            flag[x] = True

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

Submission status: Accepted

Solution code:
n,q = map(int,input().split())

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

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

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

qux = [0]

while qux:
    x = qux.pop()
    for ko in ki[x]:
        counter[ko] += counter[x]
        qux.append(ko)
        ki[ko].remove(x)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from collections import deque

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

    # KeyInsight
    # 直線のグラフとみなす
    # 累積和の考え方を応用

    # 隣接リストを作成
    for i in range(n - 1):
        ai, bi = map(int, input().split())
        graph[ai - 1].append(bi - 1)
        graph[bi - 1].append(ai - 1)

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

    for j in range(q):
        pi, xi = map(int, input().split())
        values[pi - 1] += xi

    # 木の持ち方
    d = deque()
    d.append(0)
    visited = [False for _ in range(n)]
    visited[0] = True

    # bfs
    while d:
        di = d.popleft()

        for g in graph[di]:
            if not visited[g]:
                visited[g] = True
                values[g] += values[di]
                d.append(g)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N,Q = map(int,input().split())
AB = [tuple(int(i) for i in input().split()) for j in range(N-1)]
PX = [tuple(int(i) for i in input().split()) for j in range(Q)]

graph = [[] for i 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 

parent = [None]*(N+1)
q = deque([1])
while q:
    i = q.popleft()
    for j in graph[i]:
        if parent[i] == j:
            continue
        else:
            q.append(j)
            value[j] += value[i]
            parent[j] = i

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


# par = [None] * (N+1)
# q = [1]
# while q:
#     x = q.pop()
#     for y in graph[x]:
#         if y == par[x]:
#             continue
#         value[y] += value[x]
#         q.append(y)
#         par[y] = x

Submission status: Accepted

Solution code:
# from collections import deque

# n,q = map(int,input().split())
# c = [[] for i in range(n)]
# for i in range(n-1):
#     a,b = map(int,input().split())
#     c[a-1].append(b-1)
# px = deque([int(i) for i in input().split()] for j in range(q))
# que = deque()
# ans = [0 for i in range(n)]
# while px:
#     l = px.popleft()
#     x = l[1]
#     que.append(l[0]-1)
#     while que:
#         p = que.popleft()
#         ans[p] += x
#         for j in c[p]:
#             que.append(j)
# for i in range(n):
#     print(ans[i])

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

par = [None] * (N+1)
q = [1]
while q:
    x = q.pop()
    for y in graph[x]:
        if y == par[x]:
            continue
        value[y] += value[x]
        q.append(y)
        par[y] = x

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

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

used = [False] * N
stack = [0]
s_pop = stack.pop
s_append = stack.append
used[0] = True
while len(stack) != 0:
    tmp = s_pop()
    for i in graph[tmp]:
        if not used[i]:
            s_append(i)
            count[i] += count[tmp]
            used[i] = True

print (*count)

Submission status: Accepted

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

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

used = [False] * N
stack = [0]
used[0] = True
while len(stack) != 0:
    tmp = stack.pop()
    for i in graph[tmp]:
        if not used[i]:
            stack.append(i)
            count[i] += count[tmp]
            used[i] = True

print (*count)

Submission status: Accepted

Solution code:
import sys


input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    lst_ab = [tuple(map(int, input().split())) for i in range(N - 1)]
    lst_px = [tuple(map(int, input().split())) for i in range(Q)]

    tree = [[] for _ in range(N)]
    for a, b in lst_ab:
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)

    lst_score = [0] * N
    for p, x in lst_px:
        p -= 1
        lst_score[p] += x

    lst_ans = [0] * N
    lst_ans[0] = lst_score[0]
    lst_visited = [0] * N
    stack = [0]
    while stack:
        v = stack.pop()
        lst_visited[v] = 1
        for to in tree[v]:
            if lst_visited[to]:
                continue
            stack.append(to)
            lst_ans[to] = lst_ans[v] + lst_score[to]
    
    print(*lst_ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
setrecursionlimit(10000000)

input = stdin.readline
lmi = lambda: list(map(int, input().split()))
mi = lambda: map(int, input().split())
si = lambda: input().strip('\n')
ssi = lambda: input().strip('\n').split()


def dfs(node, prev):
    for i in graph[node]:
        if i != prev:
            inc[i] += inc[node]
            dfs(i, node)


n, q = mi()
inc = [0 for i in range(n+1)]
graph = [[] for i in range(n+1)]
for i in range(n-1):
    a, b = mi()
    graph[a].append(b)
    graph[b].append(a)
for i in range(q):
    a, b = mi()
    inc[a] += b
dfs(1, -1)
print(*inc[1:])

Submission status: Accepted

Solution code:
N,Q=[int(s) for s in input().split()]
#辺でつながれた場所をすべてリストアップ
con_list=[set() for s in range(N+1)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  con_list[a].add(b)
  con_list[b].add(a)

v_list=[0 for s in range(N+1)]
for i in range(Q):
  x,y=[int(s) for s in input().split()]
  v_list[x]+=y

position=1 #現在位置
counter=v_list[1] #カウンター
ans_list=[0 for s in range(N+1)] #答え
ans_list[1]=counter 
vertex_num=1 #訪れた場所の数
oya_list=[-1 for s in range(N+1)] #親に戻るためのリスト

while vertex_num<N:
  #まだ行っていない子があるか？
  if len(con_list[position])>0:
    x=con_list[position].pop()
    con_list[x].remove(position) #xの行先から親を消す
    oya_list[x]=position
    position=x
    counter+=v_list[position] #カウンターの更新
    ans_list[position]=counter
    vertex_num+=1
  else: #行き先がないなら戻る
    position=oya_list[position]
    counter=ans_list[position] #カウンターを戻す
print(*ans_list[1:])