本文主要是介绍倍增法求lca(最近公共祖先)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：
大致上算法的思路是这样发展来的。
想到求两个结点的最小公共祖先，我们可以先把两个的深度提到同一水平，在一步一步往上跳，直到两个结点有了一个公共祖先，依照算法流程，这就是least common ancestor。
但是如果这样一步步地往上未免太让人着急，为了提高一下效率，便不再每次只跳一步，而跳2i
步。一般的，先这样蹦蹦跳跳跳上去直到两个结点相平，在两个一起这样蹦上去。
怎么确定这个i该是多少合适呢？
这里我们需要预处理一个数组f，f[u] [i]来表示结点u的第i代祖先，f[u] [0]表示结点u的父亲，这个数组用链式前向星（最近怎么老是它）加上dfs来预处理产生，十分便捷。那它有什么用呢？用在提升结点的时候，我们可以借助这个数组直接将结点提到他的合适的祖先上去。怎么才算合适的祖先？现假设求lca(s,t)
分两步，第一步是将低结点提到高结点（相对于叶节点）的深度上。这时候一个for循环从s的第20代祖先开始（为什么是二十代？可能一般的树达不到这个深度）,看能不能把s提上去后满足depth[s]>=depth[t]
，不能满足就看第十九代祖先这样一直减少i，若满足了就把s提上去，还是继续减少i，直到两个结点最终相平。这个过程有个博客里讲的很形象（见参考文章），比喻成乌鸦喝水的过程，就是乌鸦先把体积大的（这里就是i值）放进水杯里，再逐渐减小放入物品的体积直到把水杯的水升上来，而不是先填沙子这种小颗粒的东西。这就是为什么i值要从大到小。
第二步是整体提升的过程，我们不知道该几步提升，在循环中的条件就变成了if(f[s][i]!=f[t][i])
。也就是只要他两的祖先不一样就提升，祖先一样有两种可能，一种可能是节点是祖先但不是最小公共祖先，另一种可能是到了公共祖先。前一种出现在循环的开始，一开始想要提的深度比较多，所以很可能提到了公共祖先。这种情况不用管，继续减小i值，之后可能会由于满足if条件而经历一些两点提升的过程，最后不满足if
条件了，说明两个已经有了最小公共祖先，这时候随意输出一个节点的父结点就行了。
算法完成，看看代码。如觉得不太清楚请看参考文章。
代码：
#include <iostream>
#include <cstdio>
#define max_n 500005
using namespace std;
int n,m,s;//n为结点数，m为边数,s为根节点标号
int lg[max_n];//优化用到的预处理的数组，存log_2[i]-1
int f[max_n][23];//f[u][i]表示结点u的第i代祖先，其中f[u][0]为u的父结点
int depth[max_n];//节点深度
//链式前向星
int head[max_n];
struct edge
{int v;int next;
}e[max_n<<1];
int cnt = 0;
void add(int u,int v)
{++cnt;e[cnt].v = v;e[cnt].next = head[u];head[u] = cnt;
}
//快速读入模板
inline void read(int& x)
{x=0;int f=0;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f = 1;ch = getchar();}while('0'<=ch&&ch<='9') {x = 10*x+ch-'0';ch=getchar();}x = f?-x:x;
}
//dfs预处理出结点往上跳2^i的结点
void dfs(int u,int from)
{depth[u] = depth[from]+1;//比父结点深度加一for(int i = 1;1<<i<=depth[u];i++)//祖先结点要存在，不存在的默认为零{f[u][i] = f[f[u][i-1]][i-1];//f[u][i]的第u个结点第i-1代祖先的第i-1代祖先记为第i代祖先}for(int i = head[u];i;i=e[i].next){int v = e[i].v;if(v==from) continue;//因为是无向边，判断不能反回父结点f[v][0] = u;//dfs(v,u);}
}
//求最近公共祖先
int lca(int s,int t)
{if(depth[s]<depth[t]) swap(s,t);//设s比t深while(depth[s]>depth[t])//若s比t深，不断上移s{s = f[s][lg[depth[s]-depth[t]]-1];//上移log_2[深度差]步，直到相平}if(s==t)//若t为s的祖先{return s;//则s,t的lca是t}for(int i = lg[depth[s]]-1;i>=0;i--)//待s,t相平后{if(f[s][i]!=f[t][i])//只要两公共祖先不等{s = f[s][i];//将二者上移t = f[t][i];}}/*for(int i = 20;i>=0;i--){if(f[s][i]!=f[t][i]){s = f[s][i];t = f[t][i];}}*/return f[s][0];//直到最后两者公共祖先相等，记为lca
}
int main()
{read(n);read(m);read(s);for(int i = 1;i<=n;i++)//优化数组玄学构造法求log_2[i]+1{lg[i] = lg[i-1]+((1<<lg[i-1])==i);}for(int i = 1;i<n;i++){int u,v;read(u);read(v);add(u,v);add(v,u);}dfs(s,0);int ans = 0;for(int i = 1;i<=m;i++){int a,b;read(a);read(b);ans = lca(a,b);cout << ans << endl;}return 0;
}
这篇关于倍增法求lca(最近公共祖先)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
