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