LCA复习笔记
chinaxjh
2019-11-13 20:25:03
# Part 1
## 简介
求树上最近公共祖先的算法
可以在$O(nlog_n)$时间复杂度的预处理后，在以$O(log_n)$的时间复杂度回答每一次询问节点$x$,$y$的$LCA$
# Part 2
## 模板
[题目](https://www.luogu.org/problem/P3379)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,m,s,i,len,x,y,a[N],nxt[N],las[N],yu[N][21],dep[N],fa[N];
void add(int x,int y)
{
len++;
a[len]=y;
nxt[len]=las[x];
las[x]=len;
}
void yusc(int x,int fa)
{
int i;
dep[x]=dep[fa]+1;
for (i=0;i<=19;i++)
yu[x][i+1]=yu[yu[x][i]][i];
for (i=las[x];i;i=nxt[i])
if (fa!=a[i])
{
yu[a[i]][0]=x;
yusc(a[i],x);
}
}
int LCA(int x,int y)
{
int i;
if (dep[x]<dep[y]) swap(x,y);
for (i=20;i>=0;i--)
{
if (dep[yu[x][i]]>=dep[y]) x=yu[x][i];
if (x==y) return x;
}
for (i=20;i>=0;i--)
{
if (yu[x][i]!=yu[y][i])
{
x=yu[x][i];
y=yu[y][i];
}
}
return yu[x][0];
}
int main()
{
cin>>n>>m>>s;
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
yusc(s,0);
for (i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
printf("%d\n",LCA(x,y));
}
}
```
# Part 3
## 例题
#### 货车运输
$Kruskal$生成最大树，然后$LCA$求解两点之间路径最小值
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,s,i,len,x,y,q,a[N],b[N],nxt[N],las[N],yu[N][21],ans[N][21],dep[N],fa[N];
bool visit[N];
struct node
{
int x,y,z;
}k[N];
bool cmp(node aa,node bb)
{
return aa.z>bb.z;
}
int gfa(int x)
{
if (x==fa[x]) return x;
fa[x]=gfa(fa[x]);
return fa[x];
}
void add(int x,int y,int z)
{
len++;
a[len]=y;
b[len]=z;
nxt[len]=las[x];
las[x]=len;
}
void kruskal()
{
int i,xx,yy;
for (i=1;i<=m;i++)
{
xx=gfa(k[i].x);
yy=gfa(k[i].y);
if (xx!=yy)
{
fa[yy]=xx;
add(k[i].x,k[i].y,k[i].z);
add(k[i].y,k[i].x,k[i].z);
}
}
}
void yusc(int x,int fa)
{
int i;
visit[x]=true;
dep[x]=dep[fa]+1;
for (i=0;i<=19;i++)
yu[x][i+1]=yu[yu[x][i]][i],
ans[x][i+1]=min(ans[x][i],ans[yu[x][i]][i]);
for (i=las[x];i;i=nxt[i])
if (fa!=a[i])
{
yu[a[i]][0]=x;
ans[a[i]][0]=b[i];
yusc(a[i],x);
}
}
int LCA(int x,int y)
{
int i,anss;
anss=1000000000;
if (dep[x]<dep[y]) swap(x,y);
for (i=20;i>=0;i--)
{
if (dep[yu[x][i]]>=dep[y])
{
anss=min(anss,ans[x][i]);
x=yu[x][i];
}
if (x==y) return anss;
}
for (i=20;i>=0;i--)
{
if (yu[x][i]!=yu[y][i])
{
anss=min(anss,ans[x][i]);
anss=min(anss,ans[y][i]);
x=yu[x][i];
y=yu[y][i];
}
}
return min(min(ans[x][0],ans[y][0]),anss);
}
int main()
{
cin>>n>>m;
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=m;i++)
scanf("%d%d%d",&k[i].x,&k[i].y,&k[i].z);
sort(k+1,k+1+m,cmp);
kruskal();
for (i=1;i<=n;i++)
if (!visit[i])
yusc(i,0);
cin>>q;
for (i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
int w=LCA(x,y);
if (w==0) printf("-1\n");
else printf("%d\n",w);
}
}
```
#### 仓鼠找sugar
[题目](https://www.luogu.org/problem/P3398)
题意很明确，这里涉及到一个重要的知识点，如何判定两个树上的路径相交。
如果两条路径相交，那么一定有一条路径的$LCA$在另一条路径上
而判断一个节点$x$，是否在路径$s-t$上需要满足如下几个条件
- $deep[x]>=deep[LCA(s,t)]$
- $LCA(s,x)=x$或$LCA(t,x)=x;$
摘自:[沧澜](https://www.luogu.org/user/21719)大佬的博客
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,m,s,i,len,x,y,xx,yy,t,k,a[N],nxt[N],las[N],yu[N][21],dep[N],fa[N];
void add(int x,int y)
{
len++;
a[len]=y;
nxt[len]=las[x];
las[x]=len;
}
void yusc(int x,int fa)
{
int i;
dep[x]=dep[fa]+1;
for (i=0;i<=19;i++)
yu[x][i+1]=yu[yu[x][i]][i];
for (i=las[x];i;i=nxt[i])
if (fa!=a[i])
{
yu[a[i]][0]=x;
yusc(a[i],x);
}
}
int LCA(int x,int y)
{
int i;
if (dep[x]<dep[y]) swap(x,y);
for (i=20;i>=0;i--)
{
if (dep[yu[x][i]]>=dep[y]) x=yu[x][i];
if (x==y) return x;
}
for (i=20;i>=0;i--)
{
if (yu[x][i]!=yu[y][i])
{
x=yu[x][i];
y=yu[y][i];
}
}
return yu[x][0];
}
int main()
{
cin>>n>>m;
for (i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
yusc(1,0);
for (i=1;i<=m;i++)
{
scanf("%d%d%d%d",&x,&y,&xx,&yy);
t=LCA(x,y);
k=LCA(xx,yy);
if (dep[t]>=dep[k])
{
if (LCA(t,xx)==t||LCA(t,yy)==t) puts("Y");
else puts("N");
} else {
if (LCA(k,x)==k||LCA(k,y)==k) puts("Y");
else puts("N");
}
}
}
```