ARC086 E問題 Smuggling Marbles

E: Smuggling Marbles - AtCoder Regular Contest 086 | AtCoder

解法

縮約解について説明する。よく考えるとマージテク解と本質的に同じ。

深さが等しい頂点をまとめて計算できるのは自明だと思いたい。普通にやると$O(depth\times n)$ だが、各深さごとに木を縮約してあげると $O(n \log n+ n\log (10^9+7))$ で解ける。

縮約するとなぜ計算量が落ちるのかというと、内部節点がかならず分岐を持つ木であれば、内部節点の個数は葉の個数より少ないためである。

f:id:pekempey:20171211161024p:plain

内部節点の個数の評価は二分木で有名だろう。一応説明する。

証明(内部節点の個数の評価)

葉と隣接する内部節点をひとつ選び、それを改めて葉に置き直す操作を考える(図を参照)。頂点がひとつになるまでこの操作を繰り返すと、その回数は内部節点の個数と一致する。この操作によって葉は少なくとも一つ減るため、(内部節点の個数)<(葉の個数)であることが言える。(証明終わり)

f:id:pekempey:20171211161743p:plain

感想

縮約すると計算量が落ちるのには気がついたのだけど、縮約の仕方がまずかったみたいでコンテスト中には通せなかった。縮約は post-order に並べて隣接要素の LCA を取っていくと良いのだが、変な方法でやろうとして失敗した。