📷 题解插图【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3379 【模板】最近公共祖先(LCA)
树结构作为非线性数据结构的核心代表,任意两个节点之间的拓扑亲缘关系判定是图论与树算法的基石。洛谷 P3379「【模板】最近公共祖先(LCA)」是 CCF GESP 七级与 CSP-S 组别中最基础且最重要的经典模板题之一。题目要求在一棵具有 个节点且以 为根的有根多叉树上,高效响应 次关于两点最近公共祖先(Lowest Common Ancestor, LCA)的在线查询。面对 的超大数据规模,朴素的一步步向上追溯(暴力爬树)在退化成长链的树形结构上,单次查询时间复杂度高达 ,整体时间复杂度 会彻底超时(TLE)。攻克海量 LCA 查询的核心利器是树上倍增法(Binary Lifting):基于二进制拆分思想,通过预处理 规模的祖先跃迁表,将两点深度对齐与祖先逼近过程从线性步长压缩至对数阶,实现 单次快速查询;结合广度优先遍历(BFS)预处理更能彻底杜绝深链树递归爆栈的工程隐患。题目洛谷官方难度评级为普及/提高-。
luogu-P3379 【模板】最近公共祖先(LCA)
🔗 洛谷原题传送门:luogu-P3379 【模板】最近公共祖先(LCA)
题目描述
如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 ,分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 行每行包含两个正整数 ,表示 结点和 结点之间有一条直接连接的边(数据保证可以构成树)。
接下来 行每行包含两个正整数 ,表示询问 结点和 结点的最近公共祖先。
输出格式
输出包含 行,每行包含一个正整数,依次为每一个询问的结果。
样例 #1
样例输入 #1
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5样例输出 #1
4
4
1
4
4提示
对于 的数据,,。
对于 的数据,,。
对于 的数据,,,不保证 。
样例说明:
该树结构如下:

第一次询问: 的最近公共祖先,故为 。
第二次询问: 的最近公共祖先,故为 。
第三次询问: 的最近公共祖先,故为 。
第四次询问: 的最近公共祖先,故为 。
第五次询问: 的最近公共祖先,故为 。
故输出依次为 。
2021/10/4 数据更新 @fstqwq:应要求加了两组数据卡掉了暴力跳。
题目深度剖析
1. 朴素算法为何失效?(长链退化与 TLE 瓶颈)
在探讨倍增算法前,先审视最直观的朴素爬树解法:
- 朴素爬树流程:
- 预处理求出每个节点的深度 以及直接父节点 ;
- 若两点深度不同,先让深度较深的节点一步一步向上爬,直到两点处于同一深度;
- 两点同深度后,若两点未重合,则两点同时一步一步向上爬,直至第一次相遇,相遇节点即为 LCA。
- 长链退化反例:若树的拓扑结构退化为一条深度为 的单链(例如 ),根节点为 。若询问链底节点 与节点 的 LCA,单次查询需要向上爬 步。
- 复杂度失控:题目中 。在极端退化数据下,总计算步数高达 次。洛谷官方 2021/10/4 特别加入的长链测试点,正是为了坚决卡掉这种暴力跳跃解法。
2. 二进制拆分与树上倍增(Binary Lifting)核心数学原理
计算机底层依托二进制运行。任意正整数 均可唯一且无遗漏地分解为若干个 2 的非负整数次幂之和:
由此启发我们:若将向上爬一步的线性移动,改造为以 步为基本单位的指数跃迁,则任何距离 的攀爬过程都可以在至多 步内精准完成!
- 状态定义: 设 表示节点 沿树向上跳跃 步所到达的祖先节点编号。若跳跃超出根节点,则将其指向虚拟边界节点 。
- 状态转移递推方程: 由于 ,节点 向上跳 步,等价于先从 向上跳 步到达中转节点 ,再从 继续向上跳 步。因此递推关系为:
- 幂次上界确定: 题目数据中 。因为 且 ,倍增最大幂次选取 (即常量 )即可绝对覆盖树上任意两点之间的最大可能距离。
3. 倍增 LCA 查询的两阶段推进法
对于任意一次询问 ,最近公共祖先的求解严格分为两阶段推进:
-
第一阶段:深度对齐(深节点向浅节点二分靠拢)
- 设两点深度分别为 与 。不妨设 (若不满足则交换 与 )。
- 计算两者的深度差值。从最高幂次 开始向下遍历至 : 若 ,则令 。
- 二进制拆分保证在循环结束后,节点 必然精确提升至与 相同的深度。
- 边界特判:若对齐后发现 ,说明原先较浅的节点 本身就是 的祖先,此时直接返回 即可。
-
第二阶段:同步倍增逼近(保持异名向上跳跃)
- 此时 与 深度严格相等且 。
- 同样从最高幂次 向下递减至 尝试同步跃迁:
- 若 :说明向上跳 步后,两点尚未到达公共祖先(或者尚未相聚),这次跳跃是安全的,执行同步跳跃:;
- 若 :说明向上跳 步后已经到达了某个公共祖先,但该祖先不一定是最近公共祖先(可能跳过了头)。为了不跨越 LCA,此时保持两节点在原地不动,继续尝试更小的幂次步长 。
- 收敛结果:当循环递减至 结束时, 与 必然恰好停在最近公共祖先的正下方直接子节点位置。
- 返回答案:两者的直接父节点 即为所求的最近公共祖先!
4. 工程与竞赛避坑指南:BFS 层序遍历 vs DFS 递归
在树形算法中,许多教材习惯使用深度优先搜索(DFS)递归预处理倍增表。然而在工业级工程与高规格竞赛中,面对 的超大规模数据,DFS 存在致命缺陷:
- DFS 爆栈隐患:若输入数据退化为一条长链,DFS 递归调用栈将深入 500000 层。Linux 环境下默认函数栈通常为 8MB,如此深度的函数调用栈会瞬间导致栈溢出(Stack Overflow,报 SIGSEGV / 运行错误);
- BFS 稳健方案:采用广度优先搜索(BFS)层序遍历。队列动态分配于堆空间中,函数调用栈深度严格保持为 。从给定的根节点 开始,逐层向下拓展,在计算子节点深度的同时同步建立倍增表,彻底规避爆栈风险。
C++11 标准参考程序
/**
* 题目: 【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3379 【模板】最近公共祖先(LCA)
* 题号: P3379
* 归属: GESP七级 / CSP-S / 树论与树上倍增模板题
* 博客: https://www.coderli.com/gesp-7-luogu-p3379/
* 标准: C++11 (严格遵循 CCF GESP 官方规范)
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// 最大节点数量与倍增最大幂次(2^20 > 500000)
const int MAXN = 500005;
const int MAXLOG = 21;
// 邻接表存储树的双向边
vector<int> adj[MAXN];
// depth[i] 记录节点 i 在树中的深度(根节点深度设为 1)
int depth[MAXN];
// parent_node[i][k] 记录节点 i 向上跳 2^k 步所到达的祖先节点编号
int parent_node[MAXN][MAXLOG];
/**
* 广度优先搜索(BFS)层序遍历预处理深度与倍增祖先表
* 工程优势:彻底规避极端退化链状树在递归深搜(DFS)下的调用栈溢出(Stack Overflow)风险
* @param root 树根节点编号
*/
void bfs_init(int root) {
queue<int> q;
depth[root] = 1;
parent_node[root][0] = 0; // 根节点的父节点为 0(虚拟边界)
q.push(root);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
// 跳过通往直接父节点的反向边
if (v == parent_node[u][0]) {
continue;
}
depth[v] = depth[u] + 1;
parent_node[v][0] = u; // v 向上跳 2^0 = 1 步即为直接父节点 u
// 状态转移递推:跳 2^k 步 = 先跳 2^(k-1) 步,再从该中转点跳 2^(k-1) 步
for (int k = 1; k < MAXLOG; ++k) {
parent_node[v][k] = parent_node[parent_node[v][k - 1]][k - 1];
}
q.push(v);
}
}
}
/**
* 树上倍增法查询任意两点 u 和 v 的最近公共祖先(LCA)
* @param u 查询节点编号 1
* @param v 查询节点编号 2
* @return 节点 u 与 v 的最近公共祖先节点编号
*/
int query_lca(int u, int v) {
// 规范化:确保 u 始终为深度更深(或相等)的节点
if (depth[u] < depth[v]) {
swap(u, v);
}
// 第一阶段:深度对齐
// 利用二进制拆分,从大步长向小步长尝试跳跃,使 u 向上提升至与 v 处于同一深度
for (int k = MAXLOG - 1; k >= 0; --k) {
if (depth[u] - (1 << k) >= depth[v]) {
u = parent_node[u][k];
}
}
// 特判边界:若深度对齐后 u 与 v 重合,说明 v 本身就是 u 的祖先
if (u == v) {
return u;
}
// 第二阶段:同步倍增逼近
// 从大到小尝试让 u 与 v 同时向上跳跃 2^k 步
// 若跳跃后的目标节点不相等,说明尚未到达公共祖先或尚未越过 LCA,同步向上跳
for (int k = MAXLOG - 1; k >= 0; --k) {
if (parent_node[u][k] != parent_node[v][k]) {
u = parent_node[u][k];
v = parent_node[v][k];
}
}
// 循环结束后,u 与 v 恰好停在 LCA 的正下方直接子节点
// 其直接父节点 parent_node[u][0] 即为所求的最近公共祖先
return parent_node[u][0];
}
int main() {
int n, m, s;
cin >> n >> m >> s;
// 读入 n - 1 条无向树边构建邻接表
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// 从根节点 s 开始层序遍历初始化
bfs_init(s);
// 处理 m 次 LCA 查询
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
cout << query_lca(a, b) << "\n";
}
return 0;
}算法复杂度全面分析
-
时间复杂度分析:
- 邻接表建图:读入 条双向边,耗时 ;
- BFS 层序预处理:共有 个节点进入队列一次,每个节点计算 次倍增跳转,预处理耗时 ;
- 单次 LCA 查询:深度对齐耗时 ,同步逼近耗时 ,单次查询总耗时为严格的 ;
- 总查询时间:响应 次查询耗时 ;
- 整体时间复杂度:。代入 与 ,基本操作规模约 次,远在 1 秒时限内平稳运行。
-
空间复杂度分析:
- 图的邻接表存储:无向树包含 条有向边,
adj数组空间为 ; - 倍增数组:
parent_node[MAXN][MAXLOG]大小为 ; - 深度数组与辅助队列:
depth数组与 BFS 队列空间为 ; - 整体空间复杂度:,整机内存消耗约 ,完全符合洛谷 512MB 的内存限制。
- 图的邻接表存储:无向树包含 条有向边,
所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P1113 [USACO02FEB] 杂务
生活与工业生产中的工序流水线调度,天然蕴含着严苛的时序依赖:地基未筑不可起高楼,原料未至不可开炉灶。洛谷 P1113「[USACO02FEB] 杂务」以牧场日常作业为背景,生动抽象出工程管理与图论中的核心模型——有向无环图(DAG)的关键路径与最早完成时间计算(Crit...
【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3371 【模板】单源最短路径(弱化版)
在交通网络寻径、物流供应链调度与通信路由协议中,求解从指定始发枢纽到网络中所有连通节点的最优开销,是离散优化与图论的核心基石。洛谷 P3371「【模板】单源最短路径(弱化版)」给出了非负权有向图单源最短路径(Single-Source Shortest Path, SS...
【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3366 【模板】最小生成树
在通信基站管网布线、电力网架设以及交通枢纽规划等重大工程中,如何在保证所有节点相互连通的前提下,使铺设线路的总建设开销(边权之和)达到全局最小,是经典的最小生成树(Minimum Spanning Tree, MST)离散优化问题。洛谷 P3366「【模板】最小生成树」...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

