最近公共祖先（LCA）学习笔记

给定一棵树，求任意两点的 $\operatorname{lca}$ ，不需要支持带修。

这是一个十分常见的问题，这里总结一下目前常用的几种做法。

倍增（ $O(n\log n+q\log n)$ ）

最常用的方法，用 $up_{u,i}$ 记录 $u$ 的第 $2^i$ 级祖先，用 $dep_u$ 记录 $u$ 的深度，显然这两个东西可以一遍 $dfs$ 在 $O(n\log n)$ 的时间复杂度内求出来。

每次询问 $\operatorname{lca}(x,y)$ 的时候先倍增让深度大的那个点跳到深度和另外一个点的深度相同的祖先，然后两个点一起倍增往上跳即可。

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

代码如下：

void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1;
	up[u][0]=fa;
	for(int i=1;i<=25;i++) up[u][i]=up[up[u][i-1]][i-1];
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs(v,u);
	}
}

inline int quelca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=25;i>=0;i--) if(dep[up[x][i]]>=dep[y]) x=up[x][i];
	if(x==y) return x;
	for(int i=25;i>=0;i--) if(up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i];
	return up[x][0];
}

dfs 序（ $O(n\log n+q)$ ）

目前主流的还是欧拉序求 $\operatorname{lca}$ ，但是其实 dfs 序也可以，而且时间空间常数码量等等都吊打欧拉序。

思考欧拉序为什么能 $\operatorname{rmq}$ 求 $\operatorname{lca}$ ，显然是因为 $x,y$ 和 $\operatorname{lca}(x,y)$ 映射到欧拉序之后 $\operatorname{lca}(x,y)$ 一定在两点之间，而映射到 dfs 序之后却没有这个性质。

但是 dfs 序也有一个看似无用的性质：祖先一定出现在后代之前。

为了表述方便，设 $pos_u$ 表示节点 $u$ 在 dfs 序中的位置，设 $dep_u$ 表示节点 $u$ 的深度，并且下文假定 $pos_x<pos_y$ 。

接下来分情况讨论：

$x$ 不是 $y$ 的祖先

设 $\operatorname{lca}(x,y)=r$ ，那么显然有 $pos_r<pos_x$ 。显然此时 dfs 的顺序是从 $r$ 下降到 $x$ ，再回到 $r$ ，下降到 $y$ 。

考虑 $r$ 的 $y$ 方向的儿子，即 $r$ 的满足 $y$ 在 $u$ 子树内的儿子 $u$ ，那么由于需要先回到 $r$ 才能在下降到 $y$ 的过程中经过 $u$ ，所以一定有 $pos_x<pos_u\le pos_y$ ，也就是说在 dfs 序中 $u$ 会出现在 $x$ 和 $y$ 中间。

那么找到 dfs 序 $[pos_x,pos_y]$ 区间内深度最小的点的父亲即可。
$x$ 是 $y$ 的祖先

虽然这种情况可以很方便地特判掉，但是这样不够优美。

依旧考虑 $x$ 的 $y$ 方向的儿子 $u$ ，那么一定有 $pos_x<pos_u\le pos_y$ ，那么找到 dfs 序 $[pos_x+1,pos_y]$ 区间内深度最小的点的父亲即可。

观察到就算 $x$ 不是 $y$ 的祖先，查询 $[pos_x+1,pos_y]$ 区间内深度最小的点的父亲也可以得到 $\operatorname{lca}(x,y)$ ，所以直接对于所有情况都查询 $[pos_x+1,pos_y]$ 区间内深度最小的点的父亲，唯一需要特判的情况只有 $x=y$ 。

那么解法就很显然了，用倍增 $O(n\log n)$ 预处理 dfs 序某个区间中 $dep_u$ 最小的点 $u$ 即可做到 $O(n\log n+q)$ 。

代码如下：

int tot,dep[S],fat[S],a[S],pos[S];
int mylog[S],mn[S][30];
void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;
    fat[u]=fa;
    a[++tot]=u;
    pos[u]=tot;
    for(int i=h[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==fa) continue;
        dfs(v,u);
    }
}
inline void init(int rt)
{
    dfs(rt,0);
    mylog[0]=-1;
    for(int i=1;i<=n;i++) mylog[i]=mylog[i>>1]+1;
    for(int i=1;i<=n;i++) mn[i][0]=a[i];
    for(int j=1;j<=mylog[n];j++)
    {
        for(int i=1;i<=n-(1<<j)+1;i++)
        {
            mn[i][j]=dep[mn[i][j-1]]<dep[mn[i+(1<<j-1)][j-1]]?mn[i][j-1]:mn[i+(1<<j-1)][j-1];
        }
    }
}
inline int quelca(int x,int y)
{
    if(x==y) return x;
    if(pos[x]>pos[y]) swap(x,y);
    int l=pos[x]+1,r=pos[y];
    int k=mylog[r-l+1];
    int u=dep[mn[l][k]]<dep[mn[r-(1<<k)+1][k]]?mn[l][k]:mn[r-(1<<k)+1][k];
    return fat[u];
}

树链剖分（ $O(n+q\log n)$ ，支持换根操作）

前置知识：树链剖分学习笔记

完成剖分之后每次暴力跳重链即可。

树链剖分还可以支持换根操作，具体详见：换根树剖学习笔记

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

Tarjan（ $O(n+q)$ ，离线）

有些恶心的题目数据范围太大，带 $\log$ 的时间复杂度都过不去，那么此时就需要用 tarjan 来离线求 $\operatorname{lca}$ 。

考虑 $x$ 和 $y$ 和它们的 $\operatorname{lca}(x,y)=d$ 在对整棵树进行 dfs 遍历时的访问顺序，显然是先从 $d$ 下降到 $x,y$ 中的某一个点，再回到 $d$ ，然后下降到另外一个点。

设一个点 $u$ “完成了”当且仅当 $u$ 的整棵子树都遍历完成了，若我们每次“完成”一个点之后就把它子树内的点集并入它的父亲的点集，那么显然 $d$ 即为 $x$ 和 $y$ 都“完成”时“完成”得较早的那个点所处的集合内深度最小的那个点。

那么把询问离线下来，然后用并查集维护即可。

代码如下：

int tot;
int xs[S],ys[S],ans[S];
vector<int> ques[S];
int fa[S];
bool vis[S];
inline void quelca(int x,int y)
{
	xs[++tot]=x;
	ys[tot]=y;
	ques[x].push_back(tot),ques[y].push_back(tot);
}
inline int fnd(int x)
{
	return fa[x]==x?x:fa[x]=fnd(fa[x]);
}
inline void meg(int x,int y)
{
	int rx=fnd(x),ry=fnd(y);
	fa[rx]=ry;
}
void dfs(int u,int fa)
{
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs(v,u);
		meg(v,u);
	}
	vis[u]=true;
	for(int qid:ques[u])
	{
		int v=u==xs[qid]?ys[qid]:xs[qid];
		if(vis[v]) ans[qid]=fnd(v);
	}
}
void flush(int rt)
{
	for(int i=1;i<=n;i++) fa[i]=i;
	dfs(rt,0);
}

总结 & 完整模板

一般情况下，倍增求 $\operatorname{lca}$ 和 dfs 序求 $\operatorname{lca}$ 已经足够。

在需要换根的情况下，只能用树剖求 $\operatorname{lca}$ 。

在需要卡常的情况下，若询问数较少，常数优秀的树剖求 $\operatorname{lca}$ 比 Tarjan 求 $\operatorname{lca}$ 还要快，但是若询问数非常多，那么 Tarjan 求 $\operatorname{lca}$ 还是有必要的。

在强制在线并且要卡常的情况下，常数优秀的树剖求 $\operatorname{lca}$ 是唯一的选择。

完整模板：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=1000005;

int n,q,rot;
int esum,to[S],nxt[S],h[S];

inline void add(int x,int y)
{
	to[++esum]=y;
	nxt[esum]=h[x];
	h[x]=esum;
}

namespace BZ
{
	int dep[S],up[S][30];
	void dfs(int u,int fa)
	{
		dep[u]=dep[fa]+1;
		up[u][0]=fa;
		for(int i=1;i<=25;i++) up[u][i]=up[up[u][i-1]][i-1];
		for(int i=h[u];i;i=nxt[i])
		{
			int v=to[i];
			if(v==fa) continue;
			dfs(v,u);
		}
	}
	inline int quelca(int x,int y)
	{
		if(dep[x]<dep[y]) swap(x,y);
		for(int i=25;i>=0;i--) if(dep[up[x][i]]>=dep[y]) x=up[x][i];
		if(x==y) return x;
		for(int i=25;i>=0;i--) if(up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i];
		return up[x][0];
	}
}

namespace DFS
{
	int tot,dep[S],fat[S],a[S],pos[S];
	int mylog[S],mn[S][30];
	void dfs(int u,int fa)
	{
		dep[u]=dep[fa]+1;
		fat[u]=fa;
		a[++tot]=u;
		pos[u]=tot;
		for(int i=h[u];i;i=nxt[i])
		{
			int v=to[i];
			if(v==fa) continue;
			dfs(v,u);
		}
	}
	inline void init(int rt)
	{
		dfs(rt,0);
		mylog[0]=-1;
		for(int i=1;i<=n;i++) mylog[i]=mylog[i>>1]+1;
		for(int i=1;i<=n;i++) mn[i][0]=a[i];
		for(int j=1;j<=mylog[n];j++)
		{
			for(int i=1;i<=n-(1<<j)+1;i++)
			{
				mn[i][j]=dep[mn[i][j-1]]<dep[mn[i+(1<<j-1)][j-1]]?mn[i][j-1]:mn[i+(1<<j-1)][j-1];
			}
		}
	}
	inline int quelca(int x,int y)
	{
		if(x==y) return x;
		if(pos[x]>pos[y]) swap(x,y);
		int l=pos[x]+1,r=pos[y];
		int k=mylog[r-l+1];
		int u=dep[mn[l][k]]<dep[mn[r-(1<<k)+1][k]]?mn[l][k]:mn[r-(1<<k)+1][k];
		return fat[u];
	}
}

namespace TARJAN
{
	int tot;
	int xs[S],ys[S],ans[S];
	vector<int> ques[S];
	int fa[S];
	bool vis[S];
	inline void quelca(int x,int y)
	{
		xs[++tot]=x;
		ys[tot]=y;
		ques[x].push_back(tot),ques[y].push_back(tot);
	}
	inline int fnd(int x)
	{
		return fa[x]==x?x:fa[x]=fnd(fa[x]);
	}
	inline void meg(int x,int y)
	{
		int rx=fnd(x),ry=fnd(y);
		fa[rx]=ry;
	}
	void dfs(int u,int fa)
	{
		for(int i=h[u];i;i=nxt[i])
		{
			int v=to[i];
			if(v==fa) continue;
			dfs(v,u);
			meg(v,u);
		}
		vis[u]=true;
		for(int qid:ques[u])
		{
			int v=u==xs[qid]?ys[qid]:xs[qid];
			if(vis[v]) ans[qid]=fnd(v);
		}
	}
	void flush(int rt)
	{
		for(int i=1;i<=n;i++) fa[i]=i;
		dfs(rt,0);
	}
}

int main()
{
	scanf("%d%d%d",&n,&q,&rot);
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
//	BZ::dfs(rot,0);
//	DFS::init(rot);
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
	//	printf("%d\n",BZ::quelca(x,y));
	//	printf("%d\n",DFS::quelca(x,y));		
		TARJAN::quelca(x,y);
	}
	TARJAN::flush(rot);
	for(int i=1;i<=TARJAN::tot;i++) printf("%d\n",TARJAN::ans[i]);
	return 0;
}

最近公共祖先（LCA）学习笔记

倍增（O(nlog⁡n+qlog⁡n)O(n\log n+q\log n)O(nlogn+qlogn)）

dfs 序 （O(nlog⁡n+q)O(n\log n+q)O(nlogn+q)）

树链剖分（O(n+qlog⁡n)O(n+q\log n)O(n+qlogn)，支持换根操作）

Tarjan（O(n+q)O(n+q)O(n+q)，离线）

总结 & 完整模板

感谢您的支持，我会继续努力的!

倍增（ $O(n\log n+q\log n)$ ）

dfs 序（ $O(n\log n+q)$ ）

树链剖分（ $O(n+q\log n)$ ，支持换根操作）

Tarjan（ $O(n+q)$ ，离线）