【图论线段树复习】之lca的应用
Ryan_
2019-09-27 10:18:46
众所周知，树上的任意两点之间有且仅有一条最短路径。因此我们若想要知道某点是否在某路径上，我们只需求该点到这条路径两端的距离相加是否会等于这条路径就行了，（啰嗦一下）由上面第一句话可知不在当前路径上的点到路径的两端点的距离必然存在且必然大于当前路径的长，正确性得证。
一道经典例题[p3398仓鼠找sugar](https://www.luogu.org/problem/P3398)
**0分代码**
```
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n,k;
int first[N],go[N],nxt[N],tot,dep[N],f[N][30];
void add(int u,int v) {
nxt[++tot]=first[u];
first[u]=tot;
go[tot]=v;
}
void Deal_first(int u,int fa) {
dep[u]=dep[fa]+1;
for(int i=0; i<=15; i++)
f[u][i+1]=f[f[u][i]][i];
for(int i=first[u];i;i=nxt[i]){
int v=go[i];
if(v==fa)continue;
f[v][0]=u;
Deal_first(v,u);
}
}
int lca(int x,int y) {
if(dep[x]<dep[y])swap(x,y);
for(int i=15;i>=0;i--){
if(dep[f[x][i]]!=dep[y]){
x=f[x][i];
}
if(x==y)return x;
}
for(int i=15;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int dis(int x,int y){
int c=lca(x,y);
return abs(dep[c]-dep[y])+abs(dep[c]-dep[x]);
}
void Init() {
scanf("%d%d",&n,&k);
for(int i=1,a,b; i<n; i++)scanf("%d%d",&a,&b),add(a,b),add(b,a);
for(int i=1,a,b,c,d; i<=k; i++) {
scanf("%d%d%d%d",&a,&b,&c,&d);
int L1=lca(a,b),L2=lca(c,d);
if(((dis(L1,c)+dis(L1,d))==dis(c,d))||((dis(L2,a)+dis(L2,b))==dis(a,b)))cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
}
int main() {
Init();
Deal_first(1,0);
return 0;
}
```
为啥0分啊？？
**100分代码：**
```
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int f[N][25],d[N],dis[N],T,n,m,tot,t,ver[2*N],next[2*N],head[N];
queue <int> q;
void add(int x,int y)
{
ver[++tot]=y;
next[tot]=head[x];
head[x]=tot;
}
int lca(int x,int y)
{
if(d[x]>d[y]) swap(x,y);
for(int i=t;i>=0;i--) if(d[f[y][i]]>=d[x]) y=f[y][i];
if(x==y) return x;
for(int i=t;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int dist(int a,int b) {return dis[a]+dis[b]-2*dis[lca(a,b)];}//lca求树上两点距离
int main()
{
scanf("%d%d",&n,&m);
t=(int)(log(n)/log(2))+1;
for(int i=1;i<=n;i++) head[i]=d[i]=0;
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
q.push(1);
d[1]=1;
while(q.size())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=next[i])
{
int y=ver[i];
if(d[y]) continue;
d[y]=d[x]+1;
dis[y]=dis[x]+1;
f[y][0]=x;
for(int j=1;j<=t;j++)
f[y][j]=f[f[y][j-1]][j-1];
q.push(y);
}
}
for(int i=1;i<=m;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(dist(x1,y1)+dist(x2,y2)>=dist(x1,x2)+dist(y1,y2)) printf("Y\n");
else printf("N\n");
}
return 0;
}
```
---
这里复习一下lca的具体应用：
- 上面的总结中求路径的长度的过程，即先求出路径两端点的lca，然后用lca所在层数减去两端点所在层数的绝对值，再将绝对值相加
- 判断树上两路径是否相交，引用一下其他人的方法及证明
> #
询问树上aa到bb，cc到dd的两条路径是否相交
我们容易发现，如果相交，记 x=lca(a,b)x=lca(a,b)，y=lca(c,d)y=lca(c,d)，则必有x在c~d路径上或yy在a~b路径上
之前类似的题解都没有给出证明。为什么呢？
首先易知两点的lca在其路径上。如果路径相交，那么x要么在相交的路径上，要么不在。我们不妨记相交的那段为e~f
如果不在，由对称性，不妨设xx靠近a，那么有a到x深度递减，b到e、e到f、f到x深度递减；同样，肯定有c到f、d到e深度递减，由此可知，y必定为f，由此得证（以上的e、f和c、d的相对位置是由对称性直接设的，我表达不太好，各位不妨画图理解一下qwq）
先去做一些经典题目积累思路一起过来总结，待更