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:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        lower, upper = [], []
        i = 1
        while i * i <= n:
            if n % i == 0:
                lower.append(i)
                if i != n // i:
                    upper.append(n // i)
            i += 1
        return lower + upper[::-1]

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)

ans = None
counter = None
G = None


def dfs(v, cnt):
    global ans, counter, G
    cnt += counter[v]
    ans[v] = cnt
    for g in G[v]:
        if ans[g] != -1:
            continue
        dfs(g, cnt)


def solve():
    global ans, counter, G
    N, Q = Scanner.map_int()
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    counter = [0 for _ in range(N)]
    for _ in range(Q):
        p, x = Scanner.map_int()
        p -= 1
        counter[p] += x
    ans = [-1 for _ in range(N)]
    dfs(0, 0)
    print(*ans)


def main():
    sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import *
S=sys.stdin.readlines()
N,Q=map(int,S[0].split())
G=[[] for i in range(N)]
a,b=0,0
for i in range(N-1):
  a,b=map(int,S[i+1].split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
X=[0]*N
for i in range(Q):
  a,b=map(int,S[N+i].split())
  X[a-1]+=b
D=deque()
S=set()
def qao(x):
  global D,S
  if x in S:
    return False
  S.add(x)
  D.append(x)
  return True

def bfs():
  global D,X,G
  v=0
  for i in range(len(D)):
    v=D.popleft()
    for j in range(len(G[v])):
      if qao(G[v][j]):
        X[G[v][j]]+=X[v]
  return len(D)

qao(0)
while bfs():
  pass
print(*X)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    P = [0] * N
    (*PX,) = map(int, read().split())
    for p, x in zip(*[iter(PX)] * 2):
        P[p - 1] += x

    stack = deque([0])
    seen = [False] * N
    while stack:
        v = stack.pop()
        seen[v] = True
        for nv in G[v]:
            if seen[nv]:
                continue
            P[nv] += P[v]
            stack.append(nv)

    print(' '.join(map(str, P)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    P = [0] * N
    (*PX,) = map(int, read().split())
    for p, x in zip(*[iter(PX)] * 2):
        P[p - 1] += x

    def dfs(v, p):
        for nv in G[v]:
            if nv == p:
                continue
            P[nv] += P[v]
            dfs(nv, v)

    dfs(0, -1)

    print(' '.join(map(str, P)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

import collections
N, Q = rl()
edges = collections.defaultdict(list)
for i in range(N-1):
	a, b = rl()
	edges[a-1].append(b-1)
	edges[b-1].append(a-1)
root_cnts = [0] * N
for i in range(Q):
	p, x = rl()
	root_cnts[p-1] += x

cnts = [0] * N

queue = collections.deque()
queue.append([0, 0, -1])

while queue:
	n, c, p = queue.pop()
	c += root_cnts[n]
	cnts[n] = c
	for m in edges[n]:
		if m == p: continue
		queue.append((m, c, n))

print(*cnts)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

q = [1]
used = [False]*(N+1)
used[1] = True
while q:
    s = q.pop()
    for t in d[s]:
        if used[t]:continue
        used[t] = True
        ans[t]+=ans[s]
        q.append(t)

print(*ans[1:])

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
tree = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)

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

stack = [0]
flag = [False]*n

while stack:
    nex = stack.pop()
    flag[nex] = True
    for i in tree[nex]:
        if flag[i]:
            continue
        w[i] += w[nex]
        stack.append(i)

print(*w)

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

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

stack = [0]
flag = [False]*N

while stack:
    next = stack.pop()
    flag[next] = True
    for i in graph[next]:
        if flag[i]:
            continue
        w[i] += w[next]
        stack.append(i)
        #print(stack)

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

Submission status: Accepted

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

from pprint import pprint
import sys

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


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

graph = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = map(int, input().split())
    # undirected, 0-indexed
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

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

# 方針
# 1. 各クエリに対し、頂点p_jのカウンターにx_jを足す
# (この段階では部分木に含まれるノードには操作を行わない)
# 2. クエリを全て処理したあと、深さ優先順に各ノードvのカウンタを以下のように更新する
# count[v] = count[v] + 親ノードのカウンタ
# 毎回部分木に対して処理を行うのだとO(N^2)の計算量となり遅いので、上記のように工夫して更新する


def bfs(v, parent):
    for v_adj in graph[v]:
        if v_adj == parent:
            continue
        count[v_adj] += count[v]
        bfs(v_adj, v)


count = [0] * N
for p, x in query:
    count[p] += x
# pprint(count)

v = 0
bfs(0, -1)

print(*count)

Submission status: Accepted

Solution code:
#「探索候補スタック」「探索済みリスト」「現在地点」の３点セットでとらえる
n,q=map(int,input().split())
mat=[set() for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    mat[a-1].add(b-1)
    mat[b-1].add(a-1) # プラスした要素
count=[0]*n
for _ in range(q):
    p,score=map(int,input().split())
    count[p-1]+=score

stack=[[0,0,-1]]
while stack:
    # print(stack)
    num,cnt,pr=stack.pop()
    count[num]+=cnt
    for k in mat[num]:
        if k==pr:
            continue
        stack.append([k,count[num],num])
print(*count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,Q = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

X = {i+1:0 for i in range(N)}
for px in PX:
    X[px[0]] += px[1]

G = {i+1:[] for i in range(N)}
for ab in AB:
    G[ab[0]].append(ab[1])
    G[ab[1]].append(ab[0])

seen = [False]*N
W = [0]*N

def dfs(G, W, v, w):
    seen[v-1] = True
    W[v-1] = w+X[v]
    for nv in G[v]:
        if seen[nv-1]:
            continue
        dfs(G, W, nv, W[v-1])

dfs(G, W, 1, 0)

print(*W)

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
tree = [set() for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].add(b-1)
    tree[b-1].add(a-1)
count = [0]*n
for _ in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
    
stack = [[0,0,-1]] # [number,count,pair]
while stack:
    num,cnt,pr = stack.pop()
    count[num] += cnt
    for k in tree[num]:
        if k == pr:
            continue
        stack.append([k,count[num],num])
        
print(*count)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7
N,Q = I()
edge = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = I()
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
ans = [0]*N
for _ in range(Q):
    p,x = I()
    ans[p-1] += x
que = [0]
visited = {0}
while que:
    p = []
    for i in que:
        for j in edge[i]:
            if j in visited:
                continue
            visited.add(j)
            ans[j] += ans[i]
            p.append(j)
    que = p
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

q = deque([1])
visited=set()
while q:
    v = q.popleft()
    visited.add(v)
    for next_v in g[v]:
        if next_v not in visited:
            cnt[next_v]+=cnt[v]
            q.append(next_v)

print(*cnt[1:])

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n,q = imap()
g = adj(n+1)
for i in range(n-1):
    a,b = imap()
    g[a].append(b)
    g[b].append(a)

cnt = iarr(n+1)
for i in range(q):
    p,x = imap()
    cnt[p] += x

que = col.deque([1])
dep = col.defaultdict(int)
dep[1] = 1
while que:
    now = que.popleft()
    for next in g[now]:
        if dep[next]: continue
        # dep更新、que更新、そのほか　＝３点セット
        dep[next] = dep[now] + 1
        que.append(next)
        cnt[next] += cnt[now]

print(*cnt[1:])

Submission status: Accepted

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

n, q = 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)

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

def dfs(idx):
    visited[idx]=1
    for i in g[idx]:
        if visited[i]==1:
            continue
        costs[i]+=costs[idx]
        dfs(i)
    return

dfs(0)
print(*costs)

Submission status: Accepted

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

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

n,q=map(int,input().split())
cnt=[0]*(n)
g=[[] for _ in range(n)]
for _ in range(n-1): #木グラフの隣接リストを作成
  a,b=map(int,input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
for _ in range(q):
    a , b = map(int,input().split())
    a = a - 1
    cnt[a] += b

def dfs(now,prev=-1):
  for next in g[now]:
    if next==prev:
      continue
      
    cnt[next]+=cnt[now]
    dfs(next,now)
dfs(0)
print(*cnt)

Submission status: Accepted

Solution code:
from collections import deque

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

def LI():
    return list(map(int, input().split()))

N, Q = MI()
T = [[] for _ in range(N)]

for _ in range(N - 1):
    a, b = MI()
    T[a - 1].append(b - 1)
    T[b - 1].append(a - 1)
    
plus = [0] * N

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

queue = deque([0])
visited = [False] * N

while queue:
    u = queue.popleft()
    visited[u] = True
    
    for t in T[u]:
        if not visited[t]:
            plus[t] += plus[u]
            queue.append(t)

print(*plus)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

visited = [False] * N
def dfs(v):
    visited[v] = True
    for u in adj[v]:
        if visited[u]:
            continue
        count[u] += count[v]
        dfs(u)

dfs(0)
print(*count)

Submission status: Accepted

Solution code:
from collections import deque

int1 = lambda x: int(x) - 1

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

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

d = deque([0])
visited = set()
while d:
    v = d.pop()
    visited.add(v)
    for x in T[v]:
        if x not in visited:
            lst[x] += lst[v]
            d.append(x)
print(*lst)

Submission status: Accepted

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

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

n,q=map(int,input().split())
cnt=[0]*(n)
g=[[] for _ in range(n)]
for _ in range(n-1): #木グラフの隣接リストを作成
  a,b=map(int,input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
for _ in range(q):
    a , b = map(int,input().split())
    a = a - 1
    cnt[a] += b

def dfs(now,prev=-1):
  for next in g[now]:
    if next==prev:
      continue
      
    cnt[next]+=cnt[now]
    dfs(next,now)
dfs(0)
print(*cnt)

Submission status: Accepted

Solution code:
import collections
#def input():
#    return sys.stdin.readline()[:-1]
N , Q = map(int,input().split())
graph = [[] for _ in range(N+1)]
point = [0] * (N+1)
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
#print(graph)
for _ in range(Q):
    a , b = map(int,input().split())
    #a = a - 1
    point[a] += b
q=collections.deque()
q.append(1)
checked=[0]*(N+1)

while q:
  v=q.pop()
  checked[v]=1
  
  for u in graph[v]:
    if checked[u]==1:
      continue
      
    point[u]+=point[v]
    q.append(u)
print(*point[1:])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

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

P = [0 for i in range(N)]
for i in range(Q):
  p,x = map(int,readline().split())
  P[p - 1] += x
  
stack = [[0, 0, -1]]
while stack:
  v,point,parent = stack.pop()
  P[v] += point
  for child in G[v]:
    if child == parent:
      continue
    stack.append([child,P[v],v])
  
print(*P)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N, Q = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
Query = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    Query[p-1] += x
ans = [0]*N
past = [0]*N
def dfs(start,point):
    past[start] = 1
    point = point + Query[start]
    ans[start] = point
    for target in edges[start]:
        if past[target] == 0:
            dfs(target,point)
dfs(0,0)
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
# sys.setrecursionlimit(10**7)
 
def main():
    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)]
    # indexがノード
    adj = [[] for _ in range(n+1)]
    for a, b in ab:
            adj[a].append(b)
            adj[b].append(a)
    # indexが直接初めにノードに加えられる得点
    v = [0] * (n+1)
    for p,x in px:
        v[p] += x
    # dequeを使ったキューによるBFS
    # 子をindexで、親ノードを要素で
    parent = [None] * (n+1)
    q = deque([1])
    while q:
        par = q.popleft()
        for chl in adj[par]:
            if chl == parent[par]:
                continue
            v[chl] += v[par]
            parent[chl] = par
            q.append(chl)
    # print(parent)
    # print(v)
    ans = ' '.join(map(str,v[1:]))
    print(ans)   
 
 
    # dequeを使ったスタックによるDFS
    # 子をindexで、親ノードを要素で
    # parent = [None] * (n+1)
    # q = deque([1])
    # while q:
    #     par = q.pop()
    #     for chl in adj[par]:
    #         if chl == parent[par]:
    #             continue
    #         v[chl] += v[par]
    #         parent[chl] = par
    #         q.append(chl)
    # # print(parent)
    # # print(v)
    # ans = ' '.join(map(str,v[1:]))
    # print(ans)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
# sys.setrecursionlimit(10**7)

def main():
    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)]
    adj = [[] for _ in range(n+1)]
    for a, b in ab:
            adj[a].append(b)
            adj[b].append(a)
    # indexが直接初めにノードに加えられる得点
    v = [0] * (n+1)
    for p,x in px:
        v[p] += x
    # 子をindexで、親ノードを要素で
    parent = [None] * (n+1)
    q = deque([1])
    while q:
        par = q.pop()
        for chl in adj[par]:
            if chl == parent[par]:
                continue
            v[chl] += v[par]
            parent[chl] = par
            q.append(chl)
    ans = ' '.join(map(str,v[1:]))
    print(ans)
    
    # def dfs(cur, parent):
    #     for chl in adj[cur]:
    #         print('p', parent)
    #         if chl == parent: 
    #             continue
    #         v[chl] += v[cur]
    #         print('chl,cur', chl, cur)
    #         dfs(chl, cur)

    # dfs(1, 1)
    # ans = ' '.join(map(str,v[1:]))
    # print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections
INF = 10**18

def dfs(s,cnt):
    visited = [False]*n
    visited[s] = True
    q = collections.deque([s])
    while q:
        p = q.pop()
        visited[p] = True
        for v in edge[p]:
            if visited[v]:
                continue
            cnt[v] += cnt[p]
            q.append(v)
    return cnt

if __name__ == "__main__":
    n,q = map(int,input().split())
    edge = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(int,input().split())
        a-=1
        b-=1
        edge[a].append(b)
        edge[b].append(a)
    cnt = [0]*n
    for i in range(q):
        v,x = map(int,input().split())
        v -= 1
        cnt[v] += x
    ans = dfs(0,cnt)
    print(*ans)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
graph=[[] for _ in range(N+1)]
for _ in range(N-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
data=[0 for i in range(N+1)]
visited=[False for i in range(N+1)]
for i in range(Q):
    p,x=map(int,input().split())
    data[p]+=x
    
from collections import deque
d=deque()
e=deque()
visited[1]=True
d.append(1)
while d:
    while d:
        x=d.popleft()
        adder=data[x]
        for node in graph[x]:
            if visited[node]==False:
                visited[node]=True
                data[node]+=adder
                e.append(node)
            else:
                pass
    if e:
        d=e
        e=deque()
print(*data[1:])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

def dfs(now, parent, total):
    result[now] = total + counter[now]
    for child in tree[now]:
        if child == parent:
            continue
        dfs(child, now, result[now])

N, Q = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(N-1)]
P = [list(map(int, input().split())) for _ in range(Q)]

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

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

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

result = [0]*(N+1)
dfs(1, 0, 0)

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = [0 for i in range(n)]

# スタックによるdfs(位置, 上からの加算, 親の位置)
st = deque([(0,0,-1)])
# stが空になるまで操作
while st:
    l = st.pop()
    ans[l[0]] = l[1] + queries[l[0]]
    for v in adj[l[0]]:
        if v != l[2]:
            st.append((v, ans[l[0]], l[0]))
print(*ans)

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
input=sys.stdin.readline
#import bisect
n,q=map(int,input().split())

node=[[] for _ in range(n)]
d=deque()
d.append(0)
for i in range(n-1):
    a,b = map(int,input().split())
    node[a-1].append(b-1)
    node[b-1].append(a-1)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
seen=[0]*n
seen[0]=1
while True:
    if not d:
        break
    i=d.pop()
    for j in node[i]:
        if seen[j]==0:
            d.append(j)
            seen[j]=1
            ans[j]+=ans[i]
print(*ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,q=map(int,input().split())

node=[[] for _ in range(n)]
d=deque()
d.append(0)
for i in range(n-1):
    a,b = map(int,input().split())
    node[a-1].append(b-1)
    node[b-1].append(a-1)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
seen=[0]*n
seen[0]=1
while True:
    if not d:
        break
    i=d.pop()
    for j in node[i]:
        if seen[j]==0:
            d.append(j)
            seen[j]=1
            ans[j]+=ans[i]
print(*ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,q=map(int,input().split())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[[] for _ in range(n)]
d=deque()
d.append(0)
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
seen=[0]*n
seen[0]=1
while d:
   
    i=d.pop()
    for j in node[i]:
        if seen[j]==0:
            d.append(j)
            seen[j]=1
            ans[j]+=ans[i]
print(*ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,q=map(int,input().split())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[[] for _ in range(n)]
d=deque()
d.append(0)
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
seen=[0]*n
seen[0]=1
while True:
    if not d:
        break
    i=d.pop()
    for j in node[i]:
        if seen[j]==0:
            d.appendleft(j)
            seen[j]=1
            ans[j]+=ans[i]
print(*ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,q=map(int,input().split())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[[] for _ in range(n)]
d=deque()
d.append(0)
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
seen=[0]*n
seen[0]=1
while True:
    if not d:
        break
    i=d.pop()
    for j in node[i]:
        if seen[j]==0:
            d.append(j)
            seen[j]=1
            ans[j]+=ans[i]
print(*ans)