LCA およびその求め方
LCA とは
LCA(Lowest Common Answer / 最小共通祖先) とは、根付き木構造においてある$ 2頂点$ u, vが与えられたとき、$ u, vのいずれも子に持つような頂点のうち、最も根から遠いものを指す。
使い所
任意の$ 2頂点間の距離クエリを解く
根から頂点$ vへの距離を$ D(v)とすると、頂点$ u, v間の距離は$ D(u) + D(v) - 2(D(\mathrm{lca}(u, v)))
任意の$ 2頂点$ u, vについて$ uが$ vの子であるか判定する
$ \mathrm{lca}(u, v) = vならば真
任意の$ 2頂点$ u, v間のパス上に頂点$ aがあるか求める
$ u, a間の距離 + $ v, a間の距離を$ 2頂点間の距離クエリと同様に解く。これと$ u, v間の距離が等しければ$ u, v間のパス上に$ aがある。
求め方
いくつもの求め方が考案されているが、順を追って説明していこう。
1. 愚直解
空間計算量を無視すると、以下のようにできる。
頂点$ u, vの LCA を求める。
根ヘ向かって$ uから全ての頂点を走査する。通過した頂点を全て記録する。
根へ向かって$ vから全ての頂点を走査する。$ uから走査した時に通過した頂点のいずれかに初めて到達した時、その頂点が LCA である。
このアルゴリズムの時間計算量は$ \Omicron(N)となる。気持ちとしては$ \Theta(\log{N})なのだが、全頂点が一列に繋がったようなグラフのことを考えると非常に低速になる。よって、何回もクエリを処理する場合にはこれではいけない。
2. ダブリング
与えられる頂点$ u, vの根からの深さが等しいとしよう。
この時は$ u, v同時に一つずつ根の方向へと走査できる。
ところで、根の方向へと走査するとき、$ k頂点遡った後の頂点を求めることはダブリングでできる。$ u, vから$ k頂点遡った後の頂点が等しいかどうか？という判定問題について、真となる$ kの最小値を求めれば、$ uから$ k頂点遡った頂点が LCA になる。
この判定問題は単調性のあるものになるので、二分探索をすると$ \Omicron((\log{N})^2)で解ける。
しかし、さらに高速にする方法として
$ k = \lceil \log_2{N} \rceilから開始する。
$ u, vの$ 2^k頂点先が一致していないならば、$ u, vをそれぞれ$ 2^k頂点遡った先の頂点に置き換える。
$ kを$ 1減らして一致しているかどうかの判定に戻る。なお、$ 1減らしたときに$ kが$ -1になったら終了する。
というように処理すると、$ \Omicron(\log{N})で処理できる。
これで$ u, vの深さが等しい時の処理ができた。
次に一般の$ u, vについてだが、これは深い方の頂点について深さが等しくなるよう先に遡っておけば良く、これもダブリングしたデータを活用すると$ \Omicron(\log{N})で収まる。
よって、前処理$ Ο(N \log N)およびクエリごとに時間計算量$ \Omicron(\log{N})で任意$ 2頂点の LCA を求めることができた。
3. Euler Tour + RMQ
Euler Tour を知らないという方は先にそちらを確認することをお勧めする。
まず、Euler Tour 順に並べた頂点列と、各頂点の in, out をどこかに保管しておく。
さらに、Sparse Table を使って以下の情報を取得できるようにする。
{number, depth}の列について、区間内で最小のdepthを達成する要素のnumber
ここで、Euler Tour は深さ優先探索の話なので、任意の部分木は必ず Euler Tour 列上での連続部分列として表される。
とすれば、欲しいのは$ u, vそれぞれを根とした部分木を接続するような頂点である。
重要な事実として、深さ優先探索は「部分木単位の探索」でありなおかつ「小さい部分木から終える」探索である。
そのことを念頭に置いて深さ優先探索で$ u, vの間を探索することを考えると、必ず LCA の頂点より上には到達しないまま$ u, v間を探索し終えることができる。
したがって、探索中に訪れる深さが最小の頂点が、そのまま LCA であることが期待されるため、
$ uの in と$ vの out (ただし前後が反転した場合は u, v を swap する)の間に含まれる深さが最小の頂点を求めてこれを LCA とする。これは Sparse Table で出来るので、構築$ Ο(N \log{N})およびクエリ$ \Omicron(1)で処理できた。
例題