算法篇之最近公共祖先(LCA)
引言：
本篇将会讲解朴素和在线倍增的最近公共祖先算法，当然还有离线的算法，但是因为种种原因，Moon的数据结构与算法专栏暂时就更新到这了，后期可能会回归选择更新，感谢大家的喜欢！，也祝愿大家能够不断挑战自己，登足顶峰！
最近公共祖先(LCA)
概念：
- 祖先节点：给定一棵多叉树，对于其中任意非根节点x，我们称从x的父节点到根节点的路径上的所有点为x的祖先节点
- 公共祖先：如果节点a同时是节点b和c的祖先，称a是b和c的公共祖先
最近公共祖先LCA:对于树上任意两点x和y，距离它们最近的公共祖先的节点就称为x和y的最近公共祖先(简称LCA)
朴素求解(暴力)
原理：我们只需要将x和y节点都升到同一深度或同一层，并让x和y同时向上走，直到x和y相等时，当前的x或y就是原先x和y节点的最近公共祖先
时间复杂度：最坏情况下，n为树上节点数，q为查询次数，则朴素求解的lca时间复杂度为O(q*n)
做法：
- 定义一个
dep数组和p数组，分别用于存储树上节点的深度和每个树上节点的父节点 - 先用
dfs预处理dep数组和p数组 - 对于每次查询，我们先判断dep[x]是否大于dep[y]，如果小于，则将x和y交换
- 将x上升到与y相同深度，也就是dep[x]==dep[y]的时候
- 然后令x和y一起上升，直到x==y，则x或y就是最近公共祖先，返回x或y
代码：
#include <bits/stdc++.h>
using namespace std;const int N=5e5+20;
int n,m,s,a,b; //n为节点数，m为查询次数，s为根节点编号,a和b用于临时存储节点的临时变量
int dep[N],p[N];
vector<int>g[N]; //存储边集void dfs(int u,int d){dep[u]=d;int size=g[u].size();for(int i=0;i<size;++i){int v=g[u][i];if(v==p[u]) continue;p[v]=u;dfs(v,d+1);}
}int lca(int x,int y){if(dep[x]<dep[y]) swap(x,y);while(dep[x]>dep[y]) x=p[x];while(x!=y){x=p[x];y=p[y];}return x;
}int main() {cin>>n>>m>>s;for(int i=1;i<n;++i){cin>>a>>b;g[a].emplace_back(b);g[b].emplace_back(a);}dfs(s,0);while(m--){cin>>a>>b;cout<<lca(a,b)<<endl;}system("pause");return 0;
}
在线倍增算法
原理：
- 跟朴素求解一样的，我们也是需要将x和y置于同一深度，但是我们不再是简单的一个个去上升，而是利用倍增的思想，每次以2i(i∈[0,log2(dep[x]-dep[y])])的递增上升
- 同样的当x和y在同一深度上升时，也是利用倍增的递增上升，每次以2i(i∈[0,log2(dep[x])])的跨度递增，直到x和y相等
在线：就是输入数据，就直接通过计算得出结果
倍增：倍增就是递增速度是通过2j(j=0,1,2,…)的速度递增的，一个倍增数组的元素f[i][j]，表示第i+2j的元素
至于j为什么最大为log2(n+1)解答：n为树上节点数，我们假设最坏情况为从根节点一直到最后一个节点x都是一条线连接，那最后一个节点x也必须能够通过倍增访问根节点，而倍增的速度是通过2j(j=0,1,2,…)的速度递增的，因此最大的j就应该保证x+2j等于根节点，因此我们发现根节点到x中间一共n-1(包括根节点)，因此最大的j要保证2j=n-1，这样就可以得到最大的
j=log2(n)+1了
做法：
-
定义一个
dep[N]和f[N][log2(n+1)]，分别用于存储树上节点的深度、每个树上节点的父节点和存储每个节点i通过2j(j=0,1,2,…log2(n)+1)的递增到达的节点 -
通过
dfs预处理dep和f数组预处理f数组时，假设当前节点为u，则将f[u][0]置为p[u](上升2的0次方就是上升一个，所以为父节点)，然后遍历递增倍数i从1到log2(dep[2])，然后将利用u的2i的祖先等于u的2i-1的2i-1祖先，也就是
f[u][i]=f[f[u][i-1]][i-1]，得到当前节点u倍增到的各节点 -
对于每次查询，判断dep[x]是否大于dep[y]，如果小于，则将x和y交换
-
然后开始通过
递增倍数i从log2(dep[x]-dep[y])到0的跨度递增，如果当前2i小于dep[x]-dep[y]，就让x上升到f[x][i]，让x与y深度相等为啥i从log2(dep[x]-dep[y])到0，而不是从0开始
解答：
- 这是
因为我们从0开始增加的跨度，很可能会使x的深度达不到y，为啥是达不到呢，因为我们需要判断当前dep[x]-dep[y]是否大于当前2i，如果从0开始就会产生x到dep[x]-dep[y]还有余数，而剩下的i太大，导致无法使用 - 至于为啥会有余数，我们可以从二进制进行证明，假设dep[x]-dep[y]=50，而50的二进制为110010，我们的i从log2(50)也就是5到0的过程中，假设当前i为5，25转为二进制就为100000，因此就将50中的最高位1消掉，假设当前i为3，此时的50只剩0010，而23为1000，0010<1000，所以不减，按照这种规则(如果2i大就不减，小就减)，50最终一定会变为0
- 而i从0开始递增，假设当前i=0，那相减，二进制就为110001，因为i是递增的，所以导致最低位的1一定会留下，就会产生余数，将这两种方法转换为10进制也是一样道理，50-32-16-2=0，而50-1-2-4-8-16=19，而19<32，导致无法继续减，所以可能导致x无法上升到y的高度
- 这是
-
判断x是否等于y，如果等于，就返回x(这种情况就是y是x的祖先)
-
当dep[x]==dep[y]时，我们就可以让x和y同时倍增上升，按照步骤4的递增方法递增，当for循环中判断
f[x][i]!=f[y][i]，如果不相等就让x和y一起上升到f[x][i]和f[y][i]，直到i=0时，根据4的性质证明，发现最后f[x][0]都会等于f[y][0]，所以i=0时，无法x和y无法上升，所以最后返回f[x][0]
代码：
#include <bits/stdc++.h>
using namespace std;const int N=5e5+20;
int n,m,s,a,b; //n为节点数，m为查询次数，s为根节点编号,a和b用于临时存储节点的临时变量
int dep[N],f[N][22]; //log2(N)算出来19，可以创建大于19的数组
vector<int>g[N]; //存储边集void dfs(int u,int p,int d){dep[u]=d;f[u][0]=p;for(int i=1;i<=log2(dep[u]);++i){f[u][i]=f[f[u][i-1]][i-1];}int size=g[u].size();for(int i=0;i<size;++i){int v=g[u][i];if(v==p) continue;dfs(v,u,d+1);}
}int lca(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int i=log2(dep[x]-dep[y]);i>=0;--i){if((1<<i)<=dep[x]-dep[y]) x=f[x][i];}if(x==y) return x;for(int i=log2(dep[x]);i>=0;--i){if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}}return f[x][0];
}int main() {cin>>n>>m>>s;for(int i=1;i<n;++i){cin>>a>>b;g[a].emplace_back(b);g[b].emplace_back(a);}dfs(s,s,0);while(m--){cin>>a>>b;cout<<lca(a,b)<<endl;}system("pause");return 0;
}