Day 123-Q4 | 森上のLink操作と最大独立集合の動的維持

問題

$N$頂点の森（最初は辺が1本もない）が与えられる。$Q$個のクエリが順に与えられ、各クエリは頂点$u,v$を結ぶ辺を追加する（Link操作、$u,v$は必ず異なる木に属する）。各クエリ後の森全体の最大独立集合（MIS）サイズの合計を出力せよ。

入力形式

N Q
u_1 v_1
...
u_Q v_Q

制約

$2 \le N \le 2000$

$1 \le Q \le N-1$

$1 \le u_i, v_i \le N$

各クエリ時点でu,vは異なる木

入出力例

入力例1

出力例1

概念図: 各クエリ後の森の変化

ヒント（段階的開示）

ヒント1: 方向性

木のMISは根を1つ決め「選ぶ/選ばない」の2状態を持つ標準的な木DPでO(木のサイズ)で計算できる。問題は辺が1本ずつ増えていくたびに、この値を効率よく更新できるか。

ヒント2: アプローチ

最も愚直な発想は「辺を追加するたびに合体後の木全体で木DPをやり直す」。1回のコストは合体後の木のサイズに比例するため最悪O(NQ)だが、N,Q≤2000の制約なら十分高速に動く。まず正しく動く愚直解を書く視点が実務でも重要。

ヒント3: 誘導（コード骨格）

Union-Findで各木の代表頂点とMIS値を管理し、Linkのたびに①旧2木のMISを合計から引く②辺追加③合体後の木全体でDP再計算④加算、を行う。

def compute_mis(root, adj):
    dp0, dp1 = {}, {}
    stack = [(root, -1, False)]
    while stack:
        v, p, done = stack.pop()
        if not done:
            stack.append((v, p, True))
            for u in adj[v]:
                if u != p:
                    stack.append((u, v, False))
        else:
            d0, d1 = 0, 1
            for u in adj[v]:
                if u != p:
                    d0 += max(dp0[u], dp1[u])
                    d1 += dp0[u]
            dp0[v], dp1[v] = d0, d1
    return max(dp0[root], dp1[root])

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1

    adj = [[] for _ in range(N + 1)]
    parent = list(range(N + 1))
    size = [1] * (N + 1)
    comp_mis = {v: 1 for v in range(1, N + 1)}
    total_mis = N

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def compute_mis(root):
        dp0, dp1 = {}, {}
        stack = [(root, -1, False)]
        while stack:
            v, p, done = stack.pop()
            if not done:
                stack.append((v, p, True))
                for u in adj[v]:
                    if u != p:
                        stack.append((u, v, False))
            else:
                d0, d1 = 0, 1
                for u in adj[v]:
                    if u != p:
                        d0 += max(dp0[u], dp1[u])
                        d1 += dp0[u]
                dp0[v], dp1[v] = d0, d1
        return max(dp0[root], dp1[root])

    out = []
    for _ in range(Q):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1

        ru, rv = find(u), find(v)
        total_mis -= comp_mis[ru]
        total_mis -= comp_mis[rv]

        adj[u].append(v)
        adj[v].append(u)

        if size[ru] < size[rv]:
            ru, rv = rv, ru
        parent[rv] = ru
        size[ru] += size[rv]

        new_mis = compute_mis(ru)
        comp_mis[ru] = new_mis
        total_mis += new_mis

        out.append(str(total_mis))

    print('\n'.join(out))

solve()

計算量: 1回のLinkはO(合体後の木のサイズ)。N,Q≤2000の制約下で最悪でもO(N^2)=4×10^6程度に収まる。入力例1を手計算し、各クエリ後の合計が4,4,3,3になることを確認済み（5頂点パスのMIS=⌈5/2⌉=3とも一致）。

Step-by-Step 解説

1木の最大独立集合DP
dp1[v]=vを選ぶ場合、dp0[v]=vを選ばない場合。dp1[v]=1+Σdp0[child]、dp0[v]=Σmax(dp0[child],dp1[child])。木全体のMISはmax(dp0[root],dp1[root])。

2Union-Findで木の境界を管理
各木の代表頂点と現在のMIS値をUnion-Findと辞書で管理。Linkのたびに合体前の2木のMIS値を合計から引き、後で新しいMIS値を足し直す。

3再計算のコストとその許容範囲
compute_misは合体後の木全体を1回走査。N≤2000の制約下では最悪でもO(N^2)=4×10^6程度に収まりPythonでも現実的な時間で動作する。

4なぜ反復（スタック）でDPを書くか
Pythonの再帰は既定で1000段程度の制限があり、細長い木で容易にオーバーフローする。(頂点,親,処理済みフラグ)の3つ組で反復的な後行順走査にする。

5正しさの検証
入力例1を手計算し合計4,4,3,3を確認。パスグラフのMIS一般式⌈n/2⌉とも一致する。

よくあるミス

ミス	原因	正しい書き方
Union-Findの併合前にMIS値を差し引くタイミングを間違える	find呼び出し前に辺を追加し古い代表頂点の特定に失敗する	辺追加前に find(u), find(v) で古い代表頂点を確定させる
再帰DFSでRecursionErrorになる	パス状の木で深さ2000に達し得ることを見落とす	反復的なスタックベースの後行順走査を使う
compute_misを毎回全頂点に対して呼んでしまう	変化していない木まで再計算してしまう	合体でできた新しい木の代表頂点1つに対してのみ再計算する
Union by sizeを実装せず常に一定方向に繋げる	木がチェーン状に偏る	サイズの小さい方を大きい方に繋げる

次のステップ

発展: 真に効率的な動的アルゴリズムではEuler Tour TreeやLink-Cut Tree上で、各頂点の4状態をsmall-to-largeでマージすることでならしO((N+Q)log N)まで高速化できる。"Dynamic Trees Dynamic Programming"で調べてみるとよい。
次回予告: 含意グラフとSCC分解による2-SAT充足可能性判定

自己評価

完全理解おおむね理解要復習

Day 123-Q4 — 森上のLink操作と最大独立集合の動的維持

問題