一.倍增算法的前期铺垫
我们记节点v到根的深度为depth(v)。那么如果节点w是节点u和节点v的最近公共祖先的话，让u往上走(depth(u)-depth(w))步，让v往上走(depth(v)-depth(w))步，都将走到节点w。因此，我们首先让u和v中较深的一个往上走|depth(u)-depth(v)|步，再一起一步步往上走，直到走到同一个节点，就可以在O(depth(u)+depth(v))的时间内求出LCA。
由于节点的最大深度为n，所以这个方法在最坏的情况下一次查询时间复杂度就要O(n)，这显然是不够的。于是我们开始考虑优化。
二.倍增算法的实现过程
分析刚才的算法，两个节点到达同一节点后，不论怎么向上走，达到的显然还是同一节点。利用这一点，我们就能够利用二分搜索求出到达最近公共祖先的最小步数了。
首先我们要进行预处理。对于任意的节点，可以通过fa2[v]=fa[fa[v]]得到其向上走2步到达的顶点，再利用这个信息，又可以通过fa4[v]=fa2[fa2[v]]得到其向上走4步所到的顶点。以此类推，我们可以得到其向上走2^k步所到的顶点fa[v][k],预处理的时间点复杂度为O(nlogn)。
有了k=floor(logn)以内的所有信息后，就可以进行二分所搜的，每次查询的时间复杂度为O(logn)。
以poj1330为例
#include<iostream> #include<cstdio> #include<vector> #include<cmath> #include<cstring> using namespace std; vector<int>v[10010]; int fa[10010][100];//fa[i][j]表示从i节点走2^j步可以达到的祖先节点 int depth[10010];//记录每个节点的深度 int n; void dfs(int u,int pre,int dep) { fa[u][0]=pre; depth[u]=dep; for(int i=0;i<v[u].size();i++) { int p=v[u][i]; dfs(p,u,dep+1); } } void init(int root) { dfs(root,-1,0); for(int j=0;(1<<(j+1))<=n;j++) { for(int i=1;i<=n;i++) { if(fa[i][j]<0) fa[i][j+1]=-1; else fa[i][j+1]=fa[fa[i][j]][j]; } } } int LCA(int u,int v) { if(depth[u]>depth[v]) swap(u,v); int temp=depth[v]-depth[u]; //cout<<temp<<endl; for(int i=0;(1<<i)<=temp;i++) { if((1<<i)&temp) { v=fa[v][i]; //cout<<v<<endl; } } if(v==u) return u; for(int i=int(log(n*1.0));i>=0;i--) { if(fa[u][i]!=fa[v][i]) { u=fa[u][i]; v=fa[v][i]; } } return fa[u][0]; } int main() { int T,k,x,y; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) v[i].clear(); memset(fa,0,sizeof(fa)); for(int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); v[x].push_back(y); fa[y][0]=x; } for(int i=1;i<=n;i++) { if(fa[i][0]==0) { k=i; break; } } //cout<<k<<endl; init(k); scanf("%d%d",&x,&y); printf("%d ",LCA(x,y)); } }