D - Minimum Steiner Tree Editorial
by 
rsk0315
ユーザ解説 同様、指定された頂点のうちの一つを根とする根つき木を考えます。根を \(r\) とおきます。
このとき、「各 \(i\) (\(1\le i\le K\)) に対し、\(r\) と \(V_i\) を結ぶパスに含まれる頂点」の和集合が、答え（条件を満たすうちで頂点数が最小）となる木の頂点集合となります。
証明
$r$ と $V_i$ を結ぶパスに含まれる頂点を取り除くと、$r$ と $V_i$ が連結でなくなるため木ではなくなります。 逆に、こうして作られる木は条件を満たすため、これ以外の頂点を追加する必要はありません。さて、各頂点 \(v\) に対して、\(r\) を根としたときの親 \(p_v\) を求めておくと、下記の手続きによって該当の集合を構成することができます。ただし、\(p_r = \infty\) としておきます。
- \(S \gets \emptyset\) で初期化する。
- \(v \gets V_1, V_2, \dots, V_K\) に対して下記を行う。(loop A)
- \(u \gets v\) で初期化する。
- \(u \lt \infty\) である間、下記を繰り返す。(loop B)
- \(u \in S\) であれば loop B を終了 (break) する。
- そうでなければ、\(S \gets S\cup\{u\}\) および \(u \gets p_u\) で更新する。
証明
$u \in S$ ならば $(u = r) \vee (p_u \in S)$ であることを示します。 これを示せば、各 $i$ について $V_i\in S$ であることから従います。 帰納的に示します。まず、loop A を行う前は $S=\emptyset$ なので明らかに成り立ちます。 $v \gets V_i$ での loop A の開始時に条件が成り立っていると仮定すると、そのループの完了時にも条件が成り立つことを示します。 loop B が break されないときは明らかに成り立ちます。 loop B が break されるときは、帰納法の仮定から従います。各頂点に対して、\(S\) に追加されるのは高々 1 回であることから、loop B の内部が実行されるのは全体で高々 \(N\) 回であることがわかります。 そのため、全体で \(O(N)\) 時間で求められます。
おまけのポエム
ABC 367 E の線形時間解法 を実装する際に、部分問題として上記のような手続きを実装していました（long-path decomposition をする際です）。コンテストに使う用のライブラリとしては必要がないと思われる場合でも、実装しておくとコンテスト中の発想に役立つ場合があってうれしいですね。
posted:
last update: