AtCoder Grand Contest 018 D. Tree and Hamilton Path

誤読したら解けたんだけど(は？)、未証明が発生した。

問題概要

読んで: D - Tree and Hamilton Path

解法

まず誤読した問題を書きます:

最長のHamilton Cycleを求めてください。

これは多分900点ぐらいです、以下に解法を書くので考えたい人は先に考えてください。

ネタバレ回避用余白

結論から言うと、任意の頂点から初めて良い以下の再帰で解けます。

gist2e95637586b5bb181112b6d922283ff1

sz[v]は適当に根付きにした木のvを根とする部分木のサイズで、mx[v]はvの子が根であるような部分木の最大サイズです。

初めに呼び出すのはdfs(root, root, N)です。

これは本来の問題より簡単で、結局「頂点の順列であって、隣り合う頂点のLCAの深さの和が最小になるものを求めてください(順列の先頭と末尾も隣り合っていると見做す)」になって、当然LCAが根であるのが深さが最小であることをなどを考えると貪欲にやっていいことが分かります。

次に、誤読したのでここから修正を試みます。

最長のハミルトンサイクルは求まっているので、適当な部分でサイクルを切ってハミルトンパスにすることにします。

未証明なのは、「最長のハミルトンサイクルから取り除ける最短のパスを除いたものは、最長でないハミルトンサイクルから取り除ける最短パスを除いたものより長い」です。証明して助けてください(まあ想定解から示せそうなんだけど、それなら想定解で解けばいいんだから負けだろ)。

さて、取り除ける最短パスってなーんだ？実はこれは与えられた木の単一の辺になって、2本以上の辺から成るパスであることはありません。

上の解法が分かった人ならすぐ分かりそうですが一応証明の概略を書きます。

まず求めたのはサイクルなので、適当にシフトしても問題ないです。

ということで先頭をとりあえず根に固定します(根は任意なので実質任意の頂点を先頭に持ってきているのと変わりません)。

この時取り除かれるパスというのは、順列の末尾の頂点と根を端点とするパスです。

つまり引かれる長さは末尾の頂点の深さです。

今、「取り除かれるパスを単一の辺に出来る」ということを示したいので、末尾に持ってきたいのは、根の子です。

上のコードでいうremが-1以下になる時、任意の根の子を末尾に持ってこれます(三角不等式を考えれば言えます)。

そうでない時、mx[v]を与える根の子uは一意に決まります。ここで、mx[v] == N-mx[v]ならば、uは末尾に持ってこれます(これは実はrem == 0と同値です、重心ですね、バーカ)(この時点で、他の子は絶対に持ってこれません。他の子の子孫も持ってこれないので、2辺以上のパスならどうにかなるということもないです)。

そうでない時、末尾に持ってこれるのは、uの子孫の何かのみです。ここで、「持ってこれる頂点の内、最も深さが浅いもの」を持ってきてることにします。これをxとします。

さて、上の解法を理解すると分かりますが、このケースでは、順列のN-1番目もuの子孫になってないとおかしいです(その頂点をyとしましょう)。もっと言えばyはxの子孫として良いです(これはね、多分そう(は？)、xとして持ってこれるものが全て子を持っていないケースはないと思ってるけど、ちょっと自信ない、未証明2)(追記: 末尾に持ってこれる頂点は部分木をなしているはずなので、大丈夫)。なので、もう一度順列を右に1回シフトしてxを先頭、yを末尾に持ってくると、深さが減ります。2辺以上のパスが取り除かれる場合はこうして取り除かれるパスの長さを減らせるので、結局除かれるのは1辺であるということが分かります。

後は「取り除ける1辺の内最短のものを引く」をすれば良くて、これで答えが出ます。

多分そう、だってACしたから。