写在前面
目录
题目完成度
一、LCA的定义
LCA指的是最近公共祖先。具体地，给定一棵有根树，若结点z既是结点x的祖先，又是结点y的祖先，则称z是x,y的公共祖先。在x,y的公共祖先中，深度最大的一个结点称为x,y的最近公共祖先，记为LCA(x,y)
二、暴力法求LCA
暴力法，顾名思义，非常暴力，这里简单介绍一下
先DFS一遍找出每个点的深度，然后先从深度大的往上跳，跳到x,y两个点深度相同。
如果发现此时x和y是同一个结点，那么原本深度小的那个结点就是两个点的最近公共祖先。
如果不是同一个点，那么就两个点一起同时往上跳，直到发现两个点相同，则此时到达的这个结点为x,y两点的最近公共祖先。
484很简单？QWQ
那我等下放个代码，就酱紫吧
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);//默认x深度大于y
while(dep[x]>dep[y]) x=fa[x];//x每次变成自己的父结点，即往上跳一步
if(x==y) return y;
//如果此时两个结点相同，那么原本深度较小的结点就是LCA
while(x!=y)
x=fa[x],y=fa[y];//两个点同时一步步往上跳
return x;//此时两个节点相同，都是LCA
}
其实还有一种暴力的方法
就是先让其中一个点一路跳到根结点，标记经过的结点，然后另一个点也往上跳，遇到的第一个标记了的结点就是LCA
同样放下代码
int LCA(int x,int y){
while(x!=root){//root为根结点
x=fa[x];
visit[x]=;//标记
}
while(!visit[y])//如果遇到被标记了的就找到了LCA
y=fa[y];
return y;
}
三、倍增法求LCA
这是一个非常重要的算法啦！一定要记住QAQ
我来讲一讲啦
【预处理】
设f[x][k]表示x结点的2k辈祖先，即从x向根结点走2k步到达的结点
如果该结点不存在，则令f[x][k]=0，f[x][0]就是x的父亲结点
因为2k=2k-1+2k-1，所以对于1≤k≤logn，有f[x][k]=f[f[x][k-1]][k-1]
预处理部分的时间复杂度为O(nlongn)
void ready(int x,int father){
dep[x]=dep[father]+;//计算深度
go(i,,)//预处理f数组
f[x][i+]=f[f[x][i]][i];
for(int i=head[x];i;i=next[i]){
int y=to[i];//用链式前向星存边
if(y==father) continue;
f[y][]=x;
ready(y,x);
}
}
【查找LCA】
预处理过后可以对多个x,y查找LCA，每次的时间复杂度均为O(nlogn)
具体操作如下：
1.假设dep[x]≥dep[y]，如果不成立可以交换
2.用二进制拆分思想把x上调到与y同一深度
其实就是依次尝试让x向上跳k=2logn...21,20步，若到达的结点比y深，则令x=f[x][k]
3.和上面说的一样，若此时x与y相等，则y就是LCA
4.若此时x≠y，那么x和y同时往上跳，同样用二进制拆分思想，把x和y同时向上跳，并保持深度一致且不相会
与上面调整x时一样，让x和y尝试向上走k=2logn...21,20步，若f[x][k]≠f[y][k](即两点不相会)，则令x=f[x][k]，y=f[y][k]
5.结束时x和y必然只差一步就相会了，所以他们的父节点f[x][0]就是LCA啦！QWQ
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
back(i,,){
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
//只要x的深度没有比y小就可以继续跳
if(x==y) return x;
}
back(i,,){
if(f[x][i]!=f[y][i])//跳的过程中要保证两点不相会
x=f[x][i],y=f[y][i];
}
return f[x][];
}
最后再放一个完整版代码吧QWQ
#include<bits/stdc++.h>
#define go(i,a,b) for(register int i=a;i<=b;i++)
#define back(i,a,b) for(register int i=a;i>=b;i--)
using namespace std;
const int N=;
int n,m;
int dep[N],head[N];
int f[N][];
int next[N*],to[N*],num=;
int last=;
int fr(){
int w=,q=;
char ch=getchar();
while(ch<''||ch>''){
if(ch=='-') q=-;
ch=getchar();
}
while(ch<=''&&ch>='')
w=(w<<)+(w<<)+ch-'',ch=getchar();
return w*q;
}
void ready(int x,int father){
dep[x]=dep[father]+;
go(i,,)
f[x][i+]=f[f[x][i]][i];
for(int i=head[x];i;i=next[i]){
int y=to[i];
if(y==father) continue;
f[y][]=x;
ready(y,x);
}
}
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
back(i,,){
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;
}
back(i,,){
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
}
return f[x][];
}
int main(){
n=fr();
int root,father;
go(i,,n){
father=fr();
if(father==) root=i;
next[++num]=head[father];
to[num]=i;
head[father]=num;
next[++num]=head[i];
to[num]=father;
head[i]=num;
}
ready(root,);
m=fr();
while(m--){
int x=fr(),y=fr();
last=LCA(x,y);
printf("%d\n",last);
}
return ;
}
代码戳这里
四、树链剖分求LCA
咕咕咕咕咕
五、LCA典型例题
咕咕咕咕