木の中の2つのノードuとvのLCAは,根から最も遠い(最も深い)共通の祖先である.
では、LCAをどう救うのか.

Method 1

ルートノードから各ノードへのパスを比較することでナビゲートできます.

本からu,vへの経路は、それぞれアレイに

記憶する.

の2つの配列を比較して得られた共通の祖先の中で、根から最も遠いのはLCAである.

時間的複雑度はO(N)であった.

Method 2

もう一つのNaive HanfulはParent Pointerを利用していますmethod 1とは異なり、uまたはvからルート方向に順番に進みます.

まずuから根まで巡回し、祖先を保存する.

v根元を巡回するときは、u上の祖先と同じものがあるかどうかを確認します.このとき、最初に同じものがLCAです.

時間的複雑度はO(N)であった.

Method 3

	   1
     /   \
    2     3
  /   \
 4     5

上記の木がある場合はDFSを使ってEuler Tourを行います.sub−treeの根rに達すると、rの子孫uに戻り、その後rに戻り、他の子孫vに下がる.すなわち,uとvは共通の祖先rを経なければならず,この特徴を利用して問題を解くことができる.
まず、3つの配列が必要です.

dfs node[]:Euler Tourにアクセスするノード

を順番に格納

dfsレベル[]:Euler Tourノードにアクセスするレベル

を順番に格納

firstOccur[]:各ノードがEuler Tourで初めて出現するインデックス

上記の場合、次の配列が生成されます.

dfs_node[]   = {1, 2, 4, 2, 5, 2, 1, 3, 1}
dfs_level[]  = {0, 1, 2, 1, 2, 1, 0, 1, 0}
firstOccur[] = {0, 1, 7, 2, 4 }

これを用いてLCA(4,3)を解いた.各ノードが最初に生成したインデックスは7,2である.共通の祖先は、2と7の間でlevelが最も低いノードである可能性があります.したがって、dfs level[2:7]を調べると、index=6のとき、この最小値がlevel=0のノードはすぐにlcaになり、dfs node[6]でnode 1であることを決定できます.
この場合,区間の最小値を1つずつ比較するのではなく,Segment TreeをベースとしたRange Minimum Query(RMQ)で検索する方が早い.
時間的複雑度は,DFSにより配列とセグメントツリーのO(N),各クエリのO(logn)を生成する.

Method 4

method 2では,根の方向に沿って巡回し,互いの祖先を比較した.しかし、すぐにはいかない.すべての祖先が一つ一つ比較しているからだ.逆に、バイナリ検索で検索する値がmidより小さい場合は調査(l,mid−1)、midより大きい場合は調査(mid+1,r)は、祖先の調査区間を選択するように、解を求めるのが速い.
まず、各ノードの2^k番目の祖先を次のように保存します.

memo[i][j] = i-th node의 (2^j)-th ancestor
		   = memo[ memo[i][j-1] ][j-1]

( 0 <= j <= log ), ( log = ceil( log2(N) ) )

この二次検索LCAを利用します.

1. u 와 v의 level을 동일하게 맞춘다. 이때, u == v 라면, 다른 하나가 조상인 것이다.
2. loop j: log to 0
	if ( memo[u][j] != memo[v][j] ){
    	u = memo[u][j];
        v = memo[v][j];
    }
3. memo[u][0] 이 LCA이다. (memo[v][0])

このようにDynamic Programmingを利用すればLCAを簡単に見つけることができ、二重リンク方法と呼ばれています.
時間的複雑度は,dp生成時はO(NlogN),各クエリ時はO(logN)である.
(この形式のrmqデータ構造は疎表とも呼ばれる.)