专栏文章

题解：P3379 【模板】最近公共祖先（LCA）

BBrute_Force
P3379题解参与者 28已保存评论 34

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
34 条
当前快照
1 份
快照标识符
@miptoxfk
此快照首次捕获于
2025/12/03 17:46
3 个月前
此快照最后确认于
2025/12/03 17:46
3 个月前
查看原文

算法介绍

本题解介绍倍增法求 LCA。

倍增法

倍增法的本质是通过已知的一段内容，将该内容求解的范围扩大一倍，进而求解整个问题，从而提升程序效率。

倍增法求解 LCA

我们令 fi,jf_{i,j} 表示节点 ii 向上跳 2j2^j 步，所到的节点。显然，fi,0f_{i,0} 表示节点 ii 的父亲节点。
现在有了初始化，那么我们就有了求解所有 fi,jf_{i,j} 的基础。想要求解每一个 ii 节点跳 2j2^j 到的节点，等同于 ii 节点先往上跳 2j−12^{j-1} 步到的节点，再往上跳 2j−12^{j-1} 步到的最终节点。由上述描述，可得递推式： fi,j=ffi,j−1,j−1f_{i,j} = f_{f_{i,j-1},j-1}
注意，往上跳的过程中，不能跳出根节点。
求解 LCA 时，只需将两个节点拉直同一深度，如果两个节点相同，则返回两者之间任一节点，否则一起往上跳相同步数直至求出 LCA 为止。

正确性证明

时间复杂度证明

预处理时，对于 nn 个节点在不跳出根节点的情况下，每次最多循环 log⁡n\log n 次。预处理复杂度 O(nlog⁡n)O(n \log n)。
每次查询时，最坏情况下两个深度最高的节点的 LCA 是根节点，拉至 LCA 的总时间复杂度为 O(log⁡n)O(\log n)。

递推式证明

如果程序在求解 11 到 nn 跳跃 2j2^j 步达到的节点，必然求解了 11 到 nn 跳跃 2j−12^{j-1} 步的节点。所以递推式正确。
本棵树边界条件是条链，因此，一个节点最多跳的步数小于 nn。

查询证明

一个节点到另一个节点的深度是唯一确定的，因此跳跃的步数也是唯一确定的。所以相同深度的两个节点到 LCA 的步数也是相同的。而我们已经用倍增法记录下了每个 fi,jf_{i,j}，所以该算法是正确的。

代码实现

对于每一个节点 ii 求 fi,0f_{i,0}，我们可以直接用 DFS 求解，并记录下此时节点 ii 的深度以及 fi,0f_{i,0}。代码如下：
CPP
inline void dfs (int u, int fa) {
	f[u][0] = fa;//记录父亲节点
	dep[u] = dep[fa] + 1;//记录深度
	for (auto v : e[u])
		if (v != fa) dfs (v, u);
}
对于求解每一个 fi,jf_{i,j}，代码如下：
CPP
inline void init () {
	for (int j = 1; (1 << j) <= n; ++j)//边界范围
		for (int i = 1; i <= n; ++i)
			f[i][j] = f[f[i][j - 1]][j - 1];
}
接下来是核心的求解 LCA，代码如下：
CPP
inline int lca (int u, int v) {
	if (dep[u] < dep[v]) swap (u, v);
	for (int i = 22; i >= 0; i--) {
		if (dep[f[u][i]] >= dep[v]) u = f[u][i];
	}//跳至同一深度
	if (u == v) return u;//此时节点为 LCA
	for (int i = 22; i >= 0; i--) {
		if (f[u][i] != f[v][i]) {
			u = f[u][i];
			v = f[v][i];
		}
	}//一起往上跳
	return f[u][0];
}
完整代码如下：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
int n, m, s, f[N][33], dep[N];
vector <int> e[N];
bool vis[N];
inline void dfs (int u, int fa) {
	f[u][0] = fa;
	dep[u] = dep[fa] + 1;
	for (auto v : e[u])
		if (v != fa) dfs (v, u);
}//求 f[i][0]
inline int lca (int u, int v) {
	if (dep[u] < dep[v]) swap (u, v);
	for (int i = 22; i >= 0; i--) {
		if (dep[f[u][i]] >= dep[v]) u = f[u][i];
	}
	if (u == v) return u;
	for (int i = 22; i >= 0; i--) {
		if (f[u][i] != f[v][i]) {
			u = f[u][i];
			v = f[v][i];
		}
	}
	return f[u][0];
}//求两个节点的 LCA
inline void init () {
	for (int j = 1; (1 << j) <= n; ++j)
		for (int i = 1; i <= n; ++i)
			f[i][j] = f[f[i][j - 1]][j - 1];
}//求 f[i][j]
int main () {
	ios :: sync_with_stdio (0);
	cin.tie (0), cout.tie (0);
	cin >> n >> m >> s;
	for (int i = 1; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		e[x].push_back (y);
		e[y].push_back (x);
	}
	dfs (s, 0);
	init ();
	for (int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		cout << lca (u, v) << "\n";
	}
	return 0;
}

评论

共 34 条评论，欢迎与作者交流。

正在加载评论...