????最近公共祖先（Lowest Common Ancestors, LCA），是指在有根樹中，某兩個(gè)結(jié)點(diǎn) u和 v最近的公共祖先。

????祖先是指當(dāng)前結(jié)點(diǎn)到樹根的路徑上所有的結(jié)點(diǎn)。

????u 和 v的公共祖先是指一個(gè)結(jié)點(diǎn)既是 u 的祖先，又是 v 的祖先。

????u 和 v 最近的公共祖先是指離 u 和 v 最近的公共祖先。

????如果 v 本身就是 u 的祖先則 u 和 v 最近的公共祖先就是 v ，如圖所示。

可以利用 LCA求解樹上任意兩點(diǎn)之間的距離。

????例如，求 u 和 v之間的距離，如圖所示。如果u和v的最近公共祖先為 lca,則 u 和 v之間的距離為 u 到樹根的距離加上 v到到樹根的距離，減去 2倍的 lca到樹根的距離：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? dist[u] + dist[v] -2*dist[lca]

求解 LCA的方法有很多，包括 1. 暴力搜索法， 2. 樹上倍增法， 3. 在線 RMQ算法，4. 離線 Tarjan算法，5. 樹鏈剖分法。本節(jié)只講前 4種典型算法，樹鏈剖分留到后面講解。

• ????在線算法：以序列化的方式一個(gè)個(gè)的處理輸入，也就是說在開始時(shí)并不需要已經(jīng)直到所有的輸入，在解決一個(gè)問題后立即輸出結(jié)果。
  

• ????離線算法：在開始時(shí)就需要知道問題的所有輸入數(shù)據(jù)，可以一次性回答所有的問題。
  

????除了離線Tarjan算法, 其它算法均為在線算法。

1. 暴力搜索法有兩種思路：

????第一種是向上標(biāo)記法：從 u 向上一直到根結(jié)點(diǎn)，標(biāo)記所有經(jīng)過的結(jié)點(diǎn)；如果 v已經(jīng)被標(biāo)記，則 v 結(jié)點(diǎn)即為 LCA(u,v) 。否則 v 也向上走，第一次遇到已標(biāo)記的結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)即為 LCA(u,v) 。

????第二種是同步前進(jìn)法：將 u,v中深度較深的那個(gè)結(jié)點(diǎn)向上走到和深度較淺的結(jié)點(diǎn)同一深度，然后兩個(gè)點(diǎn)一起向上走，直到走到同一結(jié)點(diǎn)，該結(jié)點(diǎn)就是 u，v 的最近公共祖先，記作 LCA(u,v) 。如果較深的結(jié)點(diǎn) u 到達(dá) v 的同一深度時(shí)，那個(gè)結(jié)點(diǎn)正好就是 v, 則 v 結(jié)點(diǎn)即為 LCA( u,v ) 。

????性能分析：

????暴力搜索法求解 LCA,兩種思路的時(shí)間復(fù)雜度最壞的情況下均為 O(n) 時(shí)間，每一次查詢需要 O(n) 時(shí)間。

2. 在樹上進(jìn)行倍增

????樹上倍增法不僅僅可以解決 LCA問題，還可以解決很多其它問題，掌握樹上倍增法的思路，是很有必要的。

????F[ i，j ] 表示 i 的 2^j 輩祖先，即 i 結(jié)點(diǎn)向根結(jié)點(diǎn)走 2^j 步到達(dá)的結(jié)點(diǎn)。

????例如，u 結(jié)點(diǎn)向上走 2^0 步，則為 u 的父親 x，F(xiàn)[u,0] = x; u 結(jié)點(diǎn)向上走 2^1 步，到達(dá) y , F[u,1] =y; 向上走 2^2步，達(dá)到 z, F[ u, 2] = z; u 結(jié)點(diǎn)向上走 2^3 步，結(jié)點(diǎn)不存在，令 F[u,3] = 0。如圖所示：

1) 采用動(dòng)態(tài)規(guī)劃的思想，先填寫二維表格

????算法代碼：

2）然后利用 ST 表，求解 LCA

????和前面暴力搜索中第二種同步向前進(jìn)法一樣，先讓深度大的結(jié)點(diǎn) y 向上走到與 x 同深度，然后 x和y 一起向上走。和暴力搜索不同的是，向上走是按照倍增思想走的，不是一步一步地向上走，因此速度比較快。

• 怎么讓深度大的結(jié)點(diǎn) y 向上走到與 x 同深度呢？

????總結(jié)：按照增量遞減地方式，到達(dá)的結(jié)點(diǎn)深度比 x 的深度小時(shí)，什么也不做；到達(dá)的結(jié)點(diǎn)深度大于等于 x 的深度時(shí)，y 上移，直到增量為 0，此時(shí) x,y 在同一深度。

????算法代碼：

• ????x 和 y 一起向上走，怎么找最近公共祖先結(jié)點(diǎn)呢？

????總結(jié)：按照增量遞減的方式，到達(dá)的結(jié)點(diǎn)相同時(shí)，什么也不做；到達(dá)的結(jié)點(diǎn)不同時(shí)，同時(shí)上移，直到增量為0，此時(shí) x,y 的父結(jié)點(diǎn)即為公共祖先結(jié)點(diǎn)。

????算法代碼：

性能分析：

3. 在線 RMQ 算法

????兩個(gè)點(diǎn)的 LCA 一定是兩個(gè)點(diǎn)之間的歐拉序列（dfs 序列）中深度最小的那個(gè)點(diǎn)，尋找深度最小值可以使用 RMQ。

????歐拉序列是指在深度遍歷過程中，把依次經(jīng)過的結(jié)點(diǎn)記錄下來，回溯時(shí)經(jīng)過的頂點(diǎn)也記錄下來，一個(gè)結(jié)點(diǎn)可能被記錄多次。相當(dāng)于從樹根開始，一筆畫出一個(gè)經(jīng)過所有點(diǎn)的回路。

????該樹的歐拉序列為 1 2 4 6 8? 6 4 2 5 7 5 2 1 3 1 ，搜索時(shí)首先得到 6 和 5 的存儲(chǔ)下標(biāo) i, j ,然后查詢?cè)搮^(qū)間深度最小的結(jié)點(diǎn)，即為 6和5號(hào)結(jié)點(diǎn)的最近公共祖先。

性能分析：

4. 離線 Tarjan 算法

????這里的 Tarjan 算法是用于解決 LCA 問題的離線算法，你可能還會(huì)見到其他的 Tarjan算法，例如求連通分量的Tarjan算法。

????在線算法是指每讀入一個(gè)查詢（求一次LCA叫做一次查詢），運(yùn)行一次程序得到本次查詢答案，如果一次查詢需要 O(log n)時(shí)間，m 次查詢需要 O(mlogn); 離線算法是指首先讀入所有的詢問，然后運(yùn)行一次程序得到所有查詢答案。 Tarjan 算法利用并查集優(yōu)越的時(shí)空復(fù)雜度，可以實(shí)現(xiàn) LCA問題的線性處理時(shí)間 O(n+m)。

Tarjan 算法步驟：