最近公共祖先

参考资料

• 最近公共祖先 - OI Wiki

简介

最近公共祖先（Lowest Common Ancestor，LCA）指两个点的公共祖先中距离根节点最远的点。

倍增

预处理每个点的 $2^k$ 级祖先 $a_{u,k}$，查询时先把较深的点跳到与另一点同深度，若已重合则得到答案，否则两点一起从高位向上跳到 LCA 的下一层。预处理 $O(n\log n)$，单次查询 $O(\log n)$。

245 Bcpp

int lca(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);
	for(int i=20;i>=0;i--)
	{
		if(dep[a[u][i]]>=dep[v])u=a[u][i];
	}
	if(u==v)return u;
	for(int i=20;i>=0;i--)
	{
		if(a[u][i]!=a[v][i])
		{
			u=a[u][i];
			v=a[v][i];
		}
	}
	return a[u][0];
}

树链剖分

基于树链剖分：两点不在同一条重链上时，把链顶较深的那个点跳到链顶的父亲，重复直到同链，此时深度较小者即为 LCA。预处理 $O(n)$，单次查询 $O(\log n)$。

136 Bcpp

int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}

例题

洛谷 P3379 【模板】最近公共祖先（LCA）

给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。