算法簡介
另一種理解方式是把T理解為一個無向無環(huán)圖，而LCA(T,u,v)即u到v的最短路上深度最小的點。
這里給出一個LCA的例子：
對于T=
V={1,2,3,4,5}
E={(1,2),(1,3),(3,4),(3,5)}
則有：
LCA(T,5,2)=1
LCA(T,3,4)=3
LCA(T,4,5)=3
算法
離線算法 Tarjan
利用并查集優(yōu)越的時空復(fù)雜度，我們可以實現(xiàn)LCA問題的O(n+Q)算法，這里Q表示詢問的次數(shù)。
Tarjan算法基于深度優(yōu)先搜索的框架，對于新搜索到 的一個結(jié)點，首先創(chuàng)建由這個結(jié)點構(gòu)成的集合，再對當(dāng)前結(jié)點的每一個子樹進(jìn)行搜索，每搜索完一棵子樹，則可確定子樹內(nèi)的LCA詢問都已解決。其他的LCA詢問的結(jié)果必然在這個子樹之外，這時把子樹所形成的集合與當(dāng)前結(jié)點的集合合并，并將當(dāng)前結(jié)點設(shè)為這個集合的祖先。
之后繼續(xù)搜索下一棵子樹，直到當(dāng)前結(jié)點的所 有子樹搜索完。這時把當(dāng)前結(jié)點也設(shè)為已被檢查過的，同時可以處理有關(guān)當(dāng)前結(jié)點的LCA詢問，如果有一個從當(dāng)前結(jié)點到結(jié)點v的詢問，且v已被檢查過，則由于 進(jìn)行的是深度優(yōu)先搜索，當(dāng)前結(jié)點與v的最近公共祖先一定還沒有被檢查，而這個最近公共祖先的包涵v的子樹一定已經(jīng)搜索過了，那么這個最近公共祖先一定是v 所在集合的祖先。
下面給出這個算法的偽代碼描述：
由于是基于深度優(yōu)先搜索的算法，只要調(diào)用LCA(root[T])就可以回答所有的提問了，這里root[T]表示樹T的根，假設(shè)所有詢問(u,v)構(gòu)成集合P。
在線算法 倍增法
每次詢問O(logN)
d[i] 表示 i節(jié)點的深度， p[i,,j] 表示 i 的 2^j 倍祖先
那么就有一個遞推式子 p[i,,j]=p[p[i,,j-1],,j-1]
這樣子一個O(NlogN)的預(yù)處理求出每個節(jié)點的 2^k 的祖先
然后對于每一個詢問的點對(a, b)的最近公共祖先就是：
先判斷是否 d[a] > d[b] ,如果是的話就交換一下(保證 a 的深度小于 b 方便下面的操作)，然后把b 調(diào)到與a 同深度, 同深度以后再把a, b 同時往上調(diào)(dec(j)) 調(diào)到有一個最小的j 滿足p[a,,j]!=p[b,,j] (a b 是在不斷更新的), 最后再把 a, b 往上調(diào) (a=p[a,0], b=p[b,0]) 一個一個向上調(diào)直到a = b, 這時 a or b 就是他們的最近公共祖先。
算法實例
問題描述：
設(shè)計一個算法，對于給定的樹中 結(jié)點返回它們的最近公共祖先。
編程任務(wù)：
對于給定的樹和樹中結(jié)點對，計算結(jié)點對的最近公共祖先。
數(shù)據(jù)輸入：
由文件input.txt給出輸入數(shù)據(jù)。
第一行有1個正整數(shù)n，表示給定的樹有n個頂點，編0號為1，2，…，n。編號為1 的頂點是樹根。接下來的n 行中，第i+1 行描述與i 個頂點相關(guān)聯(lián)的子結(jié)點的信息。每行的第一個正整數(shù)k表示該頂點的兒子結(jié)點數(shù)。其后k個數(shù)中，每1 個數(shù)表示1 個兒子結(jié)點的編號。當(dāng)k=0 時表示相應(yīng)的結(jié)點是葉結(jié)點。文件的第n+2 行是1 個正整數(shù)m，表示要計算最近公共祖先的m個結(jié)點對。接下來的m行，每行2 個正整數(shù)，是要計算最近公共祖先的結(jié)點編號。
結(jié)果輸出:
將編程計算出的m個結(jié)點對的最近公共祖先結(jié)點編號輸出到文件output.txt。每行3 個
正整數(shù)，前2 個是結(jié)點對編號，第3 個是它們的最近公共祖先結(jié)點編號。
輸入文件示例(input.txt)
12
3 2 3 4
2 5 6
0
0
2 7 8
2 9 10
0
0
0
2 11 12
0
0
5
3 11
7 12
4 8
9 12
8 10
輸出文件示例(output.txt)
3 11 1
7 12 2
4 8 1
9 12 6
8 10 2
