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