最近公共祖先（LCA）

概念

定义

给定一棵有根树，对于树上的两个结点 $x,y$，称其最近公共祖先（LCA）为所有既是 $x$ 的祖先，又是 $y$ 的祖先的所有结点构成的集合中深度最大的一个。

求法

暴力求LCA

将深度大的点往上拉到和深度小的点同一深度，然后一起往上一步步跳，直到跳到同一点。

时间复杂度：$O(n)$

倍增求LCA

优化：如果能一次向上跳多步，则能大大提升效率。

思路：第一次先跳尽可能多的步数，后面每次步长折半。

定义 $dep[x]$ 为 $x$ 的深度，$f[x,k]$ 为 $x$ 的 $2^k$ 辈祖先，即从 $x$ 出发向根节点走 $2^k$ 步能到达的结点。

容易得到：

$$f[x,k]=f[f[x,k-1],k-1], k \in [1,\log n]$$

预处理数组 $f$ 的过程是递推，可以先遍历得到 $f[x,0]$，再递归遍历计算所有值。

对于求LCA的两个结点 $x,y$，不妨设 $dep[x] \ge dep[y]$，否则交换两结点。

若 $dep[x] > dep[y]$，依次尝试从 $x$ 向上走 $k=2^{\lfloor \log n \rfloor}, \cdots ,2,1$ 步，若到达的结点比 $y$ 深，则更新 $x$ 为 $f[x,k]$。

一直到 $dep[x]=dep[y]$，若 $x=y$，则 $LCA=x$；否则，依次尝试从 $x,y$ 向上走 $k=2^{\lfloor \log n \rfloor}, \cdots ,2,1$ 步，若 $f[x,k] \ne f[y,k]$，则更新 $x$ 为 $f[x,k]$，$y$ 为 $f[y,k]$。

最后结果为 $f[x,0]$。

预处理时间复杂度：$O(n\log n)$

总时间复杂度：$O((n+q)\log n)$

void pre_deal(int u,int fa){
	dep[u]=dep[fa]+1;
	for(int i=0;i<logn;++i)
		f[u][i+1]=f[f[u][i]][i];
	for(int e=head[u];e;e=next[e]){
		int v=go[e];
		if(v==fa) continue;
		f[v][0]=u;
		pre_deal(v,u);
	} 
}

int LCA(int x,int y){
	if(dep[x]<dep[y]) return LCA(y,x);
	for(int i=logn;i>=0;--i){
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
		if(x==y) return x;
	}
	for(int i=logn;i>=0;--i)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}

例题

A. 点的距离

找到 $x,y$ 的 $LCA$，距离就是 $dep[x]+dep[y]-2 \times dep[LCA]$。

# include<iostream>
# include<cmath>
using namespace std;

const int N=1e5+5,LN=20;
int n,x,y,q,logn;
int dep[N],f[N][LN];
int cnt,head[N],go[2*N],nxt[2*N]; //两倍边 

void add(int x,int y){
	go[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}

void pre_deal(int u,int fa){
	f[u][0]=fa;
	dep[u]=dep[fa]+1;
	for(int i=1;i<=logn;++i)
		f[u][i]=f[f[u][i-1]][i-1];
	for(int i=head[u];i;i=nxt[i]){
		int v=go[i];
		if(v==fa) continue;
		pre_deal(v,u);
	}
}

int LCA(int x,int y){
	if(dep[x]<dep[y]) return LCA(y,x);
	for(int i=logn;i>=0;--i)
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=logn;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){
	return dep[x]+dep[y]-2*dep[LCA(x,y)];
}

int main(){
	cin>>n;
	logn=floor(log2(n));
	for(int i=1;i<n;++i){
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	pre_deal(1,0);
	cin>>q;
	while(q--){
		cin>>x>>y;
		cout<<dis(x,y)<<endl;
	}
	return 0;
}

B. 暗的解锁

容易得到“主要边”构成一棵树。把一条附加边 $(x,y)$ 添加到图上，会与树上 $x,y$ 之间的路径构成环。也就是说，如果第一步选择切断 $x,y$ 之间的路径上的某条边，那么第二步就必须切断边 $(x,y)$ ，才能让图不连通。

因此我们可以称每条附加边 $(x,y)$ 都把树上 $x,y$ 之间的路径上每条边都覆盖一次。我们只需统计每条主要边被覆盖了多少次。

采用“树上差分”的思路，对于每条附加边 $(x,y)$，令两结点的权值 $+1$，$LCA$ 的权值 $-2$，那么对于每个结点 $x$，其所有子树上的结点的权值之和就是边 $(x,fa[x])$ 的覆盖次数。

时间复杂度：$O(N+M)$

G. 聚会

先证明一个引理：对于有根树上的三个结点 $x,y,z$，记 $a=LCA(x,y), b=LCA(y,z), c=LCA(z,x)$，则 $a,b,c$ 中至少有两个相同。

引理的证明：假设 $a,b,c$ 两两不同。注意到 $a$ 和 $b$ 都是 $x$ 的祖先，那么 $a$ 和 $b$ 中有一个是另一个的祖先。$b$ 和 $c$，$c$ 和 $a$ 同理。

不妨设 $a$ 是 $b$ 的祖先，$b$ 是 $c$ 的祖先，于是 $b$ 同时是 $x,y,z$ 的祖先，与 $a$ 的最近性矛盾！

回到原题，对于每个询问 $x,y,z$，如果：

1. $x=y=z$，输出“$x$ $0$”。
2. $x,y,z$ 中有两个相等，不妨设 $x=y$，则输出“$x$ $d(x,z)$”。
3. $x,y,z$ 两两不相等，记 $a=LCA(x,y), b=LCA(y,z), c=LCA(z,x)$。
   • 若 $a=b=c$，则输出“$a$ $d(x,a)+d(y,a)+d(z,a)$”；
   • 否则由引理可设 $a=b\ne c$，则输出“$c$ $2 \times d(x,c) + d(z,c)$”。

作业

2. 洛谷：团队作业——LCA（前5题）