lowest common ancestor(LCA)とは、根付き木の2つの頂点に対して、共通祖先(common ancestor)のうち最も深さが深い頂点のこと、またそれを求める問題のことである。 最小共通祖先, 最小共通先祖, nearest common ancestor, NCA, 最近共通祖先 などとも呼ばれる。

クエリ問題版では、前処理に$Θ(n)$・クエリが$Θ(1)$時間の2つのアルゴリズム、"Euler tourによる±RMQへの還元"や"Schieber-Vishkin algorithm"などが知られている。

定義

根付き木$T = (V, E, root)$, 頂点$v, u \in V$に対して、 $$ LCA_{T}(v, u) = \underset{a \in V, ancestor(v, a) ∧ ancestor(u, a)}{\operatorname{arg\,max}} depth(a) $$ を$T,v,u$のLowest common ancestorという。

クエリ問題

根付き木が事前に与えられる。 クエリでは前処理結果と2つの頂点が与えられて、入力のLCAを求める。

動的問題

根付き木に対して初期状態を求める。 LCAクエリでは内部状態と2つの頂点が与えられて、入力のLCAを求める。

パラメータ

• $n$ = 木の頂点数

アルゴリズム

ダブリングアルゴリズム

それぞれの頂点が$2^k$番目の"k-親"への参照と深さを保持する。クエリでは、2つの頂点の祖先の深さを比較しながら処理をする。{{要加筆}}

クエリ問題版に対して、前処理$Θ(n\log n)$時間, $Θ(n\log n)$空間, クエリ$Θ(\log n)$時間を達成する。

パスへの分割

"パスへの分割(木)"をする。クエリでは、パスの深さを比較しながら上っていき、同じパスに到達したら終了する。

クエリ問題版に対して、前処理$Θ(n)$時間, $Θ(n)$空間, クエリ$Θ(\log n)$時間を達成する。

動的問題版に対しては"link-cut tree"を用いることでクエリならし$Θ(\log n)$時間を達成する。

"euler tour"による±RMQへの還元

"euler tour#頂点記録版"を用いて頂点の列を作る。頂点と一緒に深さも記録する。さらに、頂点に対して列中での一番左・右の出現位置L,Rをそれぞれ記録する。 このとき、頂点v,uのLCAは列中でv,uの出現を全て含む極小の区間、つまり$[L_v, R_u]$もしくは$[L_u, R_v]$の中で深さが最小である頂点である。この列の深さ情報は隣接する2つの要素の差が必ず±1になるので、それを利用できる。 ±1の制約を使わずに単なる"range minimum query"と考えることもできる。

クエリ問題版に対しては"±RMQ#アルゴリズム"を用いることができ、前処理$Θ(n)$時間, クエリ$Θ(1)$時間を達成する。

動的問題版に対しては"euler tour tree"を用いることで様々な操作をサポートしてクエリ$Θ(\log n)$時間を達成できる。{{要加筆}}

Schieber-Vishkin algorithm

"Schieber-Vishkin algorithm"を用いることで、クエリ問題版に対して前処理$Θ(n)$時間, クエリ$Θ(1)$時間を達成する。