转载来源
LCA指的是最近公共祖先(Least Common Ancestors)，如下图所示:
4和5的LCA就是2
那怎么求呢？最粗暴的方法就是先dfs一次，处理出每个点的深度
然后把深度更深的那一个点（4）一个点地一个点地往上跳，直到到某个点（3）和另外那个点（5）的深度一样
然后两个点一起一个点地一个点地往上跳，直到到某个点（就是最近公共祖先）两个点“变”成了一个点
不过有没有发现一个点地一个点地跳很浪费时间？
如果一下子跳到目标点内存又可能不支持，相对来说倍增的性价比算是很高的
倍增的话就是一次跳2i 个点，不难发现深度差为x时，深度更深的那个点就需要跳x个点
于是可以写出这段代码
1 if(depth[a] < depth[b]) swap(a, b); 2 int c = depth[a] - depth[b]; 3 for(int i = 0; i <= 14; i++){ 4 if(c & (1 << i)){ 5 a = up[a][i]; 6 } 7 }接下来很快就会发现一个很严重的问题:两个点按照这样跳，不能保证一定是最近的
所以倍增找lca的方法是这样的:
从最大可以跳的步数开始跳(一定是2i)，如果跳的到的位置一样，就不跳，如果不一样才跳，每次跳的路程是前一次的一半
过程大概就像上图所示，但是执行完了这一段到的点不是最近公共祖先，但是，它们再往上跳一格，就到了
把这一段写成代码，就成了这样：
1 for(int i = 14; i >= 0; i--){ 2 if(up[a][i] != up[b][i]){ 3 a = up[a][i]; 4 b = up[b][i]; 5 } 6 }前面还需要加上一句特判（当a和b在同一边时，深度浅的那个点就是最近公共祖先）
if(a == b) return a;好了，会求lca了，关键是怎么构造倍增数组。
没有疑问的是向上跳一格就是自己的父节点
f[i][0] = fa[i];这个是初值，接着可以根据这个推出来其他的，除此之外还要附上初值0，不然有可能会RE
f[i][j] = f[f[i][j - 1]][j - 1];就是把这一段路，分成两段已经知道的
完整代码就是这样的:
1 Matrix<int> up; 2 inline void init_bz(){ 3 up = Matrix<int>(16, n + 1); 4 memset(up.p, 0, sizeof(int) * 16 * (n + 1)); 5 for(int i = 1; i <= n; i++){ 6 up[i][0] = fa[i]; 7 } 8 for(int j = 1; j <= 14; j++){ 9 for(int i = 1; i <= n; i++){ 10 up[i][j] = up[up[i][j - 1]][j - 1]; 11 } 12 } 13 }注意倍增求LCA适用于询问多的情况，不然光在预处理上花的时间就已经够多了（如果只有一两个询问，直接暴力就好了）
Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！