概述篇
LCA (Least Common Ancestors) ，即最近公共祖先，是指這樣的一個問題：在一棵有根樹中，找出某兩個節點
u
和
v
最近的公共祖先。
LCA 可分為線上算法與離線算法
- 線上算法：指程式可以以序列化的方式一個一個處理輸入，也就是說在一開始并不需要知道所有的輸入。
- 離線算法：指一開始就需要知道問題的所有輸入資料，而在解決一個問題後立即輸出結果。
算法篇
對于該問題，很容易想到的做法是從
u、v
分别回溯到根節點，然後這兩條路徑中的第一個交點即為
u、v
的最近公共祖先，在一棵平衡二叉樹中，該算法的時間複雜度可以達到 O(logn) ，但是對于某些退化為鍊狀的樹來說，算法的時間複雜度最壞為 O(n) ，顯然無法滿足更高頻率的查詢。
本節将介紹幾種比較高效的算法來解決這一問題，常見的算法有三種：線上 DFS + ST 算法、倍增算法、離線 Tarjan 算法。
接下來我們來一一解釋這三種
的算法。
前方多圖麼？千千也不知道，要不要發出警告呢？(；′⌒`) （逃
線上 DFS + ST 算法
首先看到
ST
你會想到什麼呢？（腦補許久都沒有想到它會是哪個單詞的縮寫）
看過前文 『資料結構』RMQ 問題 的話你便可以明白
ST算法
的思路啦~
So ，關于 LCA 的這種線上算法也是可以建立在 RMQ 問題的基礎上咯~
我們設
LCA(T,u,v)
為在有根樹
T
中節點
u、v
的最近公共祖先，
RMQ(A,i,j)
為線性序列
A
中區間
[i,j]
上的最小（大）值。
如下圖這棵有根樹：
我們令節點編号滿足父節點編号小于子節點編号（編号條件）
可以看出
LCA(T,4,5) = 2, LCA(T,2,8) = 1, LCA(T,3,9) = 3
。
設線性序列
A
為有根樹
T
的中序周遊，即
A = [4,2,5,1,8,6,9,3,7]
。
由中序周遊的性質我們可以知道，任意兩點
u、v
的最近公共祖先總在以該兩點所在位置為端點的區間内，且編号最小。
舉個栗子：
假設
u = 8, v = 7
，則該兩點所确定的一段區間為
[8,6,9,3,7]
，而區間最小值為
3
，也就是說，節點
3
為
u、v
的最近公共祖先。
解決區間最值問題我們可以采用 RMQ 問題中的
ST 算法
。
但是在有些問題中給出的節點并不一定滿足我們所說的父節點編号小于子節點編号，是以我們可以利用節點間的關系建圖，然後采用前序周遊來為每一個節點重新編号以生成線性序列
A
，于是問題又被轉化為了區間最值的查詢，和之前一樣的做法咯~
時間複雜度： n×O(logn) 預處理 + O(1) 查詢
想了解
RMQ 問題
的解法可以戳上面的連結哦~
以上部分介紹了 LCA 如何轉化為 RMQ 問題，而在實際中這兩種方案之間可以互相轉化
類比之前的做法，我們如何将一個線性序列轉化為滿足編号條件的有根樹呢？
- 設序列中的最小值為 Ak ，建立優先級為 Ak 的根節點 Tk
- 将 A[1...k−1] 遞歸建樹作為 Tk 的左子樹
- 将 A[k+1...n] 遞歸建樹作為 Tk 的右子樹
讀者可以試着利用此方法将之前的線性序列
A = [4,2,5,1,8,6,9,3,7]
構造出有根樹
T
，結果一定滿足之前所說的編号條件，但卻不一定唯一。
離線 Tarjan 算法
Tarjan 算法是一種常見的用于解決 LCA 問題的離線算法，它結合了深度優先搜尋與并查集，整個算法為線性處理時間。
首先來介紹一下 Tarjan 算法的基本思路：
- 任選一個節點為根節點，從根節點開始
- 周遊該點 u 的所有子節點 v ，并标記 v 已經被通路過
- 若 v 還有子節點，傳回 2 ，否則下一步
- 合并 v 到 u 所在集合
- 尋找與目前點 u 有詢問關系的點 e
- 若 e 已經被通路過，則可以确定 u、e 的最近公共祖先為 e 被合并到的父親節點
僞代碼：
Tarjan(u) // merge 和 find 為并查集合并函數和查找函數
{
for each(u,v) // 周遊 u 的所有子節點 v
{
Tarjan(v); // 繼續往下周遊
merge(u,v); // 合并 v 到 u 這一集合
标記 v 已被通路過;
}
for each(u,e) // 周遊所有與 u 有查詢關系的 e
{
if (e 被通路過)
u, e 的最近公共祖先為 find(e);
}
} - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
感覺講到這裡已經沒有其它内容了，但是一定會有好多人沒有了解怎麼辦呢？
即使千千不想畫那麼多那麼多的圖，但還是先發出之前所說的警告 (☆▽☆)
我們假設在如下樹中模拟 Tarjan 過程（節點數量少一點可以畫更少的圖o(￣▽￣)o）
存在查詢：
LCA(T,3,4)、LCA(T,4,6)、LCA(T,2,1)
。
注意：每個節點的顔色代表它目前屬于哪一個集合，橙色線條為搜尋路徑，黑色線條為合并路徑。
目前所在位置為
u = 1
，未周遊孩子集合
v = {2,5}
，向下周遊。
目前所在位置為
u = 2
，未周遊孩子集合
v = {3,4}
，向下周遊。
目前所在位置為
u = 3
，未周遊孩子集合
v = {}
，遞歸到達最底層，周遊所有相關查詢發現存在
LCA(T,3,4)
，但是節點
4
此時标記未通路，是以什麼也不做，該層遞歸結束。
遞歸傳回，目前所在位置
u = 2
，合并節點
3
到
u
所在集合，标記
vis[3] = true
，此時未周遊孩子集合
v = {4}
，向下周遊。
目前所在位置
u = 4
，未周遊孩子集合
v = {}
，周遊所有相關查詢發現存在
LCA(T,3,4)
，且
vis[3] = true
，此時得到該查詢的解為節點
3
所在集合的首領，即
LCA(T,3,4) = 2
；又發現存在相關查詢
LCA(T,4,6)
，但是節點
6
此時标記未通路，是以什麼也不做。該層遞歸結束。
遞歸傳回，目前所在位置
u = 2
，合并節點
4
到
u
所在集合，标記
vis[4] = true
，未周遊孩子集合
v = {}
，周遊相關查詢發現存在
LCA(T,2,1)
，但是節點
1
此時标記未通路，是以什麼也不做，該層遞歸結束。
遞歸傳回，目前所在位置
u = 1
，合并節點
2
到
u
所在集合，标記
vis[2] = true
，未周遊孩子集合
v = {5}
，繼續向下周遊。
目前所在位置
u = 5
，未周遊孩子集合
v = {6}
，繼續向下周遊。
目前所在位置
u = 6
，未周遊孩子集合
v = {}
，周遊相關查詢發現存在
LCA(T,4,6)
，且
vis[4] = true
，是以得到該查詢的解為節點
4
所在集合的首領，即
LCA(T,4,6) = 1
，該層遞歸結束。
遞歸傳回，目前所在位置
u = 5
，合并節點
6
到
u
所在集合，并标記
vis[6] = true
，未周遊孩子集合
v = {}
，無相關查詢是以該層遞歸結束。
遞歸傳回，目前所在位置
u = 1
，合并節點
5
到
u
所在集合，并标記
vis[5] = true
，未周遊孩子集合
v = {}
，周遊相關查詢發現存在
LCA(T,2,1)
，此時該查詢的解便是節點
2
所在集合的首領，即
LCA(T,2,1) = 1
，遞歸結束。
至此整個 Tarjan 算法便結束啦~
PS：不要在意最終根節點的顔色和其他節點顔色有一點點小小差距，可能是千千在染色的時候沒仔細看，總之就這樣咯~
PPS：所謂的首領就是、就是首領啦~
倍增算法
哇！還有一個倍增算法以後繼續補充吧！
總結篇
對于不同的 LCA 問題我們可以選擇不同的算法。
假若一棵樹存在動态更新，此時離線算法就顯得有點力不從心了，但是在其他情況下，離線算法往往效率更高（雖然不能保證得到解的順序與輸入一緻，不過我們有 sort 呀）
總之，喜歡哪種風格的
code
是我們自己的意願咯~
另外， LCA 和 RMQ 問題是兩個非常基礎的問題，很多複雜問題都可以轉化為這兩類問題來解決。（當然這兩類問題之間也可以互相轉化啦~）
轉載自：『圖論』LCA 最近公共祖先