這幾天，提高B組總是有求LCA的題。由于我是蒟蒻，是以老是做不出來，直接上暴力。現在才弄懂。
沒耐心看前面部分的大神門可以直接看後面。
ST（RMQ）算法（線上）求LCA
LCA是什麼？
在一棵樹上，兩個節點的最近公共祖先就是LCA。
求LCA有什麼用？
我見到最多的是，在一些題目中，我們需要找出樹上兩個點之間的路徑，其中就要借助LCA，作為一個中轉點。
舉個例子：
我們要找出兩個紅色的點之間的路徑。
黃色的這條路就是我們要求的。
怎麼找？
暴力方法1
BFS或DFS周遊一遍。時間複雜度顯然是O(N)的。
但我們要記住，這不是圖，而是一棵樹！
這是一棵樹，是以每兩個點之間一定有一個中轉點（可能是它們本身）！
這個中轉點就是它們的最近公共祖先。（圖中綠色的那個點）
兩個點之間的路徑顯然。
怎麼求LCA？
暴力方法2
先dfsO(N)記錄它的父親。
兩端同時暴力往上跳，每到一個點就打一個标記，跳到打過标記的點時退出，這個點就是LCA。
但速度較慢。設兩個點為x和y，深度為deep[x]和deep[y]。那麼将最多會有abs(deep[x]-deep[y])個沒有用的點被搜到（比如這個圖的第5步實際上是沒用的）。那麼，我們能不能不搜到這些沒用的點？
當然可以！
暴力方法3
首先用dfsO(N)預處理出每個點的深度（它們的父親也可以同時處理）。
先挑一個比較深的點，往上跳到與另一個點深度相同的位置。然後兩邊同時往上面暴力，相遇的點即答案。
然而還是過不了。看看例題（LCA模闆題）。這種方法隻有70分。因為每次都要搜一遍，很慢。
如果資料出了一條鍊來卡，就跑得超慢。
這也不行，那怎麼辦？（讀者：說了這麼久還是在将暴力，你幾個意思啊？）
倍增求LCA
求LCA有幾種方法，在網上我見到了tarjan（離線），RMQ轉LCA，還有樹鍊剖分。我介紹一個方法，叫倍增。
設f[i][j]表示點i往上的第2^j個祖先。
首先我們用dfsO(NlgN)求出f數組。式子：f[i][j]=f[f[i][j-1]][j-1]。不解釋。
然後我們就可以優美地倍增啦！首先，原來的套路，将兩個點跳到同一深度（跳到同一深度的過程也是幾個幾個跳）。然後将j從大到小枚舉，若f[x][j]!=f[y][j]，則跳過去。否則就别跳，不然可能會跳過LCA。
最終的答案為f[x][0]（f[y][0]一樣）。因為在這種限制下，不可能出現x==y的情況，除它們在同一條鍊上，如下圖
這種情況可以特判。因為你在統一它們的深度後，它們就已經重合了。
時間複雜度：O(NlgN+QlgN)
空間複雜度：O(NlgN)
NlgN為dfs預處理的時間，Q是詢問次數。
代碼實作
例題 P3379【模闆】最近公共祖先（LCA）
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m,s;
struct EDGE
{
int x,y;
EDGE* las;
} e[];//前向星存邊
int ne;
EDGE* last[];
int f[][];
int deep[];
void make_tree(int,int,int);
int main()
{
scanf("%d%d%d",&n,&m,&s);
int i,x,y;
for (i=;i<n;++i)
{
scanf("%d%d",&x,&y);
e[++ne]={x,y,last[x]};
last[x]=e+ne;
e[++ne]={y,x,last[y]};
last[y]=e+ne;
}
make_tree(s,,);
int j,k,tx,ty;
for (i=;i<=m;++i)
{
scanf("%d%d",&x,&y);
if (deep[x]<deep[y])
swap(x,y);//確定x為深度較大的那個點
k=deep[x]-deep[y];
j=;
while (k)
{
if ((k&))
x=f[x][j];
k>>=;
++j;
}//這段代碼起了将兩點的深度統一的作用。不知道這樣打的原因的同學可以想想快速幂。當然也可以向下面那樣打for。兩種都可以。
if (x==y)
{
printf("%d\n",x);
continue;
}
for (j=int(log2(deep[x]));j>=;--j)//若這裡像上面那樣打while會錯。原因不解釋。
if (f[x][j]!=f[y][j])
{
x=f[x][j];
y=f[y][j];
}
printf("%d\n",f[x][]);
}
}
void make_tree(int t,int fa,int de)
{
f[t][]=fa;
int i,j;
for (i=,j=;j<=de;++i,j<<=)
f[t][i]=f[f[t][i-]][i-];//處理處f數組
deep[t]=de;
EDGE* ei;
for (ei=last[t];ei;ei=ei->las)
if (ei->y!=fa)
make_tree(ei->y,t,de+);
}