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:
def main():
  import sys
  sys.setrecursionlimit(500000)
  input = sys.stdin.readline

  N, Q = map(int, input().split())
  G = [set() for _ in range(N)]
  cnt = [0]*N
  visited = [0]*N

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

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

  visited[0]=1
  st = [0]
  while st:
      v = st.pop()
      for u in G[v]:
          if visited[u]:
              continue
          visited[u] = 1
          cnt[u] += cnt[v]
          st.append(u)    

  print(*cnt)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

N, Q = map(int, input().split())
G = [set() for _ in range(N)]
cnt = [0]*N
visited = [0]*N

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

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

visited[0]=1
st = [0]
while st:
    v = st.pop()
    for u in G[v]:
        if visited[u]:
            continue
        visited[u] = 1
        cnt[u] += cnt[v]
        st.append(u)    

print(*cnt)

Submission status: Accepted

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

N, Q = map(int, input().split())
G = [set() for _ in range(N)]
cnt = [0]*N
visited = [0]*N

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

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

visited[0]=1
st = [0]
while st:
    v = st.pop()
    for u in G[v]:
        if visited[u]:
            continue
        visited[u] = 1
        cnt[u] += cnt[v]
        st.append(u)    

print(*cnt)

Submission status: Accepted

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

N, Q = map(int, input().split())
G = [set() for _ in range(N)]
cnt = [0]*N
visited = [0]*N

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

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

visited[0]=1
st = [0]
while st:
    v = st.pop()
    for u in G[v]:
        if visited[u]:
            continue
        visited[u] = 1
        cnt[u] += cnt[v]
        st.append(u)    

print(*cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

N, Q = map(int, input().split())
G = [set() for _ in range(N)]
cnt = [0]*N
visited = [0]*N

def dfs(start_node):
    for i in G[start_node]:
        if visited[i]==0:
            visited[i]=1
            cnt[i] += cnt[start_node]
            dfs(i)

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

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

visited[0]=1
#dfs(0)
st = [0]
while st:
    v = st.pop()
    for u in G[v]:
        if visited[u]: continue
        visited[u] = 1
        cnt[u] += cnt[v]
        st.append(u)    

print(*cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

N, Q = map(int, input().split())
G = [set() for _ in range(N)]
cnt = [0]*N
visited = [0]*N

def dfs(start_node):
    for i in G[start_node]:
        if visited[i]==0:
            visited[i]=1
            cnt[i] += cnt[start_node]
            dfs(i)

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

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

visited[0]=1
#dfs(0)
st = [0]
while st:
    v = st.pop()
    for u in G[v]:
        if visited[u]: continue
        visited[u] = 1
        cnt[u] += cnt[v]
        st.append(u)    

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    g = [set() for _ in range(n)]
    for _ in range(n - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

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

    st = [0]
    used = [0] * n
    used[0] = 1
    while st:
        v = st.pop()
        for u in g[v]:
            if used[u]: continue
            used[u] = 1
            ctr[u] += ctr[v]
            st.append(u)
    print(*ctr)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

g = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add(b)
    g[b].add(a)

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

st = [0]
used = [0] * n
used[0] = 1
while st:
    v = st.pop()
    for u in g[v]:
        if used[u]: continue
        used[u] = 1
        ctr[u] += ctr[v]
        st.append(u)
print(*ctr)

Submission status: Accepted

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

g = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add(b)
    g[b].add(a)

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

st = [(0, -1)]
while st:
    v, par = st.pop()
    for u in g[v]:
        if u == par: continue
        ctr[u] += ctr[v]
        st.append((u, v))
print(*ctr)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
def solve(N: int, Q: int, a: "List[int]", b: "List[int]", p: "List[int]", x: "List[int]"):
    answer = [0]*N
    linked_list = [[] for _ in range(N)]
    for i in range(N-1):
        linked_list[a[i]-1].append(b[i]-1)
        linked_list[b[i]-1].append(a[i]-1)
    
    c = [0]*N
    is_Visited = [False]*N

    for j in range(Q):
        c[p[j]-1] += x[j]
    answer[0] = c[0]
    
    def dfs(node,counter):
        counter += c[node]
        is_Visited[node] = True
        for n in linked_list[node]:
            if is_Visited[n] == False:
                answer[n] = dfs(n,counter)
        
        return counter
        
    dfs(0,0)
    print(*answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    x = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, Q, a, b, p, x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq as h
import sys

input=sys.stdin.readline

N,Q=map(int,input().split())
a=[0 for i in range(0,N-1)]
b=[0 for i in range(0,N-1)]
for i in range(0,N-1):
    a[i],b[i]=map(int,input().split())
p=[0 for i in range(0,Q)]
x=[0 for i in range(0,Q)]
for i in range(0,Q):
    p[i],x[i]=map(int,input().split())
hen=[[] for i in range(0,N+1)]
for i in range(0,N-1):
    hen[a[i]].append(b[i])
    hen[b[i]].append(a[i])
subscore=[0 for i in range(0,N+1)]
for i in range(0,Q):
    subscore[p[i]]+=x[i]

ans=[0 for i in range(0,N+1)]
flag=[0 for i in range(0,N+1)]
q=[]
q.append(1)
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        ans[x]+=subscore[x]
        flag[x]=1
        for p in hen[x]:
            if flag[p]==0:
                h.heappush(sub,p)
                ans[p]=ans[x]
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break
ans[0]=-1
ans.remove(-1)
print(*ans)

Submission status: Accepted

Solution code:
import heapq as h

N,Q=map(int,input().split())
a=[0 for i in range(0,N-1)]
b=[0 for i in range(0,N-1)]
for i in range(0,N-1):
    a[i],b[i]=map(int,input().split())
p=[0 for i in range(0,Q)]
x=[0 for i in range(0,Q)]
for i in range(0,Q):
    p[i],x[i]=map(int,input().split())
hen=[[] for i in range(0,N+1)]
for i in range(0,N-1):
    hen[a[i]].append(b[i])
    hen[b[i]].append(a[i])
subscore=[0 for i in range(0,N+1)]
for i in range(0,Q):
    subscore[p[i]]+=x[i]

ans=[0 for i in range(0,N+1)]
flag=[0 for i in range(0,N+1)]
q=[]
q.append(1)
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        ans[x]+=subscore[x]
        flag[x]=1
        for p in hen[x]:
            if flag[p]==0:
                h.heappush(sub,p)
                ans[p]=ans[x]
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break
ans[0]=-1
ans.remove(-1)
print(*ans)

Submission status: Accepted

Solution code:
#23:29
n,m = 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)
cnt = [0 for _ in range(n)]
for _ in range(m):
  a,x = map(int,input().split())
  a -= 1
  cnt[a] += x
now = [0]
seen = [0 for _ in range(n)]
seen[0] = 1
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        now.append(y)
        cnt[y] += cnt[x]
print(' '.join(list(map(str,cnt))))

Submission status: Accepted

Solution code:
N,Q = [int(i) for i in input().split()]
graph = [[] for _ in range(N+1)]
ans = [0] * (N+1)
for i in range(N-1):
    a,b = [int(j) for j in input().split()]
    graph[a].append(b)
    graph[b].append(a)
for i in range(Q):
    pa,xaa = [int(j) for j in input().split()]
    ans[pa] += xaa

seen = [False] * (N+1)

import collections
from collections import deque
que = deque()
que.append(1)
seen[1] = True
while len(que) != 0:
    x = que.popleft()
    seta = set(graph[x])
    for i in seta:
        if seen[i]:
            continue
        ans[i] += ans[x]
        que.append(i)
        seen[i] = True
print(*ans[1:])

Submission status: Accepted

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

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

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

stack = [0]
parent = [0]*n
order = []

while stack:
    x = stack.pop()
    order.append(x)
    for i in ki[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)

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

for x in order:
    count = query[x]
    for y in ki[x]:
        if y == parent[x]:
            continue
        query[y] += count

print(*query)

Submission status: Accepted

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

from collections import deque
s = deque()
s.append(0)
visit = [False]*n
visit[0] = True

while s:
    x = s.pop()
    for new_x in g[x]:
        if visit[new_x] == True:
            continue
        l[new_x] += l[x]
        s.append(new_x)
        visit[new_x] = True

print(*l)

Submission status: Accepted

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

from collections import deque
s = deque()
s.append(0)
visit = [False]*n
visit[0] = True

while s:
    x = s.pop()
    for new_x in g[x]:
        if visit[new_x] == True:
            continue
        l[new_x] += l[x]
        s.append(new_x)
        visit[new_x] = True

print(*l)

Submission status: Accepted

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

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


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

stack=[0]
check = [-1]*n
check[0] = 0

while len(stack):
    v = stack.pop()
    for i in root[v]:
        if i != check[i]:
            dp[i] += dp[v]
            check[i]=i
            stack.append(i)

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

Submission status: Accepted

Solution code:
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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


treeList = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  treeList[a].append(b) # a<bとは限らないため、双方向にする
  treeList[b].append(a)

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


def treeTrace(crnt, prnt):
    for chld in treeList[crnt]:
        if prnt == chld:
            continue
        ans[chld] += ans[crnt]

        treeTrace(chld, crnt)

treeTrace(0, -1)

for s in ans:
    print(int(s), end =" ")

Submission status: Accepted

Solution code:
import sys

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

px = zip(*[map(int, sys.stdin.read().split())] * 2)

def main():
    value = [0] * (n + 1)
    for p, x in px:
        value[p] += x
    
    stack = [1]
    par = [None] * (n + 1)
    while stack:
        u = stack.pop()
        for v in g[u]:
            if v != par[u]:
                par[v] = u
                value[v] += value[u]
                stack.append(v)
    
    return value[1:]
    
if __name__ == '__main__':
    ans = main()
    print(*ans, sep=' ')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = [[] for i in range(n)]
sc = [0]*n
  
for i in range(n-1):
  x,y = map(int, input().split())
  l[x-1].append(y-1)
  l[y-1].append(x-1)

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

from collections import deque
d=deque()
d.append(0)
t = [False]*(n)
t[0] = True

while d:
    a = d.popleft()
    for b in l[a]:
      if not t[b]:
          t[b] = True
          d.append(b)
          sc[b] += sc[a]

print(*sc)

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 functools import lru_cache
import bisect
import re
import queue


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 [input() 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 [int(input()) 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 roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(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 divisor(n):
        i = 1
        table = []
        while i * i <= n:
            if n % i == 0:
                table.append(i)
                table.append(n // i)
            i += 1
        table = list(set(table))
        return table


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)

    def list(self):
        return self.__q


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    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)
    P = [0 for _ in range(N)]
    for _ in range(Q):
        p, x = Scanner.map_int()
        p -= 1
        P[p] += x

    q = []
    q.append(0)
    visited = [False] * N
    while q != []:
        v = q.pop()
        visited[v] = True
        for g in G[v]:
            if visited[g]:
                continue
            P[g] += P[v]
            q.append(g)
    print(*P)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,q=map(int,input().split())
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)

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

que=deque([0])
f=[0]*n
f[0]=1
while que:
  v=que.popleft()
  c=s[v]
  for w in g[v]:
    if f[w]:
      continue
    f[w]=1
    s[w]+=c
    que.append(w)
  
print(*s)

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
G=[[] for _ in range(N+1)]
#このような木に関する問題では、木の代わりに 1−2−3−...−N という直線的なグラフを考えると助け になることがある
cnt=[0]*(N+1)
from collections import deque
for _ in range(N-1):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)

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

queue=deque([1])
visited={1}
while queue:
    tmp=queue.popleft()
    visited.add(tmp)
    for t in G[tmp]:
        if t in visited:
            pass
        else:
            queue.append(t)
            cnt[t]+=cnt[tmp]

print(*cnt[1:])

Submission status: Accepted

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

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

from collections import defaultdict
d = defaultdict(int)
for i in range(q):
    tmp = list(map(int,input().split()))
    d[tmp[0]-1]+=tmp[1]

from collections import deque
ans =[0]*n
finish  = {0}
Q = deque()
Q.append([0,0])
while Q:
    node= Q.popleft()
    finish.add(node[0])

    val = node[1] + d[node[0]]
    ans[node[0]]+=val

    for nxt in link[node[0]]:
        if nxt in finish:
            pass
        else:
            Q.append([nxt,val])

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque


def BFS(G, counter, N):
    que = deque([0])
    ans = [-1 for i in range(N)]
    ans[0] = counter[0]

    while que:
        v = que.popleft()
        n = counter[v]
        for w in G[v]:
            if ans[w] > -1:
                continue
            counter[w] += n
            ans[w] = counter[w]

            que.append(w)

    return ans


N, Q = map(int, input().split())
G = [[] for i 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)

counter = [0 for i in range(N)]

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

ans = BFS(G, counter, N)
print(*ans)

Submission status: Accepted

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

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


ab_list = [[] for _ in range(n+1) ]
for _ in range(n-1):
  a, b = map(int, input().split())
  ab_list[a].append(b)
  ab_list[b].append(a)
  
px_list = [0]*(n+1)
for _ in range(q):
  p,x = map(int, input().split())
  px_list[p] += x
  
stack = [1]
par_list = [0] * (n+1)

while stack:
  x = stack.pop()
  for y in ab_list[x]:
    if y == par_list[x]:
      continue
    par_list[y] = x
    stack.append(y)
    px_list[y] += px_list[x]

print(' '.join(str(i) for i in px_list[1:]))

Submission status: Accepted

Solution code:
from collections import deque
n, q = map(int, input().split())
tree = [[] for _ in range(n+1)]
cnt = [0] * (n+1)

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())
    cnt[p] += x

queue = deque([1])
visited = {1}
while queue:
    now = queue.popleft()
    visited.add(now)
    for t in tree[now]:
        if t in visited:
            pass
        else:
            queue.append(t)
            cnt[t] += cnt[now]

print(*cnt[1:])

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = lr()
    edges[a].append(b)
    edges[b].append(a)

counter = [0] * (N+1)
for _ in range(Q):
    p, x = lr()
    counter[p] += x

parents = [0] * (N+1)

def bfs(x):
    p = parents[x]
    c = counter[x]
    for y in edges[x]:
        if y == p:
            continue
        counter[y] += c
        parents[y] = x
        bfs(y)

bfs(1)
print(*counter[1:])
# 09

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = lr()
    edges[a].append(b)
    edges[b].append(a)

counter = [0] * (N+1)
for _ in range(Q):
    p, x = lr()
    counter[p] += x

parents = [0] * (N+1)

def bfs(x):
    for y in edges[x]:
        if y == parents[x]:
            continue
        counter[y] += counter[x]
        parents[y] = x
        bfs(y)

bfs(1)
print(*counter[1:])
# 09

Submission status: Accepted

Solution code:
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)]

data=[[] for i in range(N+1)]
for a,b in ab:
    data[a].append(b)
    data[b].append(a)

count=[0]*(N+1)
for p,x in px:
    count[p]+=x

#dfsをする。
que=[1]

#一度通った頂点は、1にする。
flag=[0]*(N+1)
flag[1]=1
while que:
    u=que.pop()
    for v in data[u]:
        if flag[v]==0:
            flag[v]=1
            count[v]+=count[u]
            que.append(v)

print(*count[1:])

Submission status: Accepted

Solution code:
from collections import deque
def main():
  _map, _input, _int = map, input, int
  n, q = _map(_int, _input().split())
  values = [0] * n
  links = [[] for _ in range(n)]
  for _ in range(n - 1):
    a, b = _map(_int, _input().split())
    links[a - 1].append(b - 1)
    links[b - 1].append(a - 1)
  for _ in range(q):
    p, x = _map(_int, _input().split())
    values[p - 1] += x
  d = deque()
  d.append((0, -1))
  while len(d) != 0:
    i, p = d.pop()
    for j in links[i]:
      if j == p:
        continue
      values[j] += values[i]
      d.append((j, i))
  print(*values)
main()

Submission status: Accepted

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

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

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

main()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)
from collections import deque

S = input().split(" ")
N = int(S[0])
Q = int(S[1])

arr = []
prr = []
for i in range(N-1):
    S = input().split(" ")
    ar = [int(S[0]),int(S[1])]
    arr.append(ar)

for i in range(Q):
    S = input().split(" ")
    pr = [int(S[0]), int(S[1])]
    prr.append(pr)



def prepare(n, q, arr, prr):
    links = [[] for _ in range(n)]
    values = [0 for _ in range(n)]
    finalValues = [0 for _ in range(n)]
    for ar in arr:
        start = ar[0] - 1
        end = ar[1] - 1
        links[start].append(end)
        links[end].append(start)

    for pr in prr:
        i = pr[0] - 1
        x = pr[1]
        values[i] += x

    return links, values, finalValues


links, values, finalValues = prepare(N, Q, arr, prr)


def bfs():
    q = deque()

    q.append((0,-1,0))

    while len(q) > 0:
        currentNode,parentNode,parentAccumulate = q.popleft()
        parentAccumulate += values[currentNode]
        finalValues[currentNode] += parentAccumulate
        childNodes = links[currentNode]
        for ch in childNodes:
            if ch == parentNode:
                continue
            q.append((ch,currentNode,finalValues[currentNode]))

bfs()
print(*finalValues)

Submission status: Accepted

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

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

# 各頂点に counter を持たせて，幅優先探索で足していく
dist = [-1 for _ in range(N)]
dist[0] = 1
que = deque()
que.append(0)
while que:
    v = que[0]
    que.popleft()
    for new_v in Graph[v]:
        if dist[new_v] != -1:
            continue
        dist[new_v] = 1
        que.append(new_v)
        counter_list[new_v] += counter_list[v]

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

Submission status: Accepted

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


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


def main():
    def dfs(now, prev=-1):
        for next in edge[now]:
            if next == prev:
                continue
            score[next] += score[now]
            dfs(next, now)

    N, Q = map(int, input().split())
    edge = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        edge[u].append(v)
        edge[v].append(u)
    p = []
    x = []
    score = [0] * (N+1)
    for _ in range(Q):
        p, x = map(int, input().split())
        score[p] += x
    dfs(1)
    print(*score[1:])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin,setrecursionlimit
from itertools import groupby
setrecursionlimit(10**6) 
n,q = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n-1)]
lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
kazu = [[]for _ in range(n+1)]
point = [0]*(n+1)
for i in li:
    kazu[i[0]].append(i[1])
    kazu[i[1]].append(i[0])
for i in lin:
    point[i[0]] += i[1]
def dfs(now,before):
    for i in (kazu[now]):
        if i == before:
            continue
        point[i] += point[now]
        dfs(i,now)
dfs(1,0)
print(*point[1:])

Submission status: Accepted

Solution code:
from sys import stdin
import sys
from itertools import groupby
sys.setrecursionlimit(10**6) 
n,q = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n-1)]
lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]

kazu = [[]for _ in range(n)]
point = [0]*n

for i in range(n-1):
    kazu[li[i][0]-1].append(li[i][1]-1)
    kazu[li[i][1]-1].append(li[i][0]-1)
for i in range(q):
    point[lin[i][0]-1] += lin[i][1]

def dfs(now,before):
    for i in (kazu[now]):
        if i == before:
            continue
        point[i] += point[now]
        dfs(i,now)
dfs(0,-1)
print(*point)