Day 066-Q4 — 動的木上の最大独立集合（Dynamic MIS on Forest）

2026-06-19 赤色 Master / Phase 8+ ★★★★★★★★★ 木DP / 辺の動的追加削除 / Link-Cut Tree + MIS

問題

$N$ 頂点の森（複数の木の集合）が与えられる。各頂点 $i$ には重み $w_i$ がある。$Q$ 個のクエリを順番に処理せよ：

  • add u v : 頂点 $u$ と $v$ を辺で結ぶ（同じ木内でない保証あり）
  • del u v : 辺 $(u, v)$ を削除する
  • query r : 頂点 $r$ を根とする木の最大重み独立集合の値を出力せよ

制約

パラメータ範囲
$N$$1 \le N \le 2 \times 10^4$
$Q$$1 \le Q \le 2 \times 10^4$
$w_i$$1 \le w_i \le 10^9$
query での r の木森の 1 成分であることが保証

入出力例

入力例 1

5 4
3 5 2 4 1
add 1 2
add 2 3
add 3 4
query 1

出力例 1

9

パス 1-2-3-4 の MIS: {2,4} = 5+4 = 9。頂点5は孤立しているため考慮外。

概念図: 木 DP の dp[v][0/1]

最大独立集合 木DP: dp[v] = (選ばない, 選ぶ) 1 w=3 2 w=5 ★選択 3 w=2 4 w=4 ★選択 dp[v] = (not_take, take) dp[4] = (0, 4) dp[3] = (max(0,4), 2+0) = (4, 2) dp[2] = (0, 5) dp[1]: not_take = max(5,0)+max(4,2) = 5+4 = 9 take = 3 + dp[2][0] + dp[3][0] = 3 + 0 + 4 = 7 DP 遷移式 not_take += max(dp[u]) take += dp[u][0] 答え = max(dp[root])

ヒント（段階的開示）

ヒント1: 方向性
木 DP で dp[v][0/1] = v を根とする部分木で v を含まない/含む場合の最大重み独立集合。辺が動的に追加・削除されるため、毎回 O(N) の DFS を実行する（N,Q が小さいので許容）。
ヒント2: アプローチ
  1. Union-Find で成分を管理（add/del で更新）
  2. query 時に r から DFS/BFS で木全体を探索
  3. ポストオーダーで dp を計算
  4. dp[v][0] = Σ max(dp[u][0], dp[u][1])、dp[v][1] = w[v] + Σ dp[u][0]
ヒント3: コード骨格 
def tree_mis(adj, root, W):
    dp = {}
    stack = [(root, -1, False)]
    while stack:
        v, par, done = stack.pop()
        if done:
            nt = 0; t = W[v]
            for u in adj[v]:
                if u != par:
                    nt += max(dp[u])
                    t += dp[u][0]
            dp[v] = (nt, t)
        else:
            stack.append((v, par, True))
            for u in adj[v]:
                if u != par:
                    stack.append((u, v, False))
    return max(dp[root])

模範解答 (Python)

import sys
from collections import defaultdict
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    W = [0] + list(map(int, input().split()))  # 1-indexed
    adj = defaultdict(set)

    def tree_mis(root):
        dp = {}
        stack = [(root, -1, False)]
        while stack:
            v, par, done = stack.pop()
            if done:
                nt = 0; t = W[v]
                for u in adj[v]:
                    if u != par:
                        nt += max(dp[u])
                        t += dp[u][0]
                dp[v] = (nt, t)
            else:
                stack.append((v, par, True))
                for u in adj[v]:
                    if u != par:
                        stack.append((u, v, False))
        return max(dp[root])

    out = []
    for _ in range(Q):
        line = input().split()
        if line[0] == 'add':
            u, v = int(line[1]), int(line[2])
            adj[u].add(v); adj[v].add(u)
        elif line[0] == 'del':
            u, v = int(line[1]), int(line[2])
            adj[u].discard(v); adj[v].discard(u)
        else:
            r = int(line[1])
            out.append(str(tree_mis(r)))
    print('\n'.join(out))

solve()

Step-by-Step 解説

Step 1: 木 DP の定式化

$dp[v][0]$ = v を選ばない場合の部分木の最大重み、$dp[v][1]$ = v を選ぶ場合。遷移: $dp[v][0] += \max(dp[u][0], dp[u][1])$、$dp[v][1] += dp[u][0]$（隣接は選べない）。

Step 2: 反復 DFS でスタックオーバーフロー回避

再帰 DFS では N が大きいとスタックオーバーフロー。明示的スタックで「訪問前」「訪問後（done=True）」の2フェーズに分けて処理する。

Step 3: 動的変更への対応

add/del は隣接リスト（set）の更新のみ O(1)。query 時に毎回 O(N) の DFS を実行。N,Q ≤ 2×10^4 なので合計 O(NQ) = O(4×10^8) はギリギリ（PyPy 推奨）。

Step 4: より高速なアプローチ（発展）

Link-Cut Tree の各ノードに dp 値を持たせ、辺の Link/Cut 後に必要な部分のみ再計算することで O(log N) per update が実現できる（ただし実装は高難度）。

Step 5: 計算量

手法クエリあたり合計
毎回 DFS（本解）$O(N)$$O(NQ)$
LCT + 部分DP（発展）$O(\log^2 N)$$O(Q \log^2 N)$

よくあるミス

ミス原因正しい書き方
再帰 DFS でスタックオーバーフロー N が大きい（Python の再帰上限） 明示的スタック（反復 DFS）を使う
del で存在しない辺を削除 set.remove が KeyError discard を使う
take の初期値を忘れる dp[v][1] = 0 から始めて W[v] を加え忘れる 初期化 t = W[v]

次のステップ

発展問題: 辺の重みもあるとき「最大重み独立集合 vs 最大マッチング」の双対関係（König定理の木上の類似）を示し、効率的なアルゴリズムを設計せよ。

自己評価