目錄
一、引例
1、樹-結(jié)點(diǎn)間最短距離
二、LCA（最近公共祖先）
1、樸素算法
2、步進(jìn)法
3、記憶化步進(jìn)法
4、tarjan算法
5、doubly算法
三、并查集
1、"并"和"查"
2、樸素算法
3、森林實(shí)現(xiàn)
4、啟發(fā)式合并
5、路徑壓縮
6、元素刪除
四、RMQ
1、樸素算法
2、線段樹（簡介）
3、ST算法
五、最近公共祖先相關(guān)題集整理
一、引例
1、樹-結(jié)點(diǎn)間最短距離
【例題1】給定一棵n(n <= 100000)個結(jié)點(diǎn)的樹，以及m(m <= 100000)條詢問(u, v),對于每條詢問，求u和v的最短距離？
我們知道，一個普通的無向圖求兩點(diǎn)間最短距離可以采用單源最短路，將時間復(fù)雜度大致控制在O(nlogn)，但是當(dāng)詢問足夠多的時候，這并不是一個高效的算法。從樹的性質(zhì)可知，樹上任意兩點(diǎn)間有且僅有一條簡單路徑（路徑上沒有重點(diǎn)和重邊），所以樹上任意兩點(diǎn)間的最短距離其實(shí)就是這條簡單路徑的長度。如圖一-1-1所示，要求u到v的距離，我們需要知道紅色路徑A(u->r），藍(lán)色路徑B(v->r)，紅藍(lán)公共路徑C(a->r)，那么u->v的路徑顯然就可以通過A、B、C三者的長度計(jì)算出來，令dist[x]表示從x到樹根r的簡單路徑的長度，則u到v的距離可以表示成如下：dist[u] + dist[v] - 2*dist[a]。 那么問題來了，a是什么，我們來看a->r路徑上的所有結(jié)點(diǎn)既是u的祖先，也是v的祖先，所以我們給它們一個定義稱為公共祖先（Common Ancestors），而a作為深度最深的祖先，或者說離u和v最近的，我們稱它為最近公共祖先（Lowest Common Ancestors），簡稱LCA。
圖一-1-1
二、LCA（最近公共祖先）
1、樸素算法
于是求樹上兩點(diǎn)間的距離轉(zhuǎn)化成了求兩個結(jié)點(diǎn)的最近公共祖先問題上來了，最容易想到的辦法是將u->r和v->r的兩條路徑通過遞歸生成出來，并且逆序保存，然后比較兩條路徑的公共前綴路徑，顯然公共前綴路徑的尾結(jié)點(diǎn)就是u和v的最近公共祖先，但是這個算法在樹退化成鏈的時候達(dá)到最壞復(fù)雜度O(n)，并不可行。
2、步進(jìn)法
對于兩個結(jié)點(diǎn)u和v，假設(shè)它們的最近公共祖先為lca(u, v)，用depth[x]表示x這個結(jié)點(diǎn)的深度，pre[x]表示x的父結(jié)點(diǎn)。那么很顯然，有depth[ lca(u, v) ] <= min{depth[u], depth[v]}，通過這樣一個性質(zhì)，我們可以很容易得出一個算法：
1) 當(dāng)depth[u] < depth[v]時，lca(u, v) = lca(u, pre[v]);