Problem:


Score : 400 points

Problem Statement

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

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

Now, the following Q operations will be performed:

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

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

Constraints

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

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

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

100 110 111 110

The tree in this input is as follows:

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

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

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

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

Sample Input 2

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

Sample Output 2

20 20 20 20 20 20



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


Sample output:
100 110 111 110

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
root=[[] for _ in range(n)]
f=lambda x:int(x)-1
 
for i in range(n-1):
  a,b=map(f,input().split())
  root[a].append(b)
  root[b].append(a)
 
score=[0]*n
for j in range(q):
  p,x=map(int,input().split())
  score[p-1]+=x
 
visit = [False]*n
def dfs(now):
  visit[now] = True
  for go in root[now]:
    if visit[go]:
      continue
    score[go] += score[now]
    dfs(go)

dfs(0)
print(*score)

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

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

import queue
q = queue.Queue()
q.put((-1, 0))

while not q.empty():
    p, v = q.get()
    for c in G[v]:
        if c == p: continue
        memo[c] += memo[v]
        q.put((v, c))

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

Submission status: Accepted

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

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

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

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

stack = [(None,0)]
while stack:
    p,v = stack.pop()
    for u in adj[v]:
        if u != p:
            memo[u] += memo[v]
            stack.append((v,u))

print(*memo)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
input = sys.stdin.readline
import marshal


class Graph:
    def __init__(self, n, dictated=False, decrement=True, destroy=False, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.destroy = destroy
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def dfs2(self, info, start, goal=-1, time=0, save=False):
        """
        :param info: 各頂点の付加情報
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: ゴール地点までの距離。存在しなければ -1
        """

        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        if self.destroy:
            edge2 = self.edge
        else:
            edge2 = marshal.loads(marshal.dumps(self.edge))

        p, t = start, time
        self.parent[p] = -2
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                if q == goal:
                    """ ゴール時の処理"""
                    # return t + 1
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                info[q] += info[p]
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """

                """"""""""""""""""""
        return info


######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, Q: クエリの数
M = N-1

graph = Graph(N, dictated=False, destroy=True)

for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x,y)

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

print(*graph.dfs2(info, start=1))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
input = sys.stdin.readline
import marshal


class Graph:
    def __init__(self, n, dictated=False, decrement=True, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def dfs2(self, info, start, goal=-1, time=0, save=False):
        """
        :param info: 各頂点の付加情報
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: ゴール地点までの距離。存在しなければ -1
        """

        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n

        edge2 = marshal.loads(marshal.dumps(self.edge))

        p, t = start, time
        self.parent[p] = -2
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                if q == goal:
                    """ ゴール時の処理"""
                    # return t + 1
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                info[q] += info[p]
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """

                """"""""""""""""""""
        return info


######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, Q: クエリの数
M = N-1

graph = Graph(N, dictated=False)

for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x,y)

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

print(*graph.dfs2(info, start=1))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
input = sys.stdin.readline
from copy import deepcopy


class Graph:
    def __init__(self, n, dictated=False, decrement=True, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def dfs2(self, info, start, goal=-1, time=0, save=False):
        """
        :param info: 各頂点の付加情報
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: ゴール地点までの距離。存在しなければ -1
        """

        if self.decrement:
            start -= 1
            goal -= 1
        # if not save:
        #     self.parent = [-1] * self.n
        #
        edge2 = deepcopy(self.edge)


        p, t = start, time
        self.parent[p] = -2
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                if q == goal:
                    """ ゴール時の処理"""
                    # return t + 1
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                info[q] += info[p]
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """

                """"""""""""""""""""
        return info


######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, Q: クエリの数
M = N-1

graph = Graph(N, dictated=False)

for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x,y)

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

print(*graph.dfs2(info, start=1))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
input = sys.stdin.readline
from copy import deepcopy


class Graph:
    def __init__(self, n, dictated=False, decrement=True, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def dfs2(self, info, start, goal=-1, time=0, save=False):
        """
        :param info: 各頂点の付加情報
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: ゴール地点までの距離。存在しなければ -1
        """

        if self.decrement:
            start -= 1
            goal -= 1
        # if not save:
        #     self.parent = [-1] * self.n
        # 
        # edge2 = deepcopy(self.edge)
        
        edge2 = self.edge

        p, t = start, time
        self.parent[p] = -2
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                if q == goal:
                    """ ゴール時の処理"""
                    # return t + 1
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                info[q] += info[p]
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """

                """"""""""""""""""""
        return info


######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, Q: クエリの数
M = N-1

graph = Graph(N, dictated=False)

for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x,y)

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

print(*graph.dfs2(info, start=1))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
input = sys.stdin.readline
from copy import deepcopy


class Graph:
    def __init__(self, n, dictated=False, decrement=True, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def dfs2(self, info, start, goal=-1, time=0, save=False):
        """
        :param info: 各頂点の付加情報
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: ゴール地点までの距離。存在しなければ -1
        """

        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n

        edge2 = deepcopy(self.edge)

        p, t = start, time
        self.parent[p] = -2
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                if q == goal:
                    """ ゴール時の処理"""
                    # return t + 1
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                info[q] += info[p]
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """

                """"""""""""""""""""
        return info


######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, Q: クエリの数
M = N-1

graph = Graph(N, dictated=False)

for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x,y)

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

print(*graph.dfs2(info, start=1))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline


class Graph:
    def __init__(self, n, dictated=False, edge=[]):
        self.n = n
        self.dictated = dictated
        self.conj = [set() for _ in range(self.n)]
        self.visit = set()
        self.second_visit = set()
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self,x,y):
        self.conj[x].add(y)
        if self.dictated == False:
            self.conj[y].add(x)

    def dfs(self, info, start=0, goal=None, use_visit=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param use_visit: 前回の探索結果を保持するかどうか
        :return: ゴール地点までの距離。存在しなければ -1
        """
        if use_visit == False:
            self.visit = set()
            self.second_visit = set()
        self.visit.add(start)

        past_p = None
        next_set = [(start, past_p, 0)]
        next_full_set = [next_set]
        while sum(map(lambda x: x!=[], next_full_set)) != 0:
            next_set = next_full_set.pop()
            p, past_p, t = next_set.pop()
            for q in self.conj[p]:
                if p == past_p:
                    # 逆流した際の処理
                    continue
                if q in self.visit:
                    continue
                if q == goal:
                    # ゴール時の処理
                    # return t+1
                    continue
                # p から q への引継ぎ処理
                info[q] += info[p]
                self.visit.add(q)
                next_set.append((q, p, t + 1))
            if not next_set:
                self.second_visit.add(p)
                # 帰り際の処置（壊した道を元に戻す等)
                # visit.discard(p)
            else:
                next_full_set.append(next_set)
        return info


######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, Q: クエリの数
M = N-1

graph = Graph(N, dictated=False)

for _ in range(M):
    x, y = map(int, input().split())
    x -= 1                                    # デクリメントが不要な場合は消す
    y -= 1
    graph.add_edge(x,y)

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

print(*graph.dfs(info, start=0))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline


class Graph:
    def __init__(self, n, dictated=False, edge=[]):
        self.n = n
        self.dictated = dictated
        self.conj = [set() for _ in range(self.n)]
        self.visit = set()
        self.parent = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self,x,y):
        self.conj[x].add(y)
        if self.dictated == False:
            self.conj[y].add(x)

    def dfs(self, info, start=0, goal=None, use_visit=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param use_visit: 前回の探索結果を保持するかどうか
        :return: ゴール地点までの距離。存在しなければ -1
        """
        if use_visit == False:
            self.visit = set()
            self.parent = [-1]*self.n
        self.visit.add(start)
        next_set = [(start, 0)]

        while next_set:
            p, t = next_set.pop()
            for q in self.conj[p]:
                if self.parent[q] == p:
                    # 逆流した際の処理
                    continue
                if q in self.visit:
                    continue
                if q == goal:
                    # ゴール時の処理
                    # return t+1
                    continue
                # p から q への引継ぎ処理
                self.parent[q] = p
                info[q] += info[p]

                self.visit.add(q)
                next_set.append((q, t + 1))
        return info


######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, Q: クエリの数
M = N-1

graph = Graph(N, dictated=False)

for _ in range(M):
    x, y = map(int, input().split())
    x -= 1                                    # デクリメントが不要な場合は消す
    y -= 1
    graph.add_edge(x,y)

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

print(*graph.dfs(info, start=0))

Submission status: Accepted

Solution code:

n, q = map(int, input().split())
ki = [[] for i in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  a-=1
  b-=1
  ki[a].append(b)
  ki[b].append(a)
  
ans=[0]*n
vis=[False]*n

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

import queue
q = queue.Queue()
q.put(0)

while not q.empty():
  temp = q.get()
  vis[temp]=True
  for next in ki[temp]:
    if not vis[next]:
      ans[next]+=ans[temp]
      q.put(next)
ans = list(map(str, ans))
print(" ".join(ans))

Submission status: Accepted

Solution code:
from collections import deque

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

ans = px
queue = deque([(0, 0)])
while len(queue) > 0:
    prev, a = queue.pop()
    for c in ab[a]:
        if c != prev:
            ans[c] += ans[a]
            queue.append((a, c))

print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
sys.setrecursionlimit(10**9)


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

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


f = [False] * N
q = deque([1])
while(q):
    n = q.popleft()
    f[n-1] = True
    for i in t[n-1]:
        if f[i-1]:
            continue
        q.append(i)
        count[i-1]+=count[n-1]
        f[i-1] = True
#for i in range(1, N):
#    count[i] += count[parent[i + 1] - 1]
#print(parent)
print(*count)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
 
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 defaultdict
import sys
sys.setrecursionlimit(10**7)


def dfs(prev, u):
    if visited[u]:
        return
    else:
        cnt[u] += cnt[prev]
        visited[u] = True
        for nu in graph[u]:
            if visited[nu]:
                continue
            else:
                dfs(u, nu)


n, q = map(int, input().split())
graph = defaultdict(list)

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

cnt = [0] * (n + 1)

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

visited = [False] * (n + 1)

dfs(0, 1)

print(*cnt[1:])

Submission status: Accepted

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


def dfs(prev, u):
    if visited[u]:
        return
    else:
        cnt[u] += cnt[prev]
        visited[u] = True
        for nu in graph[u]:
            if visited[nu]:
                continue
            else:
                dfs(u, nu)


n, q = map(int, input().split())
graph = defaultdict(list)

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

cnt = [0] * (n + 1)

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

visited = [True] + [False] * n

dfs(0, 1)

print(*cnt[1:])

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:
import sys
sys.setrecursionlimit(500000)

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

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

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

ans = [0] * N
visited = set()
def dfs(n: int, score: int):
    score += scores[n]
    ans[n] = score
    visited.add(n)
    for v in tree[n]:
        if v not in visited:
            dfs(v, score)

dfs(0, 0)

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

visited = [False] * (N + 1)
visited[1] = True
stack = deque()
stack.append(1)
while stack:
    u = stack.popleft()
    for v in graph[u]:
        if not visited[v]:
            visited[v] = True
            tree[v] += tree[u]
            stack.append(v)
            
print(*tree[1:])

Submission status: Accepted

Solution code:
from collections import deque
def bfs(start, g, vals, n):
    visited = [-1]*n
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        added_val = vals[curr_node]
        for next_node in g[curr_node]:
            if visited[next_node] >= 0: continue
            visited[next_node] = visited[curr_node] + 1
            vals[next_node] += added_val
            q.append(next_node)


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)

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

bfs(0, g, vals, n)
print(*vals)

Submission status: Accepted

Solution code:
from collections import deque

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

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

score = [0]*n

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

visited = [0]*n
visited[0] = 1

s = deque([0])
while s:
    now = s.pop()
    for v in edge[now]:
        if visited[v]:
            continue
        score[v] += score[now]
        visited[v] = 1
        s.append(v)

print(*score)

Submission status: Accepted

Solution code:
def main():
    n,q=map(int,input().split())
    ab=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    visit=[False]*n
    cnt=[0]*n
    for i in range(q):
        p,x=map(int,input().split())
        cnt[p-1]+=x
    q=[(0,0)]
    while q:
        v,a=q.pop()
        visit[v]=True
        a+=cnt[v]
        cnt[v]=a
        for i in ab[v]:
            if visit[i]:
                continue
            else:
                q.append((i,a))
    print(*cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
nextlist=[[] for _ in range(n)]
pointlist=[0]*n
for i in range(n-1):
    tmpa,tmpb=map(int,input().split())
    nextlist[tmpa-1].append(tmpb)
    nextlist[tmpb-1].append(tmpa)

for i in range(q):
    tmpp,tmpx=map(int,input().split())
    pointlist[tmpp-1] += tmpx

#for i,next in enumerate(nextlist):
#    next.append(pointlist[i])
outlist=[0]*n
done=[False]*n
nextp=[[],[]]

outlist[0]=pointlist[0]
done[0]=True
for j in nextlist[0]:
    nextp[0].append([j,pointlist[0]])
    done[j-1]=True

i=0

while True:
    x = -i+1
    if nextp[i] == []:
        break
    else:
        for ne in nextp[i]:
            n=ne[0]
            p=ne[1]
            outlist[n-1] = pointlist[n-1] + p

            for j in nextlist[n-1]:
                if not done[j-1]:
                    nextp[x].append([j,outlist[n-1]])
                    done[j-1]=True
        nextp[i]=[]
        i=x

for out in outlist:
    print(out,end=' ')

Submission status: Accepted

Solution code:
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
import collections
q=collections.deque()
q.append(0)
check=[0]*n
while q:
  v=q.popleft()
  check[v]=1
  for u in g[v]:
    if check[u]==1:
      continue
    cnt[u]+=cnt[v]
    q.append(u)
print(*cnt)