图论（8）LCA
一、概念
给定一棵有根树，若节点z既是x的祖先，又是y的祖先，则称z是x和y的公共祖先。
在所有公共祖先中，深度最大的一个为最近公共祖先。
求最近公共祖先的方法有：
（1）：
1.x向上走，标记所有路过节点
2.y向上走，走到第一个被标记节点
（2）：树上倍增法
个人认为是动态规划和快速幂的结合。
设f（x，k）是x的2^k辈祖先，即x向上走2^k步到达的结点。如果该节点不存在，则为0.
f（x，0）显然是x的父节点，f（x，k）则可由之前计算的一步步推得，2^k=2^(k-1)+2^(k-1)即x向上走2^(k-1)步到达的结点再向上走2^(k-1)步。：
求lca前先预处理这个f数组。
我们可以用bfs，按照层次顺序，在入队之前，计算它的f数组。时间复杂度nlogn。
基于f数组计算LCA，又有一下几步：
1.设d（x）为x的深度，如果y比x深，则交换x，y
2.用快速幂思想（二进制拆分思想），把x调整到和y一个深度。
3.如果x==y 则已经找到。如果不等于，就把x，y同时向上调整，保持深度相同且二者不相会。
5.调整后，x，y必定只差一步相会，输出他们的父节点，就是LCA
具体看代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N =40010,M=N*2;
int root;
int n,m;
int h[N],e[M],ne[M],idx;
int depth[N];
int fa[N][16];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs()
{
memset(depth,0x3f,sizeof depth);
depth[0]=0;depth[root]=1;
queue<int> q;
q.push(root);
while(q.size())
{
int t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(depth[j]>depth[t]+1)
{
depth[j]=depth[t]+1;//这一步保证了不会更新已经更新过的节点
q.push(j);
fa[j][0]=t;
for(int k=1;k<=15;k++)
fa[j][k]=fa[fa[j][k-1]][k-1];
}
}
}
}
int lca(int a,int b)
{
//先跳到同一层
if(depth[a]<depth[b]) swap(a,b);
for(int k=15;k>=0;k--)
if(depth[fa[a][k]]>=depth[b])
a=fa[a][k];
if(a==b) return a;
//跳到lca的下一层
for(int k=15;k>=0;k--)
if(fa[a][k]!=fa[b][k])
{
a=fa[a][k];
b=fa[b][k];
}
return fa[a][0];
}
int main()
{
scanf("%d",&n);
memset(h,-1,sizeof h);
for(int i=0;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(b==-1) root=a;
else add(a,b),add(b,a);
}
bfs();
cin>>m;
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
int p=lca(a,b);
if(a==p) puts("1");
else if(p==b) puts("2");
else puts("0");
}
return 0;
}
作者：yankai
链接：https://www.acwing.com/activity/content/code/content/4562419/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。二、LCA的tarjan算法
在线做法：读一个询问，处理一个，输出一个
离线做法：读完全部询问，再全部处理完，再全部输出
LCA的tarjan算法时离线算法，本质上是使用并查集对“向上标记法”的优化。把m个询问统一读入，最后统一输出。
在深度优先遍历的任意时刻，树上的点分为三类：
1.已经访问完毕并且回溯的点，标记为2
2.已经开始递归，但是没有回溯的点，这些结点就是正在访问的结点x以及x的祖先。标记为1
3.尚未开始访问的点，没有标记。
对于正在访问的结点x，他到根节点的路径已经标记为1。如果y是已经回溯的点，则lca（x，y）就是y向上走到根，第一个遇到标记为1的点。
用并查集优化，当一个节点获得2标记时，把它所在的集合合并到它父节点所在的集合中（合并时父节点标记一定是1，且单独构成一个集合）
这相当于每个已经回溯过的点都指向它的父节点，即向上走遇到的第一个开始递归但没有回溯的点，也就是x所在的支路上深度比x小的某一个点，也就是LCA（x，y）。
本题中最短距离是dist（x）+dist（y）-2*dist（LCA（x，y））
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
const int N =10010,M=N*2;
int h[N],e[M],ne[M],w[M],idx;
int n,m;
int dist[N];
int res[M];//每个询问的结果
int st[N];
int p[N];
vector<PII> query[M];
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void dfs(int u,int fa)
{
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dist[j]=dist[u]+w[i];
dfs(j,u);
}
}
void tarjan(int u)
{
st[u]=1;//正在递归的结点
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!st[j])
{
tarjan(j);
p[j]=u;
}
}
for(auto item:query[u])
{
int y=item.first,id=item.second;
if(st[y]==2)
{
int anc=find(y);
res[id]=dist[u]+dist[y]-2*dist[anc];
}
}
st[u]=2;
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=0;i<n-1;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
if(a!=b)
{
query[a].push_back({b,i});
query[b].push_back({a,i});
}
}
dfs(1,-1);
tarjan(1);
for(int i=0;i<m;i++) cout<<res[i]<<endl;
}
作者：yankai
链接：https://www.acwing.com/activity/content/code/content/4570518/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。三、例题
AcWing 356. 次小生成树
在之前介绍过严格次小生成树。它与最小生成树只差一条边，构造方法是枚举所有非树边，设该边连接的是a，b。则用它替代a到b上的最大边或者是次大边。
枚举中边权和最大的为答案。
关键是如何求出任意两个点的最大边和次大边。我们仿照动态规划求LCA的思想。用d1[i][k]记录j点向上跳2^k次方步的最大边，d2为次大边。
状态转移：在一棵树中，a到b的简单路为a到LCA(a,b)到b。因此借助LCA更新。具体方式不赘述。
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long LL;
const int N =100010,M=300010,INF=0x3f3f3f3f;
int n,m;
struct Edge{
int a,b,w;
bool used;
bool operator< (const Edge& t)const
{
return w<t.w;
}
}edge[M];
int p[N];
int h[N],e[M],ne[M],w[M],idx;
int depth[N],fa[N][17],d1[N][17],d2[N][17];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
LL krusal()//预处理树边
{
LL res=0;
for(int i=0;i<=n;i++) p[i]=i;
sort(edge,edge+m);
for(int i=0;i<m;i++)
{
int a=find(edge[i].a),b=find(edge[i].b),w=edge[i].w;
if(a!=b)
{
edge[i].used=true;
res+=w;
p[a]=b;
}
}
return res;
}
void build()
{
memset(h,-1,sizeof h);
for(int i=0;i<m;i++)
if(edge[i].used)
{
int a=edge[i].a,b=edge[i].b,w=edge[i].w;
add(a,b,w),add(b,a,w);
}
}
void bfs()
{
queue<int> q;
memset(depth,0x3f,sizeof depth);
depth[0]=0;depth[1]=1;
q.push(1);
while(q.size())
{
int t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(depth[j]>depth[t]+1)
{
depth[j]=depth[t]+1;
q.push(j);
fa[j][0]=t;
d1[j][0]=w[i];d2[j][0]=-INF;
for(int k=1;k<=16;k++)
{
int anc=fa[j][k-1];
fa[j][k]=fa[anc][k-1];
int distance[4]={d1[j][k-1],d1[anc][k-1],d2[j][k-1],d2[anc][k-1]};
for(int u=0;u<4;u++)
{
int d=distance[u];
if(d>d1[j][k]) d2[j][k]=d1[j][k],d1[j][k]=d;
else if(d!=d1[j][k]&&d>d2[j][k]) d2[j][k]=d;
}
}
}
}
}
}
int lca(int a,int b,int w)
{
static int distance[N*2];
int cnt=0;
if(depth[a]<depth[b])
swap(a,b);
for(int k=16;k>=0;k--)
if(depth[fa[a][k]]>=depth[b])
{
distance[cnt++]=d1[a][k];
distance[cnt++]=d2[a][k];
a=fa[a][k];//最后才跳
}
if(a!=b)
{
for(int k=16;k>=0;k--)
{
if(fa[a][k]!=fa[b][k])
{
distance[cnt++]=d1[a][k];
distance[cnt++]=d2[a][k];
distance[cnt++]=d1[b][k];
distance[cnt++]=d2[b][k];
a=fa[a][k],b=fa[b][k];
}
}
distance[cnt++]=d1[a][0];
distance[cnt++]=d1[b][0];
}
int dist1=-INF,dist2=-INF;
for(int i=0;i<cnt;i++)
{
int d = distance[i];
if (d > dist1) dist2 = dist1, dist1 = d;
else if (d != dist1 && d > dist2) dist2 = d;
}
if(w>dist1) return w-dist1;
if(w>dist2) return w-dist2;
return INF;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
edge[i]={a,b,w};
}
LL sum=krusal();
build();
bfs();
LL res=1e18;
for(int i=0;i<m;i++)
if(!edge[i].used)
{
int a=edge[i].a,b=edge[i].b,w=edge[i].w;
res=min(res,sum+lca(a,b,w));
}
cout<<res;
}
AcWing 352. 闇の連鎖 （树上差分）
树上差分：区间操作对应路径操作，前缀和对应子树和。
根据题意，主要边构成一棵树，附加边是非树边。把一条附加边添加到主要边构成的树中，会形成一个环。因此如果第一步切断x，y之间路径的某条边，那么第二步就必须切断附加边（x，y）。
因此我们设每条附加边把（x，y）之间路径上的每条边“覆盖了一次”。我们只需要统计每条主要边被覆盖了多少次。如果第一次把覆盖0次的主要边切断，第二步可以切断任意一条附加边。
如果第一次把覆盖1次的主要边切断，第二步唯一
如果第一次把覆盖2次以上的主要边切断，第二步无解。
树上差分：对每条非树边，令节点x+1，节点y+1，节点LCA(x，y)-2。最后做一次dfs，求出以F数组，代表以x为根的子树中各节点的权值之和。表示，x节点与他的父节点之间的树边被覆盖的次数。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N =100010,M=2*N;
int n,m;
int h[N],e[M],ne[M],idx;
int d[N];
int depth[N];
int fa[N][17];
int ans;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs()
{
memset(depth,0x3f,sizeof depth);
depth[0]=0,depth[1]=1;
queue<int> q;
q.push(1);
while(q.size())
{
int t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(depth[j]>depth[t]+1)
{
depth[j]=depth[t]+1;
q.push(j);
fa[j][0]=t;
for(int k=1;k<=16;k++)
fa[j][k]=fa[fa[j][k-1]][k-1];
}
}
}
}
int lca(int a,int b)
{
if(depth[a]<depth[b]) swap(a,b);
for(int k=16;k>=0;k--)
if(depth[fa[a][k]]>=depth[b])
a=fa[a][k];
if(a==b) return a;
for(int k=16;k>=0;k--)
if(fa[a][k]!=fa[b][k])
{
a=fa[a][k];
b=fa[b][k];
}
return fa[a][0];
}
int dfs(int u,int father)
{
int res=d[u];
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==father) continue;
int s=dfs(j,u);
if(s==0) ans+=m;
else if(s==1) ans++;
res+=s;
}
return res;
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
add(a,b),add(b,a);
}
bfs();
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
int p=lca(a,b);
d[a]++,d[b]++,d[p]-=2;
}
dfs(1,-1);
cout<<ans;
}
作者：yankai
链接：https://www.acwing.com/activity/content/code/content/4587939/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。