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(500000)
N, Q, *D = map(int, open(0).read().split())
val = [0 for _ in range(N+1)]
E = [[] for _ in range(N+1)]
D = list(zip(*[iter(D)]*2))
assert(len(D) == N+Q-1)
for i in range(N+Q-1):
  l, r = D[i][0], D[i][1]
  if i < N - 1:
  	E[l].append(r)
  	E[r].append(l)
  else:
    val[l] += r
visited = [False for _ in range(N+1)]
def dfs(c):
  visited[c] = True
  for ch in E[c]:
    if not visited[ch]:
      val[ch] += val[c]
      dfs(ch)
dfs(1)
print(' '.join(map(str, val[1:N+1])))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

root_node = (1, -1) # (id, value, parent_id)
open_list = [root_node]
closed_list = []
while True:
    if len(open_list) == 0:
        break
    cur_node = open_list.pop()
    cur_id, parent_id = cur_node
    if not(parent_id == -1):
        cnt[cur_id] += cnt[parent_id]
    for child_id in edge[cur_id]:
        if child_id == parent_id:
            continue
        open_list.append((child_id, cur_id))
print(*cnt[1:])

Submission status: Accepted

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

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

bond_lst = list([list(map(int,input().split())) for _ in range(N-1)])
      
point_lst = [0]*(N+1)

for _ in range(Q):
    a, b = map(int, input().split())
    point_lst[a] += b

graph = {}

for a, b in bond_lst:
    if a in graph:graph[a].append(b)
    else:graph[a] = [b]
    if b in graph:graph[b].append(a)
    else:graph[b] = [a]
      
passed = [0]*(N+1)
nxt_lst = [1]
while nxt_lst:
    nxt = nxt_lst.pop()
    for i in graph[nxt]:
        if passed[i] == 1:continue
        point_lst[i] += point_lst[nxt]
        nxt_lst.append(i)
    passed[nxt] = 1
print(*point_lst[1:])

Submission status: Accepted

Solution code:
import sys
from collections import deque
#N,Q = list(map(int,input().split()))
N,Q = [int(i) for i in input().split()]
G=[]
for i in range(N):
    G.append([])

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

p=[0]*Q
x=[0]*Q
c=[0]*N

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

stack=deque([0])
parent = [-1]*N

while(stack):
    v = stack.pop()
    for u in G[v]:
        if u!=parent[v]:
            c[u]+=c[v]
            parent[u]=v
            stack.append(u)


ans = ' '.join([str(x) for x in c])

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
#N,Q = list(map(int,input().split()))
N,Q = [int(i) for i in sys.stdin.readline().split()]
G=[]
for i in range(N):
    G.append([])

for i in range(N-1):
    #a,b = list(map(int,input().split()))
    a,b = [int(j) for j in sys.stdin.readline().split()]
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

p=[0]*Q
x=[0]*Q
c=[0]*N

for i in range(Q):
    #p,x = list(map(int,input().split()))
    p,x = [int(j) for j in sys.stdin.readline().split()]
    p-=1
    c[p] += x

stack=deque([0])
parent = [-1]*N

while(stack):
    v = stack.pop()
    for u in G[v]:
        if u!=parent[v]:
            c[u]+=c[v]
            parent[u]=v
            stack.append(u)


ans = ' '.join([str(x) for x in c])

print(ans)

Submission status: Accepted

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

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

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

stack=[0]
parent = [-1]*N

while(stack):
    v = stack.pop()
    for u in G[v]:
        if u!=parent[v]:
            c[u]+=c[v]
            parent[u]=v
            stack.append(u)


ans = ' '.join([str(x) for x in c])

print(ans)

Submission status: Accepted

Solution code:
'''
pythonの再帰は10^5timesですら厳しい
import sys
sys.setrecursionlimit(10000000)

def dfs(v,p,G,c):
    for u in G[v]:
        if u!=p:
            c[u]+=c[v]
            dfs(u,v,G,c) 
'''

from collections import deque

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

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

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

stack=deque([0])
parent = [-1]*N

while(stack):
    v = stack.pop()
    for u in G[v]:
        if u!=parent[v]:
            c[u]+=c[v]
            parent[u]=v
            stack.append(u)


ans = ' '.join([str(x) for x in c])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

stack=deque([0])
parent = [-1]*N

while(stack):
    v = stack.pop()
    for u in G[v]:
        if u!=parent[v]:
            c[u]+=c[v]
            parent[u]=v
            stack.appendleft(u)


ans = ' '.join([str(x) for x in c])

print(ans)

Submission status: Accepted

Solution code:
'''
pythonの再帰は10^5timesですら厳しい
import sys
sys.setrecursionlimit(10000000)

def dfs(v,p,G,c):
    for u in G[v]:
        if u!=p:
            c[u]+=c[v]
            dfs(u,v,G,c) 
'''
from collections import deque

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

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

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

stack=deque([0])
parent = [-1]*N

while(stack):
    v = stack.pop()
    for u in G[v]:
        if u!=parent[v]:
            c[u]+=c[v]
            parent[u]=v
            stack.appendleft(u)


ans = ' '.join([str(x) for x in c])

print(ans)

Submission status: Accepted

Solution code:
#今日の精進
#KI
n,q=map(int,input().split())
Node=[0 for i in range(n+1)]
visited=[ False for i in range(n+1)]
from collections import deque
ki_list={i: [] for i in range(1,n+1)}
for i in range( n-1):
    a,b=map(int,input().split())
    ki_list[a].append(b)
    ki_list[b].append(a)
visited[1]=True
d=deque()
e=deque()
d.append(1)
#点の保存リスト
for _ in range(q):
    node,score=map(int,input().split())
    Node[node]+=score

while d:
    for some in d:               
        for point in ki_list[some]:
            if visited[point]==False:
                visited[point]=True
                Node[point]+=Node[some]
                e.append(point)
            elif visited[point]==True:
              pass

    d=e
    e=deque()
print(*Node[1:])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
scores = [0 for _ in range(N)]
flags = [1 for _ in range(N)]

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

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

from collections import deque
nextp = deque([0])
flags[0] = 0
while nextp:
    p = nextp.pop()
    for t in tree[p]:
        if flags[t]:
            scores[t] += scores[p]
            flags[t] = 0
            nextp.append(t)
print(*scores)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
E=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
X=[0]*N
for i in range(Q):
  p,x=map(int,input().split())
  X[p-1]+=x
  
stack=[]
stack.append([0,0,-1])
ans=[0]*N
while stack:
  node=stack.pop()
  v=node[0]
  val=node[1]
  parent=node[2]
  ans[v]+=val+X[v]
  children=E[v]
  for child in children:
    if child==parent:
      continue
    stack.append([child,ans[v],v])

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque


def solve():
    N, Q = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for i in range(N-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    val = [0 for _ in range(N + 1)]
    for i in range(Q):
        p, x = map(int, input().split())
        val[p] += x

    que = deque([1])
    parent = [0 for _ in range(N+1)]
    while que:
        i = que.popleft()
        for j in graph[i]:
            if j == parent[i]:
                continue
            parent[j] = i
            que.append(j)
            val[j] += val[i]

    print(*val[1:])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import queue


def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())

    edges = {i : [] for i in range(1, N+1)}
    for i in range(N-1):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)
    
    values = {i : 0 for i in range(1, N+1)}
    for i in range(Q):
        p, x = map(int, input().split())
        values[p] += x
    
    has_noparent = {i : True for i in range(1, N+1)}
    has_noparent[1] = False
    
    q = queue.Queue()
    q.put(1)
    
    children = {i : [] for i in range(1, N+1)}
    while not q.empty():
        parent = q.get()
        value_parent = values[parent]
        for child in edges[parent]:
            if has_noparent[child]:
                values[child] += value_parent
                q.put(child)
                has_noparent[child] = False

    ret = [str(i) for i in values.values()]
    ret = ' '.join(ret)
    print(ret)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, Q = map(int, input().split())
    V = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        V[a - 1].append(b - 1)
        V[b - 1].append(a - 1)
    C = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        C[p - 1] += x
    cur = [(0, 0, -1)]
    while cur:
        n, x, f = cur.pop()
        C[n] = x = C[n] + x
        for c in V[n]:
            if c != f:
                cur.append((c, x, n))
    print(' '.join(str(c) for c in C))

main()

Submission status: Accepted

Solution code:
def main():
    N, Q = [int(i) for i in input().split()]
    V = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].append(b)
        V[b].append(a)
    C = [0] * N
    for _ in range(Q):
        p, x = [int(i) for i in input().split()]
        C[p - 1] += x
    cur = [(0, 0, -1)]
    while cur:
        n, x, f = cur.pop()
        C[n] = x = C[n] + x
        for c in V[n]:
            if c != f:
                cur.append((c, x, n))
    print(' '.join(str(c) for c in C))

main()

Submission status: Accepted

Solution code:
def main():
    N, Q = [int(i) for i in input().split()]
    V = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(b)
        V[b].add(a)
    C = [0] * N
    for _ in range(Q):
        p, x = [int(i) for i in input().split()]
        C[p - 1] += x
    cur = [(0, 0)]
    while cur:
        n, x = cur.pop()
        C[n] = x = C[n] + x
        for c in V[n]:
            V[c].remove(n)
            cur.append((c, x))
    print(' '.join(str(c) for c in C))

main()

Submission status: Accepted

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

def main():
    N, Q = [int(i) for i in input().split()]
    V = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(b)
        V[b].add(a)
    C = [0] * N
    for _ in range(Q):
        p, x = [int(i) for i in input().split()]
        C[p - 1] += x
    cur = [(0, 0)]
    while cur:
        nxt = []
        for n, x in cur:
            C[n] = x = C[n] + x
            for c in V[n]:
                V[c].remove(n)
                nxt.append((c, x))
        cur = nxt
    print(' '.join(str(c) for c in C))

main()

Submission status: Accepted

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

stack = [0]
j = [False] * n # すでに探索したか
while stack:
    node = stack.pop()
    j[node] = True
    for snode in tree[node]:
        if j[snode]:
            continue
        c[snode] += c[node]
        stack.append(snode)

print(*c)

Submission status: Accepted

Solution code:
from collections import deque

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

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

S = deque([(1, 0)])
while S:
    v, p = S.popleft()
    for t in T[v]:
        if t == p:
            continue
        C[t] += C[v]
        S.append((t, v))

print(*C[1:])

Submission status: Accepted

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

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

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

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

check = [0 for _ in range(n)]
def dfs(st) :
  check[st] = 1
  for ne in tree[st] :
    if check[ne] == 1 :
      continue
    ans[ne] += ans[st]
    dfs(ne)

dfs(0)

print(*ans)

Submission status: Accepted

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

l = [[] for i in range(N)]

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

used = [False] * N
r = [0] * N

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

stack = [0]
while stack:
  i = stack.pop()
  used[i] = True
  for to in l[i]:
    if not used[to]:
      stack.append(to)
      r[to] += r[i]

print(*r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
for ab in AB:
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])
val = [0] * (N+1)
for px in PX:
    val[px[0]] += px[1]
parent = [0] * (N+1)
Q  = [1]
while Q:
    q = Q.pop()
    for c in graph[q]:
        if c == parent[q]:
            continue
        parent[c] = q
        Q.append(c)
        val[c] += val[q]
print(*val[1:])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
for ab in AB:
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])
val = [0] * (N+1)
for px in PX:
    val[px[0]] += px[1]
parent = [0] * (N+1)
Q  = [1]
while Q:
    q = Q.pop()
    for c in graph[q]:
        if c == parent[q]:
            continue
        parent[c] = q
        Q.append(c)
        val[c] += val[q]
print(*val[1:])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q = map(int,readline().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:N+N-2])
PX = iter(ABPX[N+N-2:])

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

val = [0] * (N+1)
for p,x in zip(PX,PX):
    val[p] += x

from collections import deque
stack = deque([1])

parent = [0] * (N+1)
while stack:
    x = stack.popleft()
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        val[y] += val[x]
print(*val[1:])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q = map(int,readline().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:N+N-2])
PX = iter(ABPX[N+N-2:])

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

val = [0] * (N+1)
for p,x in zip(PX,PX):
    val[p] += x

stack = [1]

parent = [0] * (N+1)
while stack:
    x = stack.pop()
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        val[y] += val[x]
print(*val[1:])

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
for ab in AB:
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])
val = [0] * (N+1)
for px in PX:
    val[px[0]] += px[1]
parent = [0] * (N+1)
from collections import deque
Q  = deque([1])
while Q:
    q = Q.popleft()
    for c in graph[q]:
        if c == parent[q]:
            continue
        parent[c] = q
        Q.append(c)
        val[c] += val[q]
print(*val[1:])

Submission status: Accepted

Solution code:
import sys

n, q = [int(i) for i in sys.stdin.readline().split()]
graph = {i: [] for i in range(n)}
ct = [0 for i in range(n)]
for i in range(n - 1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

for i in range(q):
    p, x = [int(i) for i in sys.stdin.readline().split()]
    p -= 1
    ct[p] += x
already = {0}
stack = [(0, ct[0], -1)]
res = [0 for i in range(n)]
while len(stack) > 0:
    cur, cost, _from = stack.pop(-1)
    res[cur] = cost
    for _next in graph[cur]:
        if _next == _from:
            continue
        next_cost = ct[_next]
        stack.append((_next, cost + next_cost, cur))
        already.add(cur)
print(" ".join([str(r) for r in res]))

Submission status: Accepted

Solution code:
# 
from collections import deque
n,q = map(int,input().split())
G = [[] for _ in range(n)]
ans = [0]*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)

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

q = deque([0])
visited=[False]*n

while q:
    v=q.pop()
    visited[v]=True
    for e in G[v]:
        if visited[e]:
            continue
        ans[e]+=ans[v]
        q.append(e)
print(*ans)

Submission status: Accepted

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

ct=[0 for _ in range(n)]   #Qの累計
for i in range(q):
  p,x=[int(s) for s in input().split()]
  p-=1
  ct[p]+=x

#深さ優先探索
stack=[(0, ct[0], -1)]
ans=[0 for _ in range(n)]
while stack:
  vrt, cost, _from = stack.pop(-1)
  ans[vrt] = cost
  for _to in graph[vrt]:
    if _to ==_from:
      continue
    stack.append((_to, cost+ct[_to],vrt))
print(*ans)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
nei_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    nei_list[a].append(b)
    nei_list[b].append(a)
score = [0] * (n+1)
for i in range(q):
    p, x = map(int, input().split())
    score[p] += x
work_stack = [1]
visited = set()
while work_stack:
    i = work_stack.pop()
    visited.add(i)
    for j in nei_list[i]:
        if j not in visited:
            work_stack.append(j)
            score[j] += score[i]
print(*score[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
s=sys.stdin.readlines()
n,q=map(int,s[0].split())
G=[[]*n for i in range(n)]
P=[0]*n
V=[0]*n
for e in s[1:n]:
    a,b=map(int,e.split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for e in s[n:]:
    c,d=map(int,e.split())
    P[c-1]+=d
def dsf(i,p):
    V[i]=1
    P[i]+=p
    for j in G[i]:
        if V[j]!=1:
            dsf(j,P[i])
dsf(0,0)
print(' '.join(map(str,P)))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N, Q = map(int, input().split())
tree = defaultdict(list)
counter = [0] * N
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

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

visited = [False] * N

queue = deque()
queue.append(0)
while queue:
    parent = queue.popleft()
    visited[parent] = True
    for child in tree[parent]:
        if not visited[child]:
            counter[child] += counter[parent]
            queue.append(child)

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
l = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    l[a - 1].append(b - 1)
    l[b - 1].append(a - 1)
r = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    r[p - 1] += x
stack = [0]
used = [False] * n    
while stack:
    i = stack.pop()
    used[i] = True
    for to in l[i]:
        if not used[to]:
            stack.append(to)
            r[to] += r[i]
for t_r in r:
    print(t_r)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
s=sys.stdin.readlines()
n,q=map(int,s[0].split())
G=[[]*n for i in range(n)]
P=[0]*n
V=[0]*n
R=[0]*n
for e in s[1:n]:
    a,b=map(int,e.split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for e in s[n:]:
    c,d=map(int,e.split())
    P[c-1]+=d

def dsf(i,p):
    V[i]=1
    R[i]+=p+P[i]
    p=0
    for j in G[i]:
        if V[j]!=1:
            dsf(j,R[i])
dsf(0,0)
print(' '.join(map(str,R)))

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
E=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  E[a].append(b)
  E[b].append(a)
  
P=[0]*N
for i in range(Q):
  p,x=map(int,input().split())
  P[p-1]+=x
  
ans=[0]*N
stack=[]
# 点,親,ポイント
stack.append([0,-1,0])
while stack:
  node=stack.pop()
  v=node[0]
  parent=node[1]
  point=node[2]
  point+=P[v]
  ans[v]=point
  children=E[v]
  for child in children:
    if child==parent:
      continue
    stack.append([child,v,point])
    
print(*ans)

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
 
def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])
 
dfs(1,0,0)
 
answer = ' '.join(map(str,value[1:]))
print(answer)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
C = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  C[a-1].append(b-1)
  C[b-1].append(a-1)
dist = [-1]*n
dist[0] = 1
A = [0]*n
F = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  F[p-1] += x
S = [0]
T = [0]
while S:
  v = S.pop()
  for nv in C[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v] + 1
      S.append(nv)
while T:
  v = T.pop()
  A[v] += F[v]
  for nv in C[v]:
    if dist[nv] > dist[v]:
      A[nv] += A[v]
      T.append(nv)
print(*A)

Submission status: Accepted

Solution code:
import sys

n, q = [int(i) for i in sys.stdin.readline().split()]
graph = {i: [] for i in range(n)}
ct = [0 for i in range(n)]
for i in range(n - 1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

for i in range(q):
    p, x = [int(i) for i in sys.stdin.readline().split()]
    p -= 1
    ct[p] += x
already = {0}
stack = [(0, ct[0], -1)]
res = [0 for i in range(n)]
while len(stack) > 0:
    cur, cost, _from = stack.pop(-1)
    res[cur] = cost
    for _next in graph[cur]:
        if _next == _from:
            continue
        next_cost = ct[_next]
        stack.append((_next, cost + next_cost, cur))
        already.add(cur)
print(" ".join([str(r) for r in res]))

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)]

ki = [[]for _ in range(N)]
for a,b in AB:
    a-=1
    b-=1
    ki[a].append(b)
    ki[b].append(a)
point = [0]*(N)
for p,x in PX:
    p-=1
    point[p]+=x
def dfs(now, last ,add):
    point[now]+= add
    for x in ki[now]:
        if (x == last):continue
        dfs(x,now,point[now])
dfs(0,0,0)
print(*point)

Submission status: Accepted

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

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

Q = [(0, -1)]
while Q:
    v, p = Q.pop()
    for x in E[v]:
        if x == p: # 孫と祖で一致していないかのチェック
            continue
        C[x] += C[v] # 親から子へ
        Q.append((x, v))

print(*C)

Submission status: Accepted

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

l = [[] for i in range(N)]

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

used = [False] * N
r = [0] * N

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

stack = [0]
while stack:
  i = stack.pop()
  used[i] = True
  for to in l[i]:
    if not used[to]:
      stack.append(to)
      r[to] += r[i]

print(*r)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)

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

    Q=[(0,-1)]
    while(Q):
        v,p=Q.pop()
        for nv in E[v]:
            if(p==nv): continue
            C[nv]+=C[v]
            Q.append((nv,v))

    print(*C)
resolve()

Submission status: Accepted

Solution code:
from collections import deque
N, Q = 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)]
tree = [[] for _ in range(N)]
ans = [0]*N
for a,b in ab:
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)
  
for p,x in px:
  ans[p-1]+=x
  
q = deque([0])
judge = [False]*N
while q:
  a=q.pop()
  judge[a]=True
  for i in tree[a]:
    if judge[i]:
      continue
    ans[i]+=ans[a]
    q.append(i)
    
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
import heapq

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

node = [0]*N
edge = [[] for _ in range(N)]
color = [0]*N

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

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

stack = [0]
while stack:
    s = stack.pop()
    color[s] = 1
    for t in edge[s]:
        if color[t]==0:
            stack.append(t)
            node[t] += node[s]
    color[s]=2

print(*node)

Submission status: Accepted

Solution code:
from collections import deque

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)

counter = [0] * N
checked = [False] * N

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

queue = deque()
queue.append(0)

while queue:
    root = queue.pop()
    checked[root] = True
    for e in edges[root]:
        if checked[e] == False:
            queue.append(e)
            counter[e] += counter[root]

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

d = deque()
d.append(1)
chked = set()
while d:
    stat = d.pop()
    chked.add(stat)
    for v in t[stat]:
        if v not in chked:
            d.append(v)
            cnt[v] += cnt[stat]

print(*cnt[1:])