最近公共祖先是樹上的概念，不瞭解樹的出門左轉百度：樹（資料結構名詞）_百度百科
假設我們需要求 x 和 y 的最近公共祖先，這裡有多種等價的定義
路徑x到y上深度最小的點
x和y公共祖先中深度最大的點
x和y在這棵樹上距離最近的公共祖先結點
如果
x就是y的祖先，則x本身就是兩者的最近公共祖先
通常來說有四種
樹上倍增
dfs序與ST表
樹鏈剖分
Tarjan (離線演演算法)
這裡我們只討論前三種線上演演算法
倍增的思想可以看一下這篇文章：演演算法學習筆記(3): 倍增與ST演演算法
這是基於樸素方法的優化，所以在講樹上倍增之前我們還需要講一下樸素的方法
選擇x和y中深度較大的點，向上跳直到兩者深度相同，然後兩者同時向上跳直到兩者第一次相遇，此時兩者所在即是最近公共祖先
顯然，我們每次只跳一個顯然不優，所以借鑑倍增與二進位制拆分的思想
令fa[x][k]指從x開始，向上跳2^k次所能達到的祖先，特別的，如果深度不夠，則fa[x][k] = 0
那麼，基於樸素演演算法的流程：我們只需要跳的時候利用倍增的思想就行了
這裡給出一種參考程式碼：
notice: 這其實不是一種特別好的寫法
int lca(int x, int y) {
int p;
// 這裡保證了x是深度相對較大那一個
if (dep[x] < dep[y]) p = x, x = y, y = p;
// 將x跳到與y深度相同的位置
p = 0;
while (p >= 0) {
if (dep[fa[x][p]] >= dep[y]) x = fa[x][p], ++p;
else --p;
}
// 達到同樣深度就已經相遇（y是x的祖先）
if (x == y) return x;
// 兩者同時向上跳直到相遇
p = 0;
while (p >= 0) {
if (fa[x][p] != fa[y][p]) x = fa[x][p], y = fa[y][p], ++p;
else --p;
}
// 最後還要向上跳一個才是公共祖先
// 通過這種倍增寫法得出的位置是最後一個滿足if條件的位置！！！
return fa[x][0];
}
那麼問題來了，如何初始化？
顯而易見，跳2^k步相當於跳2次2^(k-1)步，所以有了
fa[x][i] = fa[fa[x][i - 1]][i - 1];
在初始化的時候每一個點都需要O(logN)，那麼總初始化需要O(NlogN)
在詢問時，令k為x, y到最近公共祖先的最大距離，根據倍增演演算法，則複雜度為O(logk)，當樹退化成一條鏈時，k最大取到n，那麼最終複雜度應該為O(logN)
綜上，初始化需要O(NlogN)，單次詢問需要O(logN)
這種方法相對難以理解，所以讀者可以在掌握了一般的Tarjan縮點演演算法後再理解（這兩個演演算法幾乎沒有關係，但是一些思想在Tarjan中有所體現)
下文中不是特別明白名詞在後文中有所提及，或者可以參考講解Tarjan演演算法的文章
先求出樹每一個結點的dfn，不妨令x比y更先遍歷到（dfn[x] < dfn[y]）
x不是y的祖先在
dfs序列中，區間[dfn[x], dfn[y]]內一定包含了LCA子樹的部分，但不包含LCA及其祖先，並且該區間一定包含了LCA到y路徑上的第一個兒子，而且它的深度是最小的
所以，我們只需要找到區間[dfn[x], dfn[y]]中深度最小的點，它的父結點就是LCA
x是y的祖先，則x就是LCA，且x是區間[dfn[x], dfn[y]]中深度最小的點，與上述情況不太一樣，那麼考慮我們將x排除在區間外，則在區間[dfn[x] + 1, dfn[y]]中深度最小的點的父親結點就是x。返回考慮第一種情況，由於第一種情況x一定不是LCA，那麼將區間替換為[dfn[x] + 1, dfn[y]]不影響答案。綜上，我們只需要求區間[dfn[x] + 1, dfn[y]] 中深度最小的點的父結點即可。
定義rdfn滿足x == rdfn[dfn[x]]，ST表初始化時f[i][0] = rdfn[i]。
其實可以只需要
dfn就ok，f[dfn[i]][0] = i
定義區間操作
int Min(int x, int y) {
return depth[x] < depth[y] ? x : y;
}
定義查詢操作
int query(int x, int y) {
if (x == y) return x; // 同一個結點啊
// 確保x是先遍歷到的那一個結點
if (dfn[x] > dfn[y]) std::swap(x, y);
int k = log(dfn[y] - dfn[x]);
return Min(f[dfn[x] + 1][k], f[dfn[y] - (1<<k) + 1][k]);
}
其餘的就套模板就行了
初始化其實主要是ST表的初始化，所以初始化的複雜度為O(NlogN)（實際上應該是O(N + NlogN）
查詢也是ST表的區間查詢，複雜度為O(1)
好高階的名字……
樹鏈剖分指將一棵樹分割為若干條鏈，以維護樹上資訊。它包含重鏈剖分、長鏈剖分、實鏈剖分，在沒有特殊說明的情況下，樹鏈剖分一般指代重鏈剖分。這裡也著重描述重鏈剖分。
這裡先給出一些
dfs序指dfs的順序。具體方法是用一個計數變數cnt，遍歷到結點x時，時間戳
dfn[x] = ++cnt，對應dfs序列中第cnt個就是x而上文定義中的
rdfn則可以在同時通過rdfn[cnt] = x記錄下來
結點的dfn大於其任意父結點
對於任意結點（包含本身）的子樹中，存在一個dfn是連續的一條鏈
如果子樹在dfs序列中是連續的一段，在維護子樹（子樹求和之類的子樹操作）時，直接把它看做一個序列，那麼就和線上段樹上操作沒有區別了
相鄰重邊連結形成的鏈
重子結點（如果有）與其父結點相連的邊
一個結點的子結點中度最大的結點（孩子個數最多的點）
重鏈剖分就是將每一條重鏈單獨劃分出來，從而通過dfn來維護鏈上資訊
至於如何剖分，需要進行兩次遍歷
第一次遍歷，獲得所有節點的siz, dep, fa, son
這裡
siz指結點的度，三個字元統一一下，fa是個例外，dep指結點的深度，fa指結點的父結點，son指結點的重子結點
第二次遍歷，獲得所有點的dfn, top
這裡
dfn無需解釋，top指結點所在重鏈最頂部的結點
思路清晰，這裡給出一種參考寫法
注意前提，點編號從
1 ~ n，且這裡用的是前向星存圖（樹）
int top[N], dfn[N], son[N], dep[N], siz[N], fa[N];
// work son, siz, dep and fa
void workSSDF(int x, int par) {
dep[x] = dep[par] + 1, fa[x] = par, siz[x] = 1;
for (int y, i = head[x]; i; i = edge[i].next) {
y = edge[i].to;
if (y == par) continue;
workSSDF(y, x);
siz[x] += siz[y];
if (siz[y] >= siz[son[x]]) son[x] = y;
}
}
// work dfn and top
int cdfn = 0;
void workDT(int x, int ptop) {
dfn[x] = ++cdfn, top[x] = ptop;
if (son[x]) workDT(son[x], top[x]);
for (int y, i = head[x]; i; i = edge[i].next) {
y = edge[i].to;
if (!dfn[y]) workDT(y, y);
}
}
這麼麻煩的求這個樹鏈剖分有啥用？
如果我們隨便畫一個圖並模擬一下上述過程……
在兩次遍歷完之後：
考慮用純markdown畫圖是真的難受，但樹的結構是一樣的……T^T
我們很容易發現，在同一條重鏈上的結點的dfn序是連續的……（這我們稍後在論述）
回到求LCA的流程，由於我們把樹分為了從上到下的一些鏈
注意每一條鏈中沒有深度相同的結點
所以，我們只需要不斷的把兩個結點通過top向上跳直到在同一條鏈上（此時top[x] == top[y]）
至於為什麼要跳top結點的深度較大的結點……還請讀者自行討論
有一個需要注意的地方，不能直接
x = top[x]，因為top[top[x]] == top[x]!!!所以還需要跳到
top[x]的父節點上
流程清晰，這裡給出一種參考程式碼
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] >= dep[top[y]]) x = fa[top[x]];
else y = fa[top[y]];
}
if (dep[x] <= dep[y]) return x;
return y;
}
太難寫了 Q^Q
依據重鏈的定義，每一條重鏈至少佔了重鏈頂端結點所在的子樹結點的\(logN\)個結點（一條鏈就佔滿了）
所以，剖分之後差不多是有\(logN\)條重鏈，所以每次詢問至多跳\(logN\)次，所以……
初始化複雜度為O(N)(兩次dfs)，查詢複雜度為O(logN)
看我的另一篇文章吧，太難寫了，四千多個字嗚啊