過去問を解いたので解説します。

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): 解説の一部を読みやすくした。