競プロ参戦記 第7回「近道」 Codeforces #506 E
過去問を解いたので解説します。
E. Tree with Small Distances
問題概要：頂点数 N の無向グラフが与えられる。これはツリーである (連結、閉路なし)。いくつかの辺を追加して、点1から他の点への距離をすべて2以下にした。追加した辺の個数の最小値を求めよ。
(ループや多重辺について条件が設定されていますが、無視していいです。)
簡単に分かることを確認すると、追加する辺は必ず点 1 に隣接させるのがベストです。また、点 1 から距離が 2 以上の点 v について、点 v と点 1 の距離を 2 以下にするには、点 v 自身か、点 v の隣のノードのいずれかを点 1 と結ぶ必要があります。
グラフを点 1 を根とするツリーとみなして、深さ優先探索をしましょう。訪問した点 v から戻る時点で、その点 v の子孫がすべて、点 1 との距離 2 以下になるようにします。これにより、最終的に条件 (点 1 との距離が常に 2 以下) が満たされます。
点 v を訪問して、v の各子ノードへの再帰が終わった時点で、v の孫世代以下はすべて距離2以下のはずです。もし v の子ノードのいずれかが距離 3 以上なら、その子ノードか v を点 1 に結ばなければいけません。ここで、子ノードではなく、点 v を点 1 と結ぶのが最適です。なぜなら、他の子ノードや v の親ノードも条件を満たせる可能性があるからです。
辺を追加すると各点の点 1 との距離が変わってしまうので検討がいります。孫世代には影響はありません。祖先世代は、後々戻ったときに更新すれば十分です。結局、点 v 自身の距離だけ更新すればよいはず。
文章で説明するの難しい…… 詳しくはコードを読んでください。意外に簡潔です。
しかし、こうも複雑だと結果の正当性 (最小であることの証明) が分かりづらいです。正しそうな気はしますが、形式的な証明は思いつきません。
提出：
スレッドによるスタックオーバーフロー回避
与えられたグラフが 1→2→3→4→5 のような直線状で、頂点数が20万もあると、深さ優先探索はスタックをかなり消費します。Rust (1.26.0) ではたいていスタックオーバーフローします。上述のDFSは、普通に書くとこの問題にあたります。回避策は思いつくかぎり3つ。
1. スタック (Vec) を使ってループで書く。
2. 継続渡しスタイルにする。
3. 巨大なスタックを持つスレッドを作る。
1., 2. はめんどうなので、今回の提出では 3. の方法を使いました。提出を参照。メモリ使用量に注意。
参考 (2015年5月1日付の回答)：
更新履歴
改稿 (2018/09/05): 解説の一部を読みやすくした。