ABC014 D問題 閉路

abc014.contest.atcoder.jp

 セグメント木、楽しくなってきた。

基本方針

 節aからbまでの経路は一本しかなくて、しかもその経路は必ずaとbのLCA(Lowest Common Ancestor、最近共通祖先)を含む。なので、(aの深さ-LCAの深さ)+(bの深さ-LCAの深さ)+1で答えは求められる。

具体的な方針

 解説はダブリングでやってたけど、セグ木が組めないので練習がてら組みます。

 オイラーツアーで木を一次元配列にバラします。ちょっと調べれば出てくるとは思うけど、深さ優先探索をして、「重複ありで」通過した頂点を配列に格納していくやつ。部分木が隣接する区間になるので、色々と都合がよくなります。各ノードの深さと、各ノードが最初に出てきた場所も記憶しておきます。最終的に配列のサイズは(辺数)*2+1になります(植木算の要領)。

 こうすると、節a、bを含む部分木で、最も浅い部分っていうのがLCAになります。で、深さを配列にとってるので、区間最小値の問い合わせ問題、つまりRMQに帰着します。RMQを解く方法の一つとして、セグメントツリーがあるので今回はこれを実装します。

 で、実装なんだけど、具体的な話は蟻本を参照するのが一番良さそう。あるいはプログラミングコンテストでのデータ構造を見てもいい。こっちも秋葉先生のスライドなので全く同じ実装が乗ってます。

 まあ少しだけ言及すると、セグメントっていうのは言葉通り断片って意味で、各断片の情報を記憶してます。で、その断片を完全二分木で親の区間が子を内包するように持ってあげれば、深さがlogNに抑えられるので、O(logN)での更新とO(logN)でのクエリ処理ができます。

実装

abc014.contest.atcoder.jp

 結構いい出来なので見てほしい気持ちがある。ちなみにセグ木はここに置いてあります。継承してerrorとevalをオーバーライドすれば使えるはず。LCAサンプルとして置いておきます。

感想

 一回組んだら自信がつきますね。これからも色々な実装をしっかりとモノにしていきたいです。