非常重要的东西
我甚至模拟赛都不打了来打笔记
很简单啊，朴素lca是这样，两个节点，先令深度相等，然后一个一个往上跳直到跳到相同的位置则那个点为两点的lca
但是令深度相等与往上跳的过程都要一个一个慢慢跳所以时间复杂度拉满了
那么我们能以什么方式优化呢
我们可以发现，每个数都可以用几个二的几次方的和的方式来表示
把一个一个往上跳的过程抽象成下图一样在数组中跳至指定位置
比如从1到7
我们可以直接一个一个跳过去
也可以预处理一个数组--x[i][j]:第i个数向右跳2^j到达的数
举个例子a[1]往右跳2^1是2[3]呈现在数组中就是x[1][1]==3
于是我们就可以
从一到五
从五到七
由此很轻易可以知道怎么树上倍增
定义fa[i][j]:第i个节点向上跳2^j到达的父节点
于是我们就可以用这个思想来优化O(n)的令深度相等与往上跳的过程成O(logn)
damn码:
#include<bits/stdc++.h>
using namespace std;
vector<int> e[500005];//存图
int fa[500005][20],depth[500005];
//fa[i][j]表示i上方第2的j次方的祖先，比如fa[i][0]就是i的父亲，depth存储深度，根节点深度为1
void init(int son,int father){//初始化，两个变量英文即为含义
depth[son]=depth[father]+1;//子节点是父亲节点的深度加1
fa[son][0]=father;//将son的第一个祖先设为父亲
for(int i=1;i<20;i++) fa[son][i]=fa[fa[son][i-1]][i-1];
/*这句话翻译过来是：son跳2的i次方到达的点是它跳2的i-1次方步后再跳2的i-1次方能到的点
还是举本文章第一张图的例子，
那么5的父亲节点为3，即5跳一步能到3；5跳两步（即fa[5][1])到1,3跳一步(即fa[3][0])到1
也就是将跳好多步转化为两个部分，从“一跳到位”变成“跳一会儿，休息一会儿，再跳一会儿”
大家也可以尝试其它例子帮助理解
*/
for(int i=0;i<e[son].size();i++){
if(e[son][i]!=father) init(e[son][i],son);
//遍历son的连边，不是它的爸爸就是它的儿子，那就进去登记父子关系。
}
}
int lca(int x,int y){
if(depth[x]<depth[y]) swap(x,y);//默认x比y深度大，没有的话换一下就好了，减少代码难度
for(int i=19;i>=0;i--){
if(depth[fa[x][i]]>=depth[y]){ //只要比y深就继续跳直到一样
x=fa[x][i];
}
}
if(x==y) return x;//如果已经相等了直接返回就行
for(int i=19;i>=0;i--){//没有就一起跳，直到找到为止
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
int main(){
int n,m,s;
scanf("%d%d%d", &n, &m, &s);//用scanf或快读都行，cin会超时
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d", &x, &y);
e[x].push_back(y);//无向图
e[y].push_back(x);
}
init(s,0);//0是一个虚节点，因为没有节点是0，现在我们添加一个深度为0的0节点，便于处理根节点
while(m--){
int a,b;
scanf("%d%d", &a, &b);
cout<<lca(a,b)<<endl;
}
return 0;
}