AtCoder Beginner Contest 138 D – Ki をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Beginner Contest 138 D – Ki

部分木に含まれる全ての頂点に~と聞くと難しく感じるが、実はそれほど難しくない。根から普通に探索を行えば、自然に操作できる。

# AtCoder Beginner Contest 138 D - Ki
# https://atcoder.jp/contests/abc138/tasks/abc138_d
# tag: グラフ 木 部分木 BFS DFS

# BFS もしくは DFS にて探索を行えば、根 → 葉 と進むことになるので、
# 細かいことは気にせず、順次子へと加算値を伝播させて行けばいい。

def main():
    N, Q = map(int, input().split())
    path_dat = [list(map(int, input().split())) for _ in range(N-1)]
    add_dat = [list(map(int, input().split())) for _ in range(Q)]

    # 0-indexedへ
    paths = [[] for _ in range(N)]
    for a, b in path_dat:
        a -= 1
        b -= 1
        paths[a].append(b)
        paths[b].append(a)
    
    # 加算値 兼 回答
    counter = [0] * N
    for n, x in add_dat:
        counter[n-1] += x

    # BFS による探索    
    queue = [0]
    visited = [False] * N
    while queue:
        now = queue.pop()
        visited[now] = True

        for nxt in paths[now]:
            if visited[nxt]:
                continue
            # 親 → 子 と加算値を伝播させる
            counter[nxt] += counter[now]
            queue.append(nxt)

    print(*counter)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です