LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科 列如： 在这棵树中 17 和 8 的LCA就是 3， 9 和 7的LCA就是 7 。明白了LCA后，就下来我们就要探讨探讨LCA怎么求了 qwq
暴力算法以 17 和 18 为例，既然要求LCA，那么我们就让他们一个一个向上爬(我要一步一步往上爬 —— 《蜗牛》 )，直到相遇为止。第一次相遇即是他们的LCA。 模拟一下就是： 17->14->10->7->3 18->16->12->8->5->3 最终结果就是 3 当然这个算法妥妥的会T飞掉，那么我们就要进行优化，于是就有了用倍增来加速的倍增LCA，这也是我们今天介绍的重点。
倍增算法 顾名思义，就是依次按2的倍数1，2，4，8，~~~~，不过在这我们是按照从大往小跳，即按32，16，8，4，2，1来跳，这可以拿二进制为例，10(1010)，从高位向低位填很简单，如果填了这位之后比原数大了，那我就不填，这个过程是很好操作的。 这个算法的时间复杂度为O(nlogn),已经可以满足大部分的需求。想要实现这个算法，首先我们要记录各个点的深度和他们2^i 级的的祖先，用数组depth表示每个节点的深度，fa[i][j]表示节点ii的2^i 级祖先。 代码如下： void dfs(int f,int fath) //f表示当前节点，fath表示它的父亲节点 { depth[f]=depth[fath]+1; fa[f][0]=fath; for(int i=1;(1<<i)<=depth[f];i++) fa[f][i]=fa[fa[f][i-1]][i-1]; //这个转移可以说是算法的核心之一 //意思是f的2^i祖先等于f的2^(i-1)祖先的2^(i-1)祖先 //2^i=2^(i-1)+2^(i-1) for(int i=head[f];i;i=e[i].nex) if(e[i].t!=fath) dfs(e[i].t,f); }预处理完毕后，我们就可以去找它的LCA了，为了让它跑得快一些，我们可以加一个常数优化(来自洛谷提高组讲义)
for(int i=1;i<=n;i++) //预先算出log_2(i)+1的值，用的时候直接调用就可以了 lg[i]=lg[i-1]+(1<<lg[i-1]==i); //看不懂的可以手推一下接下来就是倍增LCA了，我们先把两个点提到同一高度，再统一开始跳。
但我们在跳的时候不能直接跳到它们的LCA，因为这可能会误判，比如4和8，在跳的时候，我们可能会认为1是它们的LCA，但1只是它们的祖先，它们的LCA其实是3。所以我们要跳到它们LCA的下面一层，比如4和8，我们就跳到4和5，然后输出它们的父节点，这样就不会误判了。
int lca(int x,int y) { if(depth[x]<depth[y]) //用数学语言来说就是：不妨设x的深度 >= y的深度 swap(x,y); while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]-1]; //先跳到同一深度 if(x==y) //如果x是y的祖先，那他们的LCA肯定就是x了 return x; for(int k=lg[depth[x]]-1;k>=0;k--) //不断向上跳（lg就是之前说的常数优化） if(fa[x][k]!=fa[y][k]) //因为我们要跳到它们LCA的下面一层，所以它们肯定不相等，如果不相等就跳过去。 x=fa[x][k], y=fa[y][k]; return fa[x][0]; //返回父节点 }完整的求17和18的LCA的路径： 17->10->7->3 18->16->8->5->3 解释：首先，18要跳到和17深度相同，然后18和17一起向上跳，一直跳到LCA的下一层(17是7，18是5)，此时LCA就是它们的父亲 总体来说就是这样了，也不知道我这个蒟蒻讲的各位dalao能不能看明白 orz 完整模板代码：
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int maxn=500000+2; int n,m,s; int k=0; int head[maxn],d[maxn],p[maxn][21];//head数组就是链接表标配了吧？d存的是深度（deep）,p[i][j]存的[i]向上走2的j次方那么长的路径 struct node{ int v,next; }e[maxn*2];//存树 void add(int u,int v) { e[k].v=v; e[k].next=head[u]; head[u]=k++; } //加边函数 void dfs(int u,int fa) { d[u]=d[fa]+1; p[u][0]=fa; for(int i=1;(1<<i)<=d[u];i++) p[u][i]=p[p[u][i-1]][i-1]; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].v; if(v!=fa) dfs(v,u); } } //首先进行的预处理，将所有点的deep和p的初始值dfs出来 int lca(int a,int b) //非常标准的lca查找 { if(d[a]>d[b]) swap(a,b); //保证a是在b结点上方，即a的深度小于b的深度 for(int i=20;i>=0;i--) if(d[a]<=d[b]-(1<<i)) b=p[b][i]; //先把b移到和a同一个深度 if(a==b) return a; //特判，如果b上来和就和a一样了，那就可以直接返回答案了 for(int i=20;i>=0;i--) { if(p[a][i]==p[b][i]) continue; else a=p[a][i],b=p[b][i]; //A和B一起上移 } return p[a][0]; 找出最后a值的数字 } int main() { memset(head,-1,sizeof(head)); int a,b; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<n;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); //无向图，要加两次 } dfs(s,0); for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); printf("%d\n",lca(a,b)); } return 0; }