一、定義與定理
      LCA：Least Common Ancestors（最近公共祖先），對(duì)于一棵有根樹(shù)T的任意兩個(gè)節(jié)點(diǎn)u，v，求出LCA(T, u, v)，即離跟最遠(yuǎn)的節(jié)點(diǎn)x，使得x同時(shí)是u和v的祖先。
      在線(xiàn)算法：用比較長(zhǎng)的時(shí)間做預(yù)處理，但是等信息充足以后每次回答詢(xún)問(wèn)只需要用比較少的時(shí)間。
      離線(xiàn)算法：先把所有的詢(xún)問(wèn)讀入，然后一起把所有詢(xún)問(wèn)回答完成。
      RMQ：給出一個(gè)數(shù)組A，回答詢(xún)問(wèn)RMQ(A, i, j)，即A[i...j]之間的最值的下標(biāo)。
二、DFS+RMQ
      1）Sparse Table（ST）算法
      描述：

      分析：初始化過(guò)程實(shí)際上是一個(gè)動(dòng)態(tài)規(guī)劃的思想。易知，初始化過(guò)程效率是O(nlogn)，而查詢(xún)過(guò)程效率是O(1)。ST是一個(gè)在線(xiàn)算法。
      示例：POJ 3368 解題報(bào)告
      2）求解LCA問(wèn)題
      描述：
      （1）DFS：從樹(shù)T的根開(kāi)始，進(jìn)行深度優(yōu)先遍歷，并記錄下每次到達(dá)的頂點(diǎn)。第一個(gè)的結(jié)點(diǎn)是root(T)，每經(jīng)過(guò)一條邊都記錄它的端點(diǎn)。由于每條邊恰好經(jīng)過(guò)2次，因此一共記錄了2n-1個(gè)結(jié)點(diǎn)，用E[1, ... , 2n-1]來(lái)表示。
      （2）計(jì)算R：用R[i]表示E數(shù)組中第一個(gè)值為i的元素下標(biāo)，即如果R[u] < R[v]時(shí)，DFS訪(fǎng)問(wèn)的順序是E[R[u], R[u]+1, ..., R[v]]。雖然其中包含u的后代，但深度最小的還是u與v的公共祖先。
      （3）RMQ：當(dāng)R[u] ≥ R[v]時(shí)，LCA[T, u, v] = RMQ(L, R[v], R[u])；否則LCA[T, u, v] = RMQ(L, R[u], R[v])，計(jì)算RMQ。
      由于RMQ中使用的ST算法是在線(xiàn)算法，所以這個(gè)算法也是在線(xiàn)算法。
      示例：ZOJ 3195 解題報(bào)告。
三、Tarjan算法
      描述：Tarjan算法是一個(gè)離線(xiàn)算法，也就是說(shuō)只有先獲得所有的查詢(xún)，再按一個(gè)特定的順序進(jìn)行運(yùn)算。