LCAを求める際にはオイラーツアーかダブリングを用いる。と述べている記事をよく見かけます。ダブリングの手法について、最初、なぜあのようなコードになるか理解ができなかったので記録としてメモをします。
この記事では次のような問題を解きます。
- 無向な根のある木において、LCAを求めたい。これはたくさんのクエリが与えられる。
- nodeは0-indexedでrootnodeは0
ダブリングについて
過去に書いたSlideShareのAtCoder167Dをダブリングで解くなどを参考にしてください。（他に分かりやすい記事はたくさんあります）
簡単に言えば、(代表されるのは)規則的な遷移のあるグラフにおいて、軽い計算量で事前計算することで、あるノード$x$の$2^k$回目の遷移を$table[k][x]$を参照することで得ることができます。これを用いると任意の回数$a$に対してその経っているビットごとの遷移先を辿ることで高速に($log_{2}x$で)求めることができます。
SlideShareの図の引用になりますが、以下のように計算をします。
ダブリングを用いた根付き木におけるa個先の祖先の求め方
satanicさんの資料がとても分かりやすいです。全ノードにおける１つ先の親を、例えば$ノードx$について、$table[0][x]$とすることで、ダブリングの事前テーブルを計算します。この時、$node0の親は-1$などにしておきます。
※node 0の親は-1など存在しない値にせねばならず、0(自分自身)にしてはダメです。後のLCA判定では親が同じか？という基準で判定を行うため、node 0 の親を0としてしまうと、1つ下のノード$b$と同じ階層に扱われてしまいます。
以下、ノード$x$における$a$個前の祖先を$ancestor(x, a)$とします。
補題: 木におけるノード分辿った後の親ノード
この木のノード数が$numv$の場合、$numv-1$回辿った後の親は必ず$-1$になります。なぜなら、例えば、５個のノードで一番深い場合というのは$0-1-2-3-4$と接続されている場合なので、4回辿ると必ず根に到達します。
LCAの考え方
さて、ここでLCAの特徴を考えます。ここでは、ノード$11と13$のLCA(図では4)を求めたいとします。
まず、ノードを$u=11, v=13$とします。まず最初に、$uとv$の深さの差を求めます。これは、木の構造を作成する際にDFSなりBFSでたどる際に、distといった変数に入れておけば事前計算可能です。さて、深い方のノードが$u$とするなら深さの差は$dist(u) - dist(v) =2$です。
uを移動して$u = ancestor(u, 2)$のように、深さの差分の分だけ辿ります。これで、$u,v = 9,11$となり、お互いの深さ(dist)が同じになりました。求めるノードの深さを同じにするは、LCAを求める際のポイントです。
深さを合わせることにより以下のようにLCAのノードを定義できます。$i=0,1,2...としていった際に、最初にancestor(u,i) == ancestor(v,i)となる、ancestor(uあるいはv, i)のノードがLCAである$。
また、次のようにも言い換えられます。
$i=0,1,2...としていった際に、最後にancestor(u,i) != ancestor(v,i)であるiに対して、ancestor(uあるいはv, i+1)のノードがLCAである$。
つまり、iを0以上の適当な数としたとき、以下の事が言えます。
-
ancestor(u,i) == ancestor(v,i)であるなら、これがLCAノードであるか(図の水色)、あるいは、辿りすぎており、より下にLCAがある(図の紫)
-
ancestor(u,i) != ancestor(v,i)であるなら、LCAノードはこれより上にある(図のピンク)
LCAを求める考察
木が十分に小さい場合、ある同じ深さのノード$u, v$からスタートして、$u!=v$である限り、$u=ancestor(u,1), v=ancestor(v,1)$してやればよいです。つまり、
while u != v:
u, v =ancestor(u,1), ancestor(v,1)
です。ただし、これでは$O(N)$かかってしまうため、大量のクエリには応えられません。
まず、シンプルな二分探索を考えます。例えば、上記の図のように深さが7であるなら、$l,r = 0,7$のように設定し、lにおいて$u,v$のancestorは異なり、rのとき$u,v$のancestorが同じになるようになるような$l,r$を探してやればよいです。この探索は$O(logN)$で動作しますが、各探索中にダブリングの計算には一定の計算量がかかります。
二分探索の場合$mid=(l+r)//2$としますがここで、深さ$15,7,3,1$を探索すると、ダブリングのテーブルを引く回数は(立っているビットだけの探索で)$4+3+2+1$回、tableを引く計算が起こります。
計算量を落とす工夫
そこで、次のようにancestorの計算をしていきます。まず、最初に、$u,v$の深さを$depth$としたとき、$k$をdepth以上の最も近い2のべき乗2**kの$k$とします。例えば、深さ7であればその数以上の近い2のべき乗は8であるためk=3, 深さ8の場合もk=3, 深さ9の場合はその数以上の2のべき乗は16なのでk=4とします。
この時、 $ancestor(u,2^k) == ancestor(v,2^k)$ です。(深さdepth以上の値なので、ルートノードか-1になります)。このkを用いて、以下のような処理を行います。
for i in range(k, -1, -1): # iをk, k-1, ... , 1, 0で回す
nextu = ancestor(u, 2**i) # = table[i][u]
nextv = ancestor(v, 2**i) # = table[i][v]
if nextu != nextv:
u = nextu
v = nextv
return ancestor(u, 1)
ancestorは、$O(1)$の処理です。これは$table[i][node]$そのものであるからです。
この処理の概要は次の通りです。
- 処理1: iに対して$i=kから0まで$、$2^{i}$の祖先を$u,v$に対して辿る。これを$nextu, nextv$とする。
- 処理2-1: $nextu==nextv$の場合、LCAはもっと手前にあるはずなのだから(あるいはそれがLCAなのだから)、$u,v$はそのままにして、$i -= 1$して処理1に戻る
- 処理2-2: $nextu!=nextv$の場合、LCAはもっと上にあることは明確なのだから、$u,v$を$nextu, nextv$にして、$i-=1$して処理1に戻る
図の例で示すと、
- u,vがそれぞれ、$8,4,2,1$個上に登ってよいかを確かめる。$nextu, nextv$が異なる場合は登ってよく、$nextu, nextv$が同じ場合は登ってはならない。
この処理も二分探索ですが、各確認に必要な計算量は$O(1)$となります。
まとめ
- 木において、ダブリングを用いて$a$個先の祖先を$O(log a)$で求めることができます
- LCAは求めたいu,vの深さを合わせたうえで、ancestorが同じ間辿り続け、ancestorが違うようになるノードがLCAと分かりました
- これは二分探索で行うことが可能ですが、深さが2の階乗でないノードに対して行う場合、さらに計算量を減らすことができます。なぜなら、ある深さ$d$のancestorを求めるには、$d$の立っているbit分のテーブルを引くことが必要になるからです。
- 深さ$depth$ではなくて、深さ$depth$以上の最も近い深さから探索を開始します。これにより、事前計算したダブリングテーブルの行を1行引けばよいです。