题解：P3379 【模板】最近公共祖先（LCA）
mazhenhao0235 · · 题解
一、LCA问题概述
最近公共祖先（Lowest Common Ancestor ，简称 LCA）是树结构中的一个基本问题，指在一棵有根树中，两个节点的公共祖先中深度最大的那个节点。 LCA 问题在树结构相关算法中有着广泛的应用，如计算树上两点间路径、解决树上的查询问题等。
二、多种 LCA 求解算法详解
1.朴素算法（暴力跳转法）
基本思路：
- 将两个节点调整到同一深度
- 然后同时向上跳转，直到相遇
实现步骤：
- 计算两个节点的深度差
- 较深的节点向上跳转深度差步
- 两个节点同时向上跳转，直到相遇
复杂度分析：
- 预处理：无（或
O(n) 计算深度） - 查询：最坏
O(n)
优缺点：
- 优点：实现简单
- 缺点：查询效率低，不适用于大规模数据
2. 倍增算法
基本思路：
- 预处理每个节点向上
2^k 层的祖先 - 利用二进制拆分思想快速跳转
实现步骤：
1.预处理每个节点的
2.查询时先将两个节点调整到同一深度
3.然后尝试以
关键代码：
int LCA(int x, int y) {
if(dep[x] < dep[y]) swap(x,y);
for(int i=20; i>=0; i--)
if(dep[fa[x][i]] >= dep[y])
x = fa[x][i];
if(x == y) return x;
for(int i=20; i>=0; i--)
if(fa[x][i] != fa[y][i])
x=fa[x][i], y=fa[y][i];
return fa[x][0];
}复杂度分析：
- 预处理
O(nlogn) - 查询
O(logn)
优缺点：
- 优点：查询效率高
- 缺点：预处理空间复杂度较高
3. Tarjan离线算法
基本思路：
- 利用并查集和 DFS 遍历
- 离线处理所有查询
实现步骤：
- 对树进行 DFS 遍历
- 使用并查集维护已访问节点
- 在处理完一个节点的子树后，处理与该节点相关的查询
复杂度分析：
- 时间复杂度：
O(nα(n)) （近似线性） - 需要离线处理所有查询
优缺点：
- 优点：时间复杂度优秀
- 缺点：必须离线处理，实现较复杂
4. 树链剖分算法（本题解法）
基本思想：
- 将树划分为若干条链
- 利用链的性质加速查询
核心概念：
- 重儿子：子树大小最大的儿子
- 轻儿子：其他儿子
- 重链：由重儿子连接形成的链
实现步骤：
第一次 DFS ：
void dfs1(int u, int fat) {
siz[u] = 1; // 初始化子树大小为1
dep[u] = dep[fat] + 1; // 计算深度
fa[u] = fat; // 记录父节点
for(auto v : g[u]) {
if(v == fat) continue;
dfs1(v, u);
siz[u] += siz[v]; // 累加子树大小
if(siz[v] > siz[heavy[u]])
heavy[u] = v; // 更新重儿子
}
}第二次 DFS ：
void dfs2(int u, int tp) {
top[u] = tp; // 记录链顶
dfn[u] = ++idx; // 记录DFS序
if(!heavy[u]) return; // 叶子节点返回
dfs2(heavy[u], tp); // 优先处理重儿子（保证重链连续）
for(auto v : g[u])
if(v != fa[u] && v != heavy[u])
dfs2(v, v); // 轻儿子作为新链的起点
}LCA查询
int LCA(int x, int y) {
while(top[x] != top[y]) { // 当两个节点不在同一条链上
if(dep[top[x]] < dep[top[y]])
swap(x, y); // 选择链顶较深的链
x = fa[top[x]]; // 跳到链顶的父节点
}
return dep[x] < dep[y] ? x : y; // 返回深度较小的节点
}复杂度分析：
- 预处理：两次 DFS ，
O(n) - 查询：
O(logn) （因为树被剖分成O(logn) 条链
优势：
- 预处理时间与空间复杂度优秀
- 查询效率高且稳定
- 可以同时支持其他树路径操作
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, s, u, v, x, y;
int siz[N], heavy[N], fa[N], top[N], dep[N];
vector<int> g[N];
void dfs1(int u, int fat) {
siz[u] = 1;
dep[u] = dep[fat] + 1;
fa[u] = fat;
for(auto v : g[u]) {
if(v == fat) continue;
dfs1(v, u);
siz[u] += siz[v];
if(siz[v] > siz[heavy[u]]) heavy[u] = v;
}
}
void dfs2(int u, int tp) {
top[u] = tp;
if(!heavy[u]) return;
dfs2(heavy[u], tp);
for(auto v : g[u])
if(v != fa[u] && v != heavy[u]) dfs2(v, v);
}
int LCA(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> s;
for(int i = 1; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(s, 0);
dfs2(s, s);
while(m--) {
cin >> x >> y;
cout << LCA(x, y) << '\n';
}
return 0;
}算法核心思想
树链剖分通过将树分解为多条链来加速 LCA 查询。其核心在于：
- 重链剖分：将树划分为若干条"重链"，使得从任意节点到根的路径最多经过
O(logn) 条链 - 跳跃查询：通过在这些链上跳跃，快速找到 LCA
总结
树链剖分是解决LCA问题的高效算法，通过两次DFS预处理将树划分为重链，使得每次查询可以在
O(logn) 时间内完成。相比倍增算法，它的预处理时间更优（O(n) vsO(nlogn) ） ，且实际运行效率更高。