本文主要是介绍最近公共祖先结点--LCA（倍增法，言简意赅），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
朴素求法
倍增法
首先我们来想想朴素做法是怎样的。
朴素求法
求两结点的最近公共祖先朴素步骤：
一、先将两结点置于树的同一深度/高度。
（处在下面的结点一步一步往上走，直到与另一个结点处于共同深度）
二、两结点同时向上走，直到遇见同一个结点，则该结点为最近公共祖先。
#include<bits/stdc++.h>
using namespace std;
const int N=100005;int dep[N];//结点的深度
int f[N];//结点的父节点//计算a，b的最近公共祖先
int lca(int a,int b){if(dep[a]<dep[b])swap(a,b);//a点向上爬，直到与b的深度相等while(dep[a]!=dep[b])a=f[a];//两结点一起向上爬，直到父节点为同一个结点while(f[a]!=f[b])a=f[a],b=f[b];//父节点即为最近公共祖先结点return f[a];
}
时间复杂度为：O(n)。
可以发现如果树的深度非常大的话，每次求两结点的lca最差的情况需要把整棵树都重新遍历一遍。这样速度太慢了。
于是有了倍增算法。
倍增法
时间复杂度：O(logn)
反正终点是确定的，为什么我们一次只向上走一个结点呢？能不能一次多走几个结点？
怎么走算多？一次走2^k步算不算多？（有点像二进制优化，一个数肯定可以化成若干个2^k之和，这样我们只需要最多logn步就能到达终点了）
那你怎么知道我走了2^k步后我飘到哪去了？
这个简单，我们只需要预处理出该节点走2^k步后的祖先结点就知道你飘到哪个祖先那去了。
预处理祖先结点。
我们用f[u][k]表示u结点的走2^k步后到达的结点。
于是f[u][0]也就是u走2^0，也就是走一步，也就是到达了u的父节点。于是f[u][0]等于他的父节点。
f[u][1]也就是u走2^1步，也就是走两步，可以看做是先走2^0步到达了u的父结点，然后再走2^0步到达了父节点的父节点。
f[u][i]也就是u走2^i步，我们可以看作是先走2^(i-1)步到达f[u][i-1]结点，然后再走2^(i-1)步。
这样我们就得到了祖先结点的递推公式：
f[u][i]=f[ f[u][i-1] ][i-1];
vector<int>son[N];
int deep[N];
int f[N][30];//f[i][j]记录i结点的第2^j个祖先结点。//预处理结点深度，祖先节点。
void dfs(int u,int p){//当前结点，父节点deep[u]=deep[p]+1;f[u][0]=p;for(int i=1;(1<<i)<=deep[u];i++){f[u][i]=f[f[u][i-1]][i-1];}for(auto it:son[u]){if(it!=p){dfs(it,u);}}
}
//计算x，y的lca
int lca(int a, int b) {if (dep[a] < dep[b]) swap(a, b);//找到同一深度的结点for (int i = 30; i >= 0; i --) {//每次尽量走最多步，所以倒序枚举if (dep[f[a][i]] >= dep[b]) a = f[a][i]; //能走即走if (a == b) return a;}//同时向上走，同样倍增着走，但是不能走到同一个祖先结点上，这样才是最近的。for (int i = 30; i >= 0; i --) {if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];}return f[a][0];
}这篇关于最近公共祖先结点--LCA（倍增法，言简意赅）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
