写在前面

目录

题目完成度

---

 

 

一、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]) 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]=1;//标记    }    while(!visit[y])//如果遇到被标记了的就找到了LCA        y=fa[y];    return y;}

 

---

 

三、倍增法求LCA

这是一个非常重要的算法啦！一定要记住QAQ

我来讲一讲啦

【预处理】

设f[x][k]表示x结点的2^k辈祖先，即从x向根结点走2^k步到达的结点

如果该结点不存在，则令f[x][k]=0，f[x][0]就是x的父亲结点

因为2^k=2^k-1+2^k-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]+1;//计算深度    go(i,0,19)//预处理f数组        f[x][i+1]=f[f[x][i]][i];    for(int i=head[x];i;i=next[i]){        int y=to[i];//用链式前向星存边        if(y==father) continue;        f[y][0]=x;        ready(y,x);    }}

【查找LCA】

预处理过后可以对多个x,y查找LCA，每次的时间复杂度均为O(nlogn)

具体操作如下：

1.假设dep[x]≥dep[y]，如果不成立可以交换

2.用二进制拆分思想把x上调到与y同一深度

其实就是依次尝试让x向上跳k=2^logn...2¹,2⁰步，若到达的结点比y深，则令x=f[x][k]

3.和上面说的一样，若此时x与y相等，则y就是LCA

4.若此时x≠y，那么x和y同时往上跳，同样用二进制拆分思想，把x和y同时向上跳，并保持深度一致且不相会

与上面调整x时一样，让x和y尝试向上走k=2^logn...2¹,2⁰步，若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]) x=f[x][i];//只要x的深度没有比y小就可以继续跳        if(x==y) return x;    }    back(i,20,0){        if(f[x][i]!=f[y][i])//跳的过程中要保证两点不相会            x=f[x][i],y=f[y][i];    }    return f[x][0];}
     

最后再放一个完整版代码吧QWQ

1 #include
      
        2 #define go(i,a,b) for(register int i=a;i<=b;i++) 3 #define back(i,a,b) for(register int i=a;i>=b;i--) 4 using namespace std; 5 const int N=100002; 6 int n,m; 7 int dep[N],head[N]; 8 int f[N][20]; 9 int next[N*2],to[N*2],num=0;10 int last=0;11 int fr(){12     int w=0,q=1;13     char ch=getchar();14     while(ch<'0'||ch>'9'){15         if(ch=='-') q=-1;16         ch=getchar();17     }18     while(ch<='9'&&ch>='0')19         w=(w<<1)+(w<<3)+ch-'0',ch=getchar();20     return w*q;21 }22 void ready(int x,int father){23     dep[x]=dep[father]+1;24     go(i,0,18)25         f[x][i+1]=f[f[x][i]][i];26     for(int i=head[x];i;i=next[i]){27         int y=to[i];28         if(y==father) continue;29         f[y][0]=x;30         ready(y,x);31     }32 }33 int LCA(int x,int y){34     if(dep[x]
       
        =dep[y]) x=f[x][i];37         if(x==y) return x;38     }39     back(i,19,0){40         if(f[x][i]!=f[y][i])41             x=f[x][i],y=f[y][i];42     }43     return f[x][0];44 }45 int main(){46     n=fr();47     int root,father;48     go(i,1,n){49         father=fr();50         if(father==0) root=i;51         next[++num]=head[father];52         to[num]=i;53         head[father]=num;54         next[++num]=head[i];55         to[num]=father;56         head[i]=num;57     }58     ready(root,0);59     m=fr();60     while(m--){61         int x=fr(),y=fr();62         last=LCA(x,y);63         printf("%d\n",last);64     }65     return 0;66 }
       
      

 

---

四、树链剖分求LCA

 咕咕咕咕咕

---

五、LCA典型例题

 咕咕咕咕