ABC138 D - Ki

DFS の基本問題

理解してACするまで3時間半ほどかかりました。

setrecursionlimit() を知らなかったので、それを入れるまでずーっとREしてました

流れ

f:id:matrochca:20201205175219j:plain

解答

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
N, Q = map(int, input().split())

# グラフ
G = [[] for i in range(N)]
for i in range(N-1):
    # ノードのインデックス
    a, b = MI()

    # 無向グラフ
    G[a-1].append(b-1) # zero-based を忘れずに
    G[b-1].append(a-1)

# print(G)

# ans の準備
ans = [0] * N
# 各ノードに x を追加
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

# DFS
def dfs(v, p): # p : parent of v
    # c : children of v
    for c in G[v]:
        # parent のインデックスの場合は足さずにスキップ
        if c == p: continue
        # children に v の値を足す
        ans[c] += ans[v]
        # 再帰的に探索
        dfs(c, v)

dfs(0, -1)

# 改行せずにリストの要素を出力
print(*ans)

参考記事

AtCoder Beginner Contest138のD問題を通してDFS(深さ優先探索)を理解した - Qiita