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: Time Limit Exceeded

Solution code:

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


def dfs2(conj, p=0, t=0, past_p=None, visit=set(), second_visit=set()):   # 距離と探索経路を返す。デクリメントされている場合は、decrement=True にする
    visit.add(p)
    for q in conj[p]:
        if q == past_p:
            # 逆流した際の処理
            continue
        if q in second_visit:
            # 帰り道に訪れた際の処理
            continue
        if q in visit:
            continue
        # p から q への引継ぎ処理
        X[q] += X[p]
        dfs2(conj, q, t+1, p, visit, second_visit)
    second_visit.add(p)
    return X

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

N, Q = map(int, input().split())  # N:頂点数, M:辺

conj = [set() for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    u -= 1                                    # デクリメントが不要な場合は消す
    v -= 1
    conj[u].add(v)
    conj[v].add(u)                            # 無効グラフの場合は消す

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

print(*dfs2(conj, p=0))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(300000)


to = [[] for _ in range(200005)]
ans: list


def dfs(v, p=-1):
    global ans
    for u in to[v]:
        if u == p: continue
        ans[u] += ans[v]
        dfs(u, v)
    return


def main():
    N, Q = map(int, input().split())
    for _ in range(N-1):
        a, b = map(int, input().split())
        to[a-1].append(b-1)
        to[b-1].append(a-1)
    global ans
    ans = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        ans[p-1] += x
    dfs(0)
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 26

import sys

sys.setrecursionlimit(10**9)

n, q = map(int, input().split())
ans_l = [0] * n
graph = [[] for x in range(n)]

def dfs(v, p=-1):
    if p >= 0:
        ans_l[v] += ans_l[p]
    for i in range(len(graph[v])):
        _v = graph[v][i]
        if _v != p:
            dfs(_v, v)
        
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    
for j in range(q):
    p, x = map(int, input().split())
    ans_l[p-1] += x
    
dfs(0)

print(*ans_l)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
lis = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)
c_plus = [0 for _ in range(n)]
for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    c_plus[p] += x
ans = [-1 for _ in range(n)]
def dfs(inp):
    now = inp[0]
    count = inp[1]
    count += c_plus[now]
    ans[now] = count
    for next in lis[now]:
        if ans[next] == -1:
            dfs([next, count])
dfs([0,0])
for i in range(n):
    ans[i] = str(ans[i])
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import queue
n,q = map(int,input().split())
branch = queue.Queue()
for _ in range(n-1):
    ab = list(map(int,input().split()))
    branch.put(ab)
count = [0]*n
for _ in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
    
tree = [set() for i in range(n)]
check = [0]*n
check[0] = 1

while not branch.empty():
    a,b = branch.get()
    if check[a-1] == 0 & check[b-1] == 0:
        branch.put([a,b])
        continue
    elif check[a-1] == 1:
        tree[a-1].add(b-1)
        check[b-1] = 1
    else:
        tree[b-1].add(a-1)
        check[a-1] = 1   
    
q = queue.Queue()
q.put(0)
while not q.empty():
    num = q.get()
    for k in tree[num]:
        count[k] += count[num]
        q.put(k)
        
print(*count)

Submission status: Time Limit Exceeded

Solution code:
import queue
n,q = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in range(n-1)])
count = [0]*n
for _ in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
    
tree = [set() for i in range(n)]
branch = queue.Queue()
check = [0]*n
check[0] = 1
for l in ab:
    branch.put(l)
while not branch.empty():
    a,b = branch.get()
    if check[a-1] == 0 & check[b-1] == 0:
        branch.put([a,b])
        continue
    elif check[a-1] == 1:
        tree[a-1].add(b-1)
        check[b-1] = 1
    else:
        tree[b-1].add(a-1)
        check[a-1] = 1   
    
q = queue.Queue()
q.put(0)
while not q.empty():
    num = q.get()
    for k in tree[num]:
        count[k] += count[num]
        q.put(k)
        
print(*count)

Submission status: Time Limit Exceeded

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

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

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

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

dfs(0, 0)
print(" ".join(map(str, count)))

Submission status: Time Limit Exceeded

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

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

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

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

dfs(0, 0)
print(" ".join(map(str, count)))

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

int1 = lambda x: int(x) - 1

N, Q = map(int, input().split())
G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from([tuple(map(int1, input().split())) for _ in range(N - 1)])

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

for parent, child in nx.dfs_edges(G, 0):
    lst[child] += lst[parent]

print(*lst)

Submission status: Time Limit Exceeded

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

def main():
    n, q = map(int, input().split())
    # バラバラに持ちたいなら
    # for i in range(n-1):
    #     a, b = map(int, input().split())
    # for i in range(q):
    #     q, x = 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)]
    # print(ab)
    # print(qx)
    # indexがノード
    adj = [[] for _ in range(n+1)]
    for a, b in ab:
            adj[a].append(b)
            adj[b].append(a)
    # print(adj)
    # indexが直接初めにノードに加えられる得点
    v = [0] * (n+1)
    for p,x in px:
        v[p] += x

    def dfs(cur, parent):
        for chl in adj[cur]:
            if chl == parent: 
                continue
            v[chl] += v[cur] 
            dfs(chl, cur)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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 = [0]
    looked[0] = 0
    while queue:
        now = queue.pop(0)
        for i in node[now]:
            if looked[i]:
                queue.append(i)
                counter[i] += counter[now]
                looked[i] = 0
    print(*counter)
main()

Submission status: Time Limit Exceeded

Solution code:
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 = [0]
    looked[0] = 0
    while(queue):
        now = queue.pop(0)
        for i in node[now]:
            if looked[i]:
                queue.append(i)
                counter[i] += counter[now]
                looked[i] = 0
    print(*counter)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,q = map(int,input().split())
    node = [[]for _ in range(n)]
    looked = [1 for _ in range(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 for _ in range(n)]
    for i in range(q):
        p,x = map(int,input().split())
        counter[p-1] += x
    queue = [0]
    looked[0] = 0
    while(queue):
        now = queue.pop(0)
        for i in node[now]:
            if looked[i]:
                queue.append(i)
                counter[i] += counter[now]
                looked[i] = 0
    print(*counter)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,q = map(int,input().split())
    node = [[]for _ in range(n)]
    looked = [1 for _ in range(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 for _ in range(n)]
    for i in range(q):
        p,x = map(int,input().split())
        counter[p-1] += x
    queue = [0]
    looked[0] = 0
    while(queue):
        now = queue.pop(0)
        for i in node[now]:
            if looked[i]:
                queue.append(i)
                counter[i] += counter[now]
                looked[i] = 0
    print(*counter)
main()

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
node = [[]for _ in range(n)]
looked = [1 for _ in range(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 for _ in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    counter[p-1] += x
queue = [0]
looked[0] = 0
while(len(queue)):
    now = queue.pop(0)
    for i in node[now]:
        if looked[i]:
            queue.append(i)
            counter[i] += counter[now]
            looked[i] = 0
print(" ".join(map(str,counter)))

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
node = [[]for _ in range(n)]
looked = [1 for _ in range(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 for _ in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    counter[p-1] += x
queue = [0]
looked[0] = 0
while(len(queue)):
    now = queue.pop(0)
    for i in node[now]:
        if looked[i]:
            queue.append(i)
            counter[i] += counter[now]
            looked[i] = 0
print(" ".join(list(map(str,counter))))

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
node = [[]for _ in range(n)]
looked = [0 for _ in range(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 for _ in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    counter[p-1] += x
queue = [0]
looked[0] = 1
while(len(queue)):
    now = queue.pop(0)
    for i in node[now]:
        if looked[i] == 0:
            queue.append(i)
            counter[i] += counter[now]
            looked[i] = 1
print(" ".join(list(map(str,counter))))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
N, Q = map(int, input().split(' '))

tree = [[] for i 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)
memo = [0] * (N)
for i in range(Q):
    p, x = map(int, input().split(' '))
    p -= 1
    memo[p] += x


def dfs(v, par):
    for i in tree[v]:
        if i == par:
            continue
        memo[i] += memo[v]
        dfs(i, v)


dfs(0, -1)

print(*memo)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
N, Q = map(int, input().split(' '))

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


def dfs(v, par):
    for i in tree[v]:
        if i == par:
            continue
        memo[i] += memo[v]
        dfs(i, v)
dfs(1,-1)

print(*memo[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, Q = map(int, input().split(' '))
tree = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split(' '))
    tree[a].append([a, b])
    tree[b].append([b, a])
val = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split(' '))
    val[p] += x
ans = [-1] * (N + 1)
ans[1] = val[1]
bfs = deque(tree[1])
while bfs:
    p, n = bfs.popleft()
    if ans[n] == -1:
        ans[n] = val[n] + ans[p]
        for i in tree[n]:
            bfs.append(i)
for i in ans[1:-1]:
    print(i,'',end="")
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, Q = map(int, input().split(' '))
tree = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split(' '))
    tree[a].append([a, b])
    tree[b].append([b, a])
val = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split(' '))
    val[p] += x
ans = [-1] * (N + 1)
ans[1] = val[1]
bfs = deque(tree[1])
while bfs:
    p,n = bfs.popleft()
    if ans[n] == -1:
        ans[n] = val[n]+ans[p]
        for i in tree[n]:
            bfs.append(i)
print(' '.join(list(map(str,ans[1:]))))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

# DFS
def dfs(i, p):
    for j in graph[i]:
        if j != p:
            scores[j] += scores[i]
            dfs(j, i)

dfs(0, -1)
print(" ".join(map(str, scores)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
n,q=map(int,input().split())
path=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  #print(a,b)
  path[a-1].append(b-1)
  path[b-1].append(a-1)
score=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  score[p-1]+=x

look=[0]*n
look[0]=1

def dfs(pos,pre_score=0):
  score[pos]+=pre_score
  #print(pos,add_[pos],pre_score,path[pos])
  path[pos]=[x for x in path[pos] if not look[x]]
  for p in path[pos]:
    if not look[p]:
      look[p]=1
      dfs(p,score[pos])

dfs(0)
print(*score)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
n,q=map(int,input().split())
path=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  #print(a,b)
  path[a-1].append(b-1)
  path[b-1].append(a-1)
score=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  score[p-1]+=x

look=[0]*n
look[0]=1

def dfs(pos,pre_score=0):
  score[pos]+=pre_score
  #print(pos,pre_score,path[pos])
  for p in path[pos]:
    if not look[p]:
      look[p]=1
      dfs(p,score[pos])

dfs(0)
print(*score)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
n,q=map(int,input().split())
path=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  #print(a,b)
  path[a-1].append(b-1)
  path[b-1].append(a-1)
add_=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  add_[p-1]+=x

score=[0]*n
look=[0]*n
look[0]=1

def dfs(pos,pre_score=0):
  score[pos]=add_[pos]+pre_score
  #print(pos,add_[pos],pre_score,path[pos])
  for p in path[pos]:
    if not look[p]:
      look[p]=1
      dfs(p,score[pos])

dfs(0)
print(*score)

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import os

# 検索用タグ、累積和、木、クエリ処理、遅延評価

sys.setrecursionlimit(1000000)

relations = []
# def dfs(me, relations, counters, arrived, ans):
def dfs(parent, me, counters):

    if not parent == me == 1:
        counters[me] += counters[parent]

    # 再帰処理のためのループ
    for target in relations[me]:

        if parent == target:
            continue

        # 次の枝を処理
        dfs(me, target, counters)


# 実装を行う関数
def resolve():
    global relations

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

    # 木のつながりを整理する
    relations = [[] for i in range(n + 1)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        relations[a].append(b)
        relations[b].append(a)

    # どの木がきたら、いくら値を加算するか、を保持する(同じ木を何度か加算することもある)
    # 最終的に、これと「木のつながり」を組み合わせて各枝の累積和を求める。
    counters = [0 for i in range(n + 1)]
    for i in range(q):
        p, x = map(int, input().split())
        counters[p] += x

    # 通過済みかを保持するリスト
    arrived = [False for i in range(n + 1)]

    # root木の値を初期設定
    arrived[1] = True

    # 辺のつながりを再帰的に追っていく。(ちなみに、木構造なのでループは無し)
    #dfs(1, relations, counters, arrived, ans)
    dfs(1, 1 , counters)

    # ans_list = [str(i) for i in ans[1:]]
    # print(" ".join(ans_list))
    print(*counters[1:])


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 3
1 2
2 3
2 4
2 10
1 100
3 1"""
        output = """100 110 111 110"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10"""
        output = """20 20 20 20 20 20"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import os

# 検索用タグ、累積和、木、クエリ処理、遅延評価

sys.setrecursionlimit(1000000)


def dfs(me, relations, counters, arrived, ans):
    # 再帰処理
    for target in relations[me]:
        # 到達済みなら何もしない
        if arrived[target]:
            continue

        arrived[target] = True
        # 枝に設定すべき値を設定(親の値 + 加算する値)※ここがポイントかも。順次加算することで、最終的には毎回足した時と同じ値になる。
        ans[target] = ans[me] + counters[target]

        # 次の枝を処理
        dfs(target, relations, counters, arrived, ans)


# 実装を行う関数
def resolve():
    n, q = map(int, input().split())

    # 木のつながりを整理する
    relations = [[] for i in range(n + 1)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        relations[a].append(b)
        relations[b].append(a)

    # どの木がきたら、いくら値を加算するか、を保持する(同じ木を何度か加算することもある)
    counters = [0 for i in range(n + 1)]
    for i in range(q):
        p, x = map(int, input().split())
        counters[p] += x

    # 通過済みかを保持するリスト
    arrived = [False for i in range(n + 1)]
    # 答えを保持するリスト
    ans = [0 for i in range(n + 1)]

    # root木の値を初期設定
    arrived[1] = True
    ans[1] = counters[1]

    # 辺のつながりを再帰的に追っていく。(ちなみに、木構造なのでループは無し)
    dfs(1, relations, counters, arrived, ans)

    # ans_list = [str(i) for i in ans[1:]]
    # print(" ".join(ans_list))
    print(*ans[1:])


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 3
1 2
2 3
2 4
2 10
1 100
3 1"""
        output = """100 110 111 110"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10"""
        output = """20 20 20 20 20 20"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import os

# 検索用タグ、累積和、木、クエリ処理、遅延評価

sys.setrecursionlimit(1000000)


def dfs(me, relations, counters, arrived, ans):
    # 再帰処理
    for target in relations[me]:
        # 到達済みなら何もしない
        if arrived[target]:
            continue

        arrived[target] = True
        # 枝に設定すべき値を設定(親の値 + 加算する値)※ここがポイントかも。順次加算することで、最終的には毎回足した時と同じ値になる。
        ans[target] = ans[me] + counters[target]

        # 次の枝を処理
        dfs(target, relations, counters, arrived, ans)


# 実装を行う関数
def resolve():
    n, q = map(int, input().split())

    # 木のつながりを整理する
    relations = [[] for i in range(n + 1)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        relations[a].append(b)
        relations[b].append(a)

    # どの木がきたら、いくら値を加算するか、を保持する(同じ木を何度か加算することもある)
    counters = [0 for i in range(n + 1)]
    for i in range(q):
        p, x = map(int, input().split())
        counters[p] += x

    # 通過済みかを保持するリスト
    arrived = [False for i in range(n + 1)]
    # 答えを保持するリスト
    ans = [0 for i in range(n + 1)]

    # root木の値を初期設定
    arrived[1] = True
    ans[1] = counters[1]

    # 辺のつながりを再帰的に追っていく。(ちなみに、木構造なのでループは無し)
    dfs(1, relations, counters, arrived, ans)

    ans_list = [str(i) for i in ans[1:]]
    print(" ".join(ans_list))


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 3
1 2
2 3
2 4
2 10
1 100
3 1"""
        output = """100 110 111 110"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10"""
        output = """20 20 20 20 20 20"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import os

# 検索用タグ、累積和、木、クエリ処理、遅延評価

sys.setrecursionlimit(1000000)


def dfs(parent, me, relations, counters, ans):
    # 再帰処理
    for target in relations[me]:
        # 呼び出し元は除外(無限ループ防止)
        if target == parent:
            continue

        # 枝に設定すべき値を設定(親の値 + 加算する値)※ここがポイントかも。順次加算することで、最終的には毎回足した時と同じ値になる。
        ans[target] = ans[me] + counters[target]

        # 次の枝を処理
        dfs(me, target, relations, counters, ans)


# 実装を行う関数
def resolve():
    n, q = map(int, input().split())
    # ab_list = [list(map(int, input().split())) for i in range(n - 1)]
    # px_list = [list(map(int, input().split())) for i in range(q)]

    # 木のつながりを整理する
    relations = [[] for i in range(n + 1)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        relations[a].append(b)
        relations[b].append(a)

    # どの木がきたら、いくら値を加算するか、を保持する(同じ木を何度か加算することもある)
    counters = [0 for i in range(n + 1)]
    for i in range(q):
        p, x = map(int, input().split())
        counters[p] += x

    ans = [0 for i in range(n + 1)]
    # root木の値を初期設定
    ans[1] = counters[1]

    # 辺のつながりを再帰的に追っていく。(ちなみに、木構造なのでループは無し)
    dfs(1, 1, relations, counters, ans)

    ans_list = [str(i) for i in ans[1:]]
    print(" ".join(ans_list))


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 3
1 2
2 3
2 4
2 10
1 100
3 1"""
        output = """100 110 111 110"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10"""
        output = """20 20 20 20 20 20"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import os

# 検索用タグ、累積和、木、クエリ処理、遅延評価

sys.setrecursionlimit(1000000)


def dfs(parent, me, relations, counters, ans):
    # 再帰処理
    for target in relations[me]:
        # 呼び出し元は除外(無限ループ防止)
        if target == parent:
            continue

        # 枝に設定すべき値を設定(親の値 + 加算する値)※ここがポイントかも。順次加算することで、最終的には毎回足した時と同じ値になる。
        ans[target] = ans[me] + counters[target]

        # 次の枝を処理
        dfs(me, target, relations, counters, ans)


# 実装を行う関数
def resolve():
    n, q = map(int, input().split())
    ab_list = [list(map(int, input().split())) for i in range(n - 1)]
    px_list = [list(map(int, input().split())) for i in range(q)]

    # 木のつながりを整理する
    relations = [[] for i in range(n + 1)]
    for ab in ab_list:
        relations[ab[0]].append(ab[1])
        relations[ab[1]].append(ab[0])

    # どの木がきたら、いくら値を加算するか保持する(同じ木を何度か加算することもある)
    counters = [0 for i in range(n + 1)]
    for px in px_list:
        counters[px[0]] += px[1]

    ans = [0 for i in range(n + 1)]
    # root木の値を初期設定
    ans[1] = counters[1]

    # 辺のつながりを再帰的に追っていく。(ちなみに、木構造なのでループは無し)
    dfs(1, 1, relations, counters, ans)

    ans_list = [str(i) for i in ans[1:]]
    print(" ".join(ans_list))


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 3
1 2
2 3
2 4
2 10
1 100
3 1"""
        output = """100 110 111 110"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10"""
        output = """20 20 20 20 20 20"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Time Limit Exceeded

Solution code:
from queue import deque

N, Q = map(int, input().split())
 
AB = []
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    AB.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
AB = sorted(AB, key=lambda x: (x[1], x[0]))
 
root = 0
q = deque([root])
parent = [-1] * N
while q:
    x = q.popleft()
    p = parent[x]
    for y in graph[x]:
        if y == p:
            continue
        parent[y] = x
        q.append(y)

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

for a, b in AB:
    if a != parent[b]:
        tmp = a
        a = b
        b = tmp
    C[b] += C[a]

print(*C)