在理解倍增方法前，先试着去搞懂逐步移动的LCA。逐步移动的方法，其实就是把深度较深的节点向着父节点方向移动，直至与另外一个节点深度相同。再将两节点同时向父节点方向移动，直至两节点相遇为止。预处理过程就是一个DFS，求出每个节点的深度。对于每一次查询，用逐步移动的方法求得LCA。如果节点数为N，树的高度为L，则预处理时间O(N)，每一次查询的总时间最坏情况为O(L)。最坏情况下树排成一条链，即L=N，则在有Q次查询时查询总时间为O(QN)。通常N比较大，虽然它通常不能做到100%正确，但是在非极端数据下表现良好。
#include<iostream> using namespace std; struct TREE { int pre; int to; }tree[500010]; int edge_sum,head[500010]; int N,M,S,parent[500010],depth[500010]; void add_edge(int from,int to) { edge_sum++; tree[edge_sum].pre=head[from]; tree[edge_sum].to=to; head[from]=edge_sum; } void dfs(int dep,int cur,int fa) { depth[cur]=dep; parent[cur]=fa; for(int i=head[cur];i!=0;i=tree[i].pre) { int u=tree[i].to; if(u!=fa)dfs(dep+1,u,cur); } } int LCA(int u,int v) { if(depth[u]<depth[v])swap(u,v); while(depth[u]>depth[v])u=parent[u]; if(u==v)return u; while(u!=v)u=parent[u],v=parent[v]; return u; } int main() { cin>>N>>M>>S; for(int i=1;i<=N-1;i++) { int u,v; cin>>u>>v; add_edge(u,v); add_edge(v,u); } dfs(1,S,-1); for(int i=1;i<=M;i++) { int u,v; cin>>u>>v; cout<<LCA(u,v)<<endl; } return 0; }
搞明白了逐步移动的LCA，就可以做倍增方法的了。倍增方法的成立依赖于这个定理：任意一个正整数都可以表示成若干个不同的2的幂次之和。这其实不难理解，因为任意一个正整数肯定都可以用二进制来表示。定义数组parent[MAXN][MAX_LOG]，其中parent[k][v]表示k的2v倍祖先。如果节点不存在就置为0。大致思路和逐步移动相似，只是用二次幂的移动来代替一步一步的移动。设有Q次询问和N个节点，预处理O(Nlog2N), 查询总时间O(Qlog2N)，整个程序的时间复杂度总和为O((N+Q)log2N)，可以通过全部的数据。
#include<cmath> #include<stack> #include<cstdio> #include<string> #include<iostream> using namespace std; struct TREE { int pre; int to; }tree[1000010]; int edge_sum,head[500010]; int N,M,S,U,V,parent[500010][20],depth[500010]; void add_edge(int from,int to) { edge_sum++; tree[edge_sum].pre=head[from]; tree[edge_sum].to=to; head[from]=edge_sum; } void dfs(int dep,int cur,int fa) { depth[cur]=dep; parent[cur][0]=fa; for(int i=head[cur];i!=0;i=tree[i].pre) { int u=tree[i].to; if(u!=fa)dfs(dep+1,u,cur); } } int query_LCA(int u,int v) { if(u==S||v==S)return S; if(depth[u]<depth[v])swap(u,v); int num=depth[u]-depth[v]; for(int k=0;(1<<k)<=num;k++) if((1<<k)&num)u=parent[u][k]; if(u==v)return u; for(int k=log(N)/log(2)-1;k>=0;k--) if(parent[u][k]!=parent[v][k]) u=parent[u][k],v=parent[v][k]; return parent[u][0]; } int main() { scanf("%d %d %d",&N,&M,&S); for(int i=1;i<=N-1;i++) { scanf("%d %d",&U,&V); add_edge(U,V); add_edge(V,U); } dfs(1,S,S); for(int k=1;(1<<k)<=N;k++) for(int v=1;v<=N;v++) parent[v][k]=parent[parent[v][k-1]][k-1]; for(int i=1;i<=M;i++) { scanf("%d %d",&U,&V); printf("%d\n",query_LCA(U,V)); } return 0; }
原文：https://www.cnblogs.com/Mr-Kyle/p/12939302.html