Problem:


Score : 400 points

Problem Statement

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

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

Now, the following Q operations will be performed:

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

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

Constraints

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

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

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

100 110 111 110

The tree in this input is as follows:

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

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

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

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

Sample Input 2

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

Sample Output 2

20 20 20 20 20 20



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


Sample output:
100 110 111 110

Submission status: Accepted

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

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

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

cnt = [0]*N
for p,x in PX:
    cnt[p-1] += x

def dfs(v,parent,add):
    for w in graph[v]:
        if w != parent:
             cnt[w-1] += add
             dfs(w,v,cnt[w-1])

for i in graph[1]:
    cnt[i-1] += cnt[0]
    dfs(i,1,cnt[i-1])

print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

deq = deque([0])
seen = [False] * n
while deq:
    parent = deq.popleft()
    link = links[parent]
    for v in link:
        if not seen[v]:
            ans[v] += ans[parent]
            deq.append(v)
    seen[parent] = True

print(*ans)

Submission status: Accepted

Solution code:
I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################
import sys
input=sys.stdin.readline
n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(q):
    p,x = I0()
    counter[p-1]+=x
    
stack = [0]
seen = dict()
seen[0] = 1
while stack:
    yy = stack.pop()
    for i in tree[yy]:
        if seen.get(i,-1) == -1:
            seen[i] = 1
            counter[i]+=counter[yy]
            stack.append(i)
            
print(*counter)

Submission status: Accepted

Solution code:
I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################
n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
 
for i in range(q):
    p,x = I0()
    counter[p-1]+=x

stack = [0]
seen = dict()
seen[0] = 1
while stack:
    yy = stack.pop()
    for i in tree[yy]:
        if seen.get(i,-1) == -1:
            seen[i] = 1
            counter[i]+=counter[yy]
            stack.append(i)
            
print(*counter)

Submission status: Accepted

Solution code:
I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################


'''from sys import stdin,setrecursionlimit
#from copy import deepcopy
 
setrecursionlimit(10**6)
input=stdin.readline'''

def dfs(p,father=-1):
    for i in tree[p]:
        if i == father:
            continue
        counter[i]+=counter[p]
        dfs(i,p)

n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(q):
    p,x = I0()
    counter[p-1]+=x
    

#dfs(0)
stack = [0]
seen = dict()
seen[0] = 1
while stack:
    yy = stack.pop()
    for i in tree[yy]:
        if seen.get(i,-1) == -1:
            seen[i] = 1
            counter[i]+=counter[yy]
            stack.append(i)
            
print(*counter)

Submission status: Accepted

Solution code:
I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################


from sys import stdin,setrecursionlimit
#from copy import deepcopy
 
setrecursionlimit(10**6)
input=stdin.readline

def dfs(p,father=-1):
    for i in tree[p]:
        if i == father:
            continue
        counter[i]+=counter[p]
        dfs(i,p)

n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(q):
    p,x = I0()
    counter[p-1]+=x
    

dfs(0)

print(*counter)

'''stack = [1]
while stack:
    yy = stack.pop()
    for i in tree[yy]:
        counter[i-1]+=counter[yy-1]
        stack.append(i)'''

Submission status: Accepted

Solution code:
#import pysnooper
#import os,re,sys,operator,math,heapq,string
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement
from sys import stdin,setrecursionlimit
#from copy import deepcopy

setrecursionlimit(10**6)
input=stdin.readline

def dfs(v,c=-1):
    for i in graph[v]:
        if i==c:
            continue
        root[i]+=root[v]
        dfs(i,v)
n,q=map(int,input().split())
graph=[[] for _ in range(n)]
root=[0]*n
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

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

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6) #再帰の回数制限を増やす
input = sys.stdin.readline


def add_num(i, total, parent=-1):
    """隣接リストを取り出して深さ優先探索
    自分より上層の total のカウント数と部分木の頂点としてのカウント数を足す"""
    for p in adj[i]:
        if p != parent:
            ans_lst[p] = total + tmp[p]
            add_num(p, total + tmp[p], i)
    return
    
    
N, Q = [int(i) for i in input().split()]

adj = [[] for _ in range(N)] # 隣接リスト
tmp = [0] * N # 部分木の根としてのカウント数 
ans_lst = [0] * N # 答えのリスト

# 隣接リストの作成
for _ in range(N - 1):
    a, b = [int(i) - 1 for i in input().split()]
    adj[a].append(b)
    adj[b].append(a)

# ｔｍｐリストの作成
for _ in range(Q):
    p, x = [int(i) for i in input().split()]
    tmp[p-1] += x

ans_lst[0] = tmp[0]
total = tmp[0]
add_num(0, total)

print(*ans_lst, sep=' ')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
L = sys.stdin.readlines()
for i in range(len(L)):
    L[i] = list(map(int, L[i].split()))
n =L[0][0]

rin = [[] for _ in range(n)]
for v in L[1:n]:
    rin[v[0]-1].append(v[1]-1)
    rin[v[1]-1].append(v[0]-1)
    
score = [0 for _ in range(n)]
for ele in L[n:]:
    score[ele[0]-1] +=ele[1]
#print(score)
 
def dfs(p, bp=-1):
    for c in rin[p]:
        if c != bp:
            #print(c)
            score[c]+= score[p]
            dfs(c, p)
 
dfs(0)
print(*score)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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)]
t = [[] for i in range(n)] #つながり
for i in ab:
  t[i[0]-1].append(i[1]-1)
  t[i[1]-1].append(i[0]-1)
c = [0] * n # count
for i in px:
  c[i[0]-1] += i[1]
a = [0] * n
visited = [0] * n
stack = [0]
a[0] = c[0]
while stack:
  cur = stack.pop()
  visited[cur] = 1
  for i in t[cur]:
    if visited[i] == 1:
      continue
    else:
      stack.append(i)
      a[i] = a[cur] + c[i]
print(' '.join(map(str,a)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, Q = map(int, sys.stdin.readline().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(N-1)]
p_x = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

rin = [[] for _ in range(N)]
for v in a_b:
    rin[v[0]-1].append(v[1]-1)
    rin[v[1]-1].append(v[0]-1)

score = [0 for _ in range(N)]
for ele in p_x:
    score[ele[0]-1] +=ele[1]
#print(score)

def dfs(p, bp=-1):
    for c in rin[p]:
        if c != bp:
            #print(c)
            score[c]+= score[p]
            dfs(c, p)

dfs(0)
print(*score)

Submission status: Accepted

Solution code:
from sys import exit, stderr, stdin, setrecursionlimit
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N, Q = list(map(int,input().split()))
    adjl = [[] for _ in range(N+1)]
    for _ in  range(N-1):
        a, b = list(map(lambda x: int(x),input().split()))
        adjl[a].append(b)
        adjl[b].append(a)
    res = [0]*(N+1)
    # print(adjl)
    for _ in  range(Q):
        p, x = list(map(lambda x: int(x),input().split()))
        res[p] += x
    # def dfs(n, parent = None):
    #     if parent != None:
    #         res[n] += res[parent]
    #     for neigh in adjl[n]:
    #         if neigh == parent:
    #             continue
    #         else:
    #             dfs(neigh,n)
    # dfs(0)
    q = [(1,0)]
    while q:
        x, parent = q.pop()
        res[x] += res[parent]
        for neigh in adjl[x]:
            if neigh != parent:
                q.append((neigh,x))

    print(' '.join(map(str,res[1:])))





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
E = [[] for _ in range(N)]
C = [0] * N
C[0] = 0
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):
  p, x = map(int, input().split())
  C[p - 1] += x
D = [-1] * N
D[0] = 0
Q = [0] * N
enq = 0
for pos in range(N):
  q = Q[pos]
  for adj in E[q]:
    if D[adj] >= 0:
      continue
    D[adj] = D[q] + 1
    C[adj] += C[q]
    enq += 1
    Q[enq] = adj
print(' '.join([str(c) for c in C]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, Q = map(int, sys.stdin.readline().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(N-1)]
p_x = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]
 
rin = [[] for _ in range(N)]
for v in a_b:
    rin[v[0]-1].append(v[1]-1)
    rin[v[1]-1].append(v[0]-1)
    
score = [0 for _ in range(N)]
for ele in p_x:
    score[ele[0]-1] +=ele[1]
#print(score)
 
def dfs(p, bp=-1):
    for c in rin[p]:
        if c != bp:
            #print(c)
            score[c]+= score[p]
            dfs(c, p)
 
dfs(0)
print(*score)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
 
input = sys.stdin.readline
tree = [[] for _ in range(200001)]
scores = [0 for _ in range(200001)]

def dfs(pre, p):
    for child in tree[p]:
        if child == pre: continue
        scores[child] += scores[p]
        dfs(p, child)

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

    for _ in range(Q):
        p, x = map(int, input().split())
        scores[p] += x
    dfs(0, 1)
    print(' '.join(map(str, scores[1:N+1])))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

N, Q = map(int, input().split())
Links = [[] for _ in range(N)]
AnsArr = [0] * N

# 辺の数だけ
for i in range(N - 1):
    a, b = map(int, input().split())
    Links[a - 1].append(b - 1)
    Links[b - 1].append(a - 1)

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

# BFS
# 頂点1から開始
q = collections.deque([0])
visited = [0] * N
while q:
    t = q.pop()
    visited[t] = 1
    for e in Links[t]:
        if visited[e] == 1:
            continue
        visited[e] = 1
        # 親の値を子に受け継ぐ
        AnsArr[e] += AnsArr[t]
        q.appendleft(e)

print(*AnsArr)

Submission status: Accepted

Solution code:
import sys
from heapq import *
sys.setrecursionlimit(10**8)
 
input = sys.stdin.readline
tree = [[] for _ in range(200001)]
scores = [0 for _ in range(200001)]

def dfs(pre, p):
    for child in tree[p]:
        if child == pre: continue
        scores[child] += scores[p]
        dfs(p, child)

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

    for _ in range(Q):
        p, x = map(int, input().split())
        scores[p] += x
    dfs(0, 1)
    print(' '.join(map(str, scores[1:N+1])))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import *
sys.setrecursionlimit(10**8)

input = sys.stdin.readline

tree = [[] for _ in range(200001)]
res = [0]*200001

def dfs(p, pre):
    for child in tree[p]:
        if child == pre: continue
        res[child] += res[p]
        dfs(child, p)

def main():
    """ main """
    N, Q = map(int, input().split())
    for _ in range(N-1):
        a,b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    for _ in range(Q):
        p,x = map(int, input().split())
        res[p] += x
    dfs(1, 0)

    print(*res[1:N+1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import collections
n,q = map(int,input().split())
a_b_list = [list(map(int,input().split())) for i in range(n-1)]
p_x_list = [list(map(int,input().split())) for i in range(q)]

graph_direct_list = [[] for _ in range(n+1)]
for i in range(n-1):
    a_i = a_b_list[i][0]
    b_i = a_b_list[i][1]
    graph_direct_list[a_i].append(b_i)
    graph_direct_list[b_i].append(a_i)

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


for j in range(q):
    p_j = p_x_list[j][0]
    x_j = p_x_list[j][1]
    counter_init_list[p_j] += x_j

counter_list = [0 for _ in range(n+1)]
graph_vertex_checked_list = [0 for _ in range(n+1)]


graph_vertex_stack_que=collections.deque()
graph_vertex_stack_que.append(1) # start
while graph_vertex_stack_que:
    v = graph_vertex_stack_que.pop()
    graph_vertex_checked_list[v] = 1
    counter_list[v] += counter_init_list[v]
    for u in graph_direct_list[v]:
        if graph_vertex_checked_list[u] == 1:
            continue
        counter_list[u] += counter_list[v]
        graph_vertex_stack_que.append(u)
print(*counter_list[1:])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
# px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
# for i in range(len(px)):
for _ in range(q):
    p,x = map(int,input().split())
    c[p-1] += x  
visited = [0]*n
cnd = [1]   # current_node
while len(cnd)>0:
    nnd = []
    for j in cnd:
        visited[j-1]=1
        ko = tree[j-1]
        for k in ko:
            if visited[k-1]==0:
                c[k-1] += c[j-1]
                nnd.append(k)
    cnd = nnd
print(" ".join(map(str,c)))

Submission status: Accepted

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

ans = [0 for i in range(N)]
for i in range(Q):
  x, p = map(int, input().split())
  ans[x-1] += p
que = deque()
for a in tree[0]:
  que.append([0,a])
used = [1] + [0]*(N-1)
while que:
  u, v = que.pop()
  if used[v] == 0:
    used[v] = 1
    ans[v] += ans[u]
    for a in tree[v]:
      que.append([v,a])

    
print(*ans)

Submission status: Accepted

Solution code:
def get_answer(ki):
    """
    めも
    配列コピーはしない
    入力テキスト配列から数値配列の変換は行わない（配列サイズが大きくなる）
    for,if,dictは使わない
    """
    k0 = ki[0].split(" ")
    n = int(k0[0])
    q = int(k0[1])
    q_index = [0] * n
    for k in ki[-q:]:
        k = k.split(" ")
        q0 = int(k[0])
        q1 = int(k[1])
        q_index[q0 - 1] += q1

    score = [0] * n

    t_index = []
    for i in range(0, n + 1):
        t_index.append([])
    for ki_n in ki[1:-q]:
        k = ki_n.split(" ")
        n0 = int(k[0])
        n1 = int(k[1])
        t_index[n0].append(n1)
        t_index[n1].append(n0)

    t_stack = [1]
    s_stack = [0]
    r_flag = [0] * n
    while len(t_stack) > 0:
        i = t_stack.pop()
        s = s_stack.pop()
        if r_flag[i - 1]:
            continue
        r_flag[i - 1] = 1
        s += q_index[i - 1]
        score[i - 1] += s
        t_stack += t_index[i]
        s_stack += [s] * len(t_index[i])

    ss = [str(s) for s in score]
    return " ".join(ss)


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break
            if len(input1) == 0:
                break
            input_ki.append(input1)
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Accepted

Solution code:
def get_answer(ki):
    """
    めも
    配列コピーはしない
    入力テキスト配列から数値配列の変換は行わない（配列サイズが大きくなる）
    for,if,dictは使わない
    """
    k0 = ki[0].split(" ")
    n = int(k0[0])
    q = int(k0[1])
    q_index = [0] * n
    for k in ki[-q:]:
        k = k.split(" ")
        q0 = int(k[0])
        q1 = int(k[1])
        q_index[q0 - 1] += q1

    score = [0] * n

    t_index = []
    for i in range(0, n + 1):
        t_index.append([])
    for ki_n in ki[1:-q]:
        k = ki_n.split(" ")
        n0 = int(k[0])
        n1 = int(k[1])
        t_index[n0].append(n1)
        t_index[n1].append(n0)

    t_stack = [1]
    s_stack = [0]
    r_flag = [0] * n
    while len(t_stack) > 0:
        i = t_stack.pop()
        s = s_stack.pop()
        if r_flag[i - 1]:
            continue
        r_flag[i - 1] = 1
        s += q_index[i - 1]
        score[i - 1] += s
        t_stack += t_index[i]
        s_stack += [s] * len(t_index[i])

    ss = [str(s) for s in score]
    return " ".join(ss)


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if (not input1) or (len(input1) == 0):
                break
            input_ki.append(input1)
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Accepted

Solution code:
def get_answer(ki):
    """
    n = ki[0][0]
    q = ki[0][1]
    n_data = ki[1:-q]
    q_index = [0] * n
    for qq in ki[-q:]:
        q_index[qq[0] - 1] += qq[1]
    """
    k0 = ki[0].split(" ")
    n = int(k0[0])
    q = int(k0[1])
    q_index = [0] * n
    for k in ki[-q:]:
        k = k.split(" ")
        q0 = int(k[0])
        q1 = int(k[1])
        q_index[q0 - 1] += q1

    score = [0] * n

    """
        assert get_answer(["4 3",
                       "1 3", "1 4", "2 3",
                       "2 10", "1 100", "3 1"]) == "100 111 101 100"
    """
    t_index = []
    for i in range(0, n + 1):
        t_index.append([])
    n_data = ki[1:-q]
    for ki_n in n_data: #ki[1:-q]:
        k = ki_n.split(" ")
        n0 = int(k[0])
        n1 = int(k[1])
        t_index[n0].append(n1)
        t_index[n1].append(n0)

    t_stack = [1]
    s_stack = [0]
    r_flag = [0] * n
    while len(t_stack) > 0:
        i = t_stack.pop()
        s = s_stack.pop()
        if r_flag[i - 1]:
            continue
        r_flag[i - 1] = 1
        s += q_index[i - 1]
        score[i - 1] += s
        t_stack += t_index[i]
        s_stack += [s] * len(t_index[i])

    ss = [str(s) for s in score]
    return " ".join(ss)

# b05 1923 ms
# b05 1382 ms
if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break
            if len(input1) == 0:
                break
            #s = input1.split(" ")
            #input_ki.append([int(s[0]), int(s[1])])
            input_ki.append(input1)
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Accepted

Solution code:
def get_answer(ki):
    """
    n = ki[0][0]
    q = ki[0][1]
    n_data = ki[1:-q]
    q_index = [0] * n
    for qq in ki[-q:]:
        q_index[qq[0] - 1] += qq[1]
    """
    k0 = ki[0].split(" ")
    n = int(k0[0])
    q = int(k0[1])
    q_index = [0] * n
    for k in ki[-q:]:
        k = k.split(" ")
        q0 = int(k[0])
        q1 = int(k[1])
        q_index[q0 - 1] += q1

    score = [0] * n

    """
        assert get_answer(["4 3",
                       "1 3", "1 4", "2 3",
                       "2 10", "1 100", "3 1"]) == "100 111 101 100"
    """
    t_index = []
    for i in range(0, n + 1):
        t_index.append([])
    for ki_n in ki[1:-q]:
        k = ki_n.split(" ")
        n0 = int(k[0])
        n1 = int(k[1])
        t_index[n0].append(n1)
        t_index[n1].append(n0)

    t_stack = [1]
    s_stack = [0]
    r_flag = [0] * n
    while len(t_stack) > 0:
        i = t_stack.pop()
        s = s_stack.pop()
        if r_flag[i - 1]:
            continue
        r_flag[i - 1] = 1
        s += q_index[i - 1]
        score[i - 1] += s
        t_stack += t_index[i]
        s_stack += [s] * len(t_index[i])

    ss = [str(s) for s in score]
    return " ".join(ss)

# b05 1923 ms
if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break
            if len(input1) == 0:
                break
            #s = input1.split(" ")
            #input_ki.append([int(s[0]), int(s[1])])
            input_ki.append(input1)
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Accepted

Solution code:
def get_answer(ki):
    n = ki[0][0]
    q = ki[0][1]
    #n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    #q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    n_data = ki[1:-q]
    #q_data = ki[-q:]
    q_index = [0] * n
    for qq in ki[-q:]:
        q_index[qq[0] - 1] += qq[1]

    score = [0] * n

    """
        assert get_answer(["4 3",
                       "1 3", "1 4", "2 3",
                       "2 10", "1 100", "3 1"]) == "100 111 101 100"
    """
    t_index = []
    for i in range(0, n + 1):
        t_index.append([])
    for nn in n_data:
        t_index[nn[0]].append(nn[1])
        t_index[nn[1]].append(nn[0])

    t_stack = [1]
    s_stack = [0]
    r_flag = [0] * n
    while len(t_stack) > 0:
        i = t_stack.pop()
        s = s_stack.pop()
        if r_flag[i - 1]:
            continue
        r_flag[i - 1] = 1
        s += q_index[i - 1]
        score[i - 1] += s
        t_stack += t_index[i]
        s_stack += [s] * len(t_index[i])

    """
    s_value = str(score[0])
    for i in range(1, n):
        s_value += " " + str(score[i])
    """
    ss = [str(s) for s in score]
    return " ".join(ss)

# b05 1998 ms
if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break
            if len(input1) == 0:
                break
            s = input1.split(" ")
            input_ki.append([int(s[0]), int(s[1])])
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Accepted

Solution code:
import sys

n, q = map(int, sys.stdin.readline().split())
g = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
xs = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, sys.stdin.readline().split())
    p -= 1
    xs[p] += x

visited = [False for _ in range(n)]
# def rec(prev_v, v, value):
#     if visited[v]:
#         return
#     visited[v] = True
#     next_value = value + xs[v]
#     costs[v] = next_value
#     for next_v in g[v]:
#         if next_v == prev_v:
#             continue
#         rec(v, next_v, next_value)
# rec(-1, 0, 0)

current_node = [0]
while len(current_node) > 0:
    next_node = []
    for v in current_node:
        visited[v] = True
        for next_v in g[v]:
            if visited[next_v]:
                continue
            next_node.append(next_v)
            xs[next_v] += xs[v]
    current_node = next_node

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

Submission status: Accepted

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

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

c = [0]*n

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

ans = [0]*n
visited = [0]*n

que = []

que.append(0)
visited[0]=1
ans[0]+=c[0]

while que:
    x = que.pop()
    for y in d[x]:
        if visited[y]==1:
            continue
        else:
            ans[y]+=ans[x]+c[y]
            visited[y]=1
            que.append(y)



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

Submission status: Accepted

Solution code:
#17:16
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:
from queue import deque
N,Q = map(int,input().split())
tree = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

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

checked = [False for i in range(N+1)]
myq = deque()
myq.append(1)

while myq:
    v = myq.pop()
    checked[v] = True
    for n in tree[v]:
        if not checked[n]:
            ans[n] += ans[v]
            myq.append(n)
print(' '.join(str(ans[i]) for i in range(1,N+1)))

Submission status: Accepted

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

N, Q = map(int, input().split())
table = [[] for i in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  table[a].append(b)
  table[b].append(a)
task = [0]*N
point = [-1]*N
point[0] = 0
for i in range(Q):
  p,x = map(int, input().split())
  p -= 1
  task[p] += x
H = deque()
H.append(0)
 
while H:
  p = H.popleft()
  point[p] += task[p]
  for np in table[p]:
    if point[np] == -1:
      H.append(np)
      point[np] = point[p]
 
print(" ".join(map(str, point)))

Submission status: Accepted

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

N, Q = map(int, input().split())
table = [[] for i in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  table[a].append(b)
  table[b].append(a)
task = [0]*N
point = [-1]*N
point[0] = 0
for i in range(Q):
  p,x = map(int, input().split())
  p -= 1
  task[p] += x
H = deque()
H.append(0)

while H:
  p = H.popleft()
  point[p] += task[p]
  for np in table[p]:
    if point[np] == -1:
      H.append(np)
      point[np] = point[p]

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

Submission status: Accepted

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

N, Q = map(int, input().split())
table = [[] for i in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  table[a].append(b)
  table[b].append(a)
task = [0]*N
point = [-1]*N
point[0] = 0
for i in range(Q):
  p,x = map(int, input().split())
  p -= 1
  task[p] += x
H = deque()
H.append(0)

while H:
  p = H.popleft()
  point[p] += task[p]
  for np in table[p]:
    if point[np] == -1:
      H.append(np)
      point[np] = point[p]

for i in range(N):
  print(point[i])

Submission status: Accepted

Solution code:
from collections import deque

N, Q = map(int, input().split())
table = [[] for i in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  table[a].append(b)
  table[b].append(a)
task = [0]*N
point = [-1]*N
point[0] = 0
for i in range(Q):
  p,x = map(int, input().split())
  p -= 1
  task[p] += x
H = deque()
H.append(0)

while H:
  p = H.popleft()
  point[p] += task[p]
  for np in table[p]:
    if point[np] == -1:
      H.append(np)
      point[np] = point[p]

for i in range(N):
  print(point[i])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
    
N, Q = map(int, input().split())

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

score = [0]*(N+1)
for j in range(Q):
    p, x = map(int, input().split())
    score[p]+=x
    
q = deque()
q.append(1)
visited = [0]*(N+1)
while q:
    v = q.pop()
    visited[v]=1
    for u in edge[v]:
        if visited[u]:
            continue
        else:
            score[u]+=score[v]
            q.append(u)

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

Submission status: Accepted

Solution code:
n, q = map(int,input().split())
score = [0]*n
parent = [-1]*n
edge_list = [[] for i in range(n)]
ope = [0]*n
ans = [0]*n
for i in range(n-1):
    a, b = map(int,input().split())
    edge_list[a-1].append(b-1)
    edge_list[b-1].append(a-1)

for i in range(q):
    p, x = map(int, input().split())
    ope[p-1] += x
stack = [0]
ans[0] += ope[0]
while stack != []:
    par = stack.pop()
    if edge_list[par]:
        for i in edge_list[par]:
            if parent[i] == -1 and i > 0:
                parent[i] = par
                ans[i] = ans[par] + ope[i]
                stack.append(i)
    else:
        stack.pop()
print(*ans)