Day 005-Q4 | 木DP

問題

N頂点の根付き木（根=頂点1）。各頂点 i に価値 v[i]。隣接する2頂点を同時に選ばない制約のもと、選んだ頂点の価値合計の最大値を求めよ（最大独立集合問題 on tree）。

入力形式

N
v1 v2 ... vN
u1 v1
...（N-1行の辺）

制約

$1 \le N \le 3 \times 10^5$

$0 \le v_i \le 10^9$

入出力例

入力例 1

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

出力例 1

頂点3(4)+頂点4(1)+頂点5(5)+頂点6(6) = 16

ヒント (段階的開示)

ヒント1: 方向性

木の各頂点で「選ぶ/選ばない」の2状態DP。

ヒント2: アプローチ

dp[v][0]=v選ばない部分木最大、dp[v][1]=v選ぶ部分木最大。子に応じて遷移。

ヒント3: 誘導

def dfs(v, parent):
    dp0, dp1 = 0, val[v]
    for u in graph[v]:
        if u == parent: continue
        c0, c1 = dfs(u, v)
        dp0 += max(c0, c1)
        dp1 += c0
    return dp0, dp1

模範解答 (Python)

import sys
sys.setrecursionlimit(400000)
input = sys.stdin.readline

def main():
    N = int(input())
    val = [0] + list(map(int, input().split()))
    graph = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    def solve():
        dp = [[0, 0] for _ in range(N + 1)]
        parent = [-1] * (N + 1)
        order = []
        stack = [1]
        visited = [False] * (N + 1)
        visited[1] = True
        while stack:
            v = stack.pop()
            order.append(v)
            for u in graph[v]:
                if not visited[u]:
                    visited[u] = True
                    parent[u] = v
                    stack.append(u)

        for v in reversed(order):
            dp[v][0] = 0
            dp[v][1] = val[v]
            for u in graph[v]:
                if u == parent[v]:
                    continue
                dp[v][0] += max(dp[u][0], dp[u][1])
                dp[v][1] += dp[u][0]

        return max(dp[1][0], dp[1][1])

    print(solve())

main()

Step-by-Step 解説

1DP定義
dp[v][0]: v を選ばないときの v の部分木最大価値。dp[v][1]: v を選ぶときの部分木最大価値。

2遷移式
選ぶなら子は選べない → dp[c][0] のみ加算。選ばないなら子は max(dp[c][0], dp[c][1])。

3反復DFSで処理順序
再帰深度制限を避け、スタックでDFSし訪問順を記録。逆順処理で「葉→根」の順になる。

計算量

$O(N)$ — 各頂点を1回処理

よくあるミス

ミス	原因	正しい書き方
再帰スタックオーバーフロー	N=3×10^5	反復DFS or setrecursionlimit
親方向への辺を処理	無向で親へ戻る	`if u == parent: continue`
dp初期化漏れ	val[v] 含め忘れ	dp[v][1] = val[v] で初期化

Day 005-Q4 — 木DP

問題