emmmmm近日刚刚学习了LCA的倍增做法，写一篇BLOG来加强一下印象w
首先 何为LCA？
LCA“光辉”是印度斯坦航空公司(HAL)为满足印度空军需要研制的单座单发轻型全天候超音速战斗攻击机，主要任务是...
LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。
怎么样，很好理解吧！
然后，关于倍增
emmmmm，可以这么理解：
……
……
……
https://blog.csdn.net/jarjingx/article/details/8180560（太烂啦有空再自己填一下这个坑吧x
怎么样，很好理解吧！
（懒癌患者是这样的orz，对不住各位观众老爷&&神犇啦
那么！
怎么把他们结合在一起就是我们要研究的问题啦。
相信大家第一次看到形似“给出一棵树和若干结点，求他们的LCA”这种问题就会想到爆搜吧（单次最坏和平均时间复杂度都是O(n)）
但是显而易见，万恶机智的出题人是不会放我们这么简单的做法过哒
这时候我们就需要在原来的爆搜上加上倍增优化一下时间复杂度（优化之后是O(nlogn)）
我们给这种神秘地操作叫做 树上倍增
总而言之就是
用一个二维数组fa[i][j]来表示从第i个结点向上跳 2 ^ j 个结点所在的点，那么理所当然的fa[i][0]表示的就是i点的父结点啦
int lca(int x, int y) {
if (dep[x] > dep[y]) {
swap(x, y); //交换x点和y点，让x点在y点上♂面（噫
}
for (int i = ; i >= ; i--) {
if (dep[y] - ( << i) >= dep[x]) {
y = fa[y][i]; //把y点调整到和x点一个高度
}
}
if(x == y) {
return x; //这里是特判哦，如果调整后x点和y点一样直接返回x就行啦
}
for(int i = ; i >= ; i--) {
if(fa[x][i] == fa[y][i]) {
continue; //如果他们的父亲向上跳2 ^ i个点后是同一个点的话就找到他们的LCA啦
}
else {
x = fa[x][i];
y = fa[y][i]; //要雨♂露♂均♂沾，一起向上跳喏
}
}
return fa[x][]; 返回LCAqwqqq
}
以上就是倍增LCA的核心算法啦
然而要知道的是，现在有许多万恶机智的出题人是会卡我们的倍增哒
所以我们就需要
优化优化优化！
因为涉及到图，我们就可以用一种叫派大星链式前向星的东西来优化它（如果你不知道链式前向星可以看看这个：
下面以洛谷的模板题为例，贴一下自己的代码（感谢kkogoro带我“走进LCA”wwww
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int Maxv = ; int fa[Maxv * ][], head[Maxv], dep[Maxv];
int cnt, n, m, s; struct edges {
int v, next;
}edge[Maxv * ]; void add(int x, int y){
edge[cnt].v = y;
edge[cnt].next = head[x];
head[x] = cnt++;
} void dfs(int u, int father){
dep[u] = dep[father] + ;
fa[u][] = father;
for (int i = ; ( << i) <= dep[u]; i++) {
fa[u][i] = fa[fa[u][i - ]][i - ];
}
for (int i = head[u]; i != -; i = edge[i].next) {
int v = edge[i].v;
if (v != father) {
dfs(v, u);
}
}
} int lca(int x, int y) {
if (dep[x] > dep[y]) {
swap(x, y);
}
for (int i = ; i >= ; i--) {
if (dep[y] - ( << i) >= dep[x]) {
y = fa[y][i];
}
}
if(x == y) {
return x;
}
for(int i = ; i >= ; i--) {
if(fa[x][i] == fa[y][i]) {
continue;
}
else {
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][];
} int main(){
int a, b;
memset(head, -, sizeof(head));
scanf("%d %d %d", &n, &m, &s);
for (int i = ; i < n; i++) {
scanf("%d %d", &a, &b);
add(a, b);
add(b, a);
}
dfs(s, );
for(int i = ; i <= m; i++) {
scanf("%d %d", &a, &b);
printf("%d\n", lca(a, b));
}
return ;
}
怎么样
很好理解吧www