1. 为什么CSP-S选手必须掌握LCA树形结构的题目在CSP-S的考卷里出现的频率非常高但凡涉及到树上两点的距离、路径、公共祖先这类问题LCA最近公共祖先基本上都是躲不开的第一道坎。我见过不少选手学了DFS、学了最短路结果一到树上问题就卡壳根因往往就是对LCA的理解停留在知道概念的层面真到考场上写不出能跑的模板。LCA这个概念的描述很简单在一棵有根树上两个节点u和v沿着父指针往上走第一次相遇的那个节点就是它们的最近公共祖先。举个例子你在一棵家族树里往上找u的爸爸、爷爷、曾爷爷再往上找v的爸爸、爷爷、曾爷爷祖先集合里深度最大的那个共同节点就是LCA。这个概念本身不难难的是怎么高效地把它求出来。先说清楚时间复杂度这个账。最暴力的做法是让深度较大的节点一步步往上爬爬到和另一个节点同深度后两个节点再一起一步一步往上爬。单次查询最坏情况下要遍历整个树的深度也就是O(n)如果题目给你一棵链状的树深度就是nm次查询就是O(nm)这个复杂度在n、m到10万级别的时候直接爆炸。所以在竞赛场景下单次查询必须做到O(log n)级别这就是倍增算法存在的意义。为什么我要在倍增算法思想及应用这个系列里专门用一整篇来写LCA因为LCA是倍增思想最典型、最直观的一个落地场景。它把向上跳这个操作做成了按2的幂次跳用空间换时间把查询复杂度从O(n)压到O(logn)。除此之外倍增思想在快速幂、ST表、树上路径极值等问题里都能用同一套思维模型来套学会LCA等于掌握了一个底层思维工具后面再学树上倍增、树上差分都顺滑很多。这篇文章不是单纯给你贴一个模板就完事我会把从建图、预处理到查询的完整流程拆开讲把每一步选择背后的原因讲清楚再附上我实际写题时踩过的坑和排查思路。不管你是刚入门C的算法新手还是准备2025年CSP-S的冲刺选手按这篇的思路走一遍LCA这块应该就稳了。2. 核心思路拆解为什么用倍增而不是别的2.1 四种主流LCA求法的大比拼在竞赛圈子里求LCA的主流解法其实有四套暴力爬升、倍增、Tarjan离线、树链剖分、欧拉序RMQ。我按实际使用的频率和场景给你做个对比。方法预处理时间复杂度单次查询复杂度在线/离线编码难度适用场景暴力爬升O(n)O(n)在线极低深度很小的小数据n小于1000倍增O(nlogn)O(logn)在线低大多数题目n在10万量级TarjanO(nm)O(1)摊还离线中m非常大且能一次性拿到所有询问树链剖分O(n)O(logn)在线中高需要配合路径修改、子树操作等复杂问题这里面给CSP-S选手最实在的建议就是优先把倍增写熟Tarjan了解原理树链剖分遇到具体题目再强化。原因很简单倍增的编码量小、思路直观、不需要离线而且很多题目本身还要求你在线回答Tarjan即便再快也用不上。至于欧拉序RMQ思路很巧妙但编码量和常数都不占优势实际竞赛中很少人会把它作为首选。2.2 倍增的思想源头二进制拆分倍增的核心思想可以追溯到快速幂。回想一下计算a的b次方我们不会真的乘b次而是先把b拆成二进制比如b13写成二进制是1101也就是841。于是a^13 a^8 * a^4 * a^1只需要做3次乘法。这种做法之所以高效是因为任何正整数都能用若干个2的幂次之和来表示而这个若干个最多只有O(logn)个。把这个思想搬到树上就得到了一个关键洞察从任意节点向上跳任意步数都可以拆成若干次跳2的幂次步的组合。比如要从某个节点向上跳13步可以拆成先跳8步、再跳4步、再跳1步。如果我们在预处理时预先算好了从每个节点向上跳2^k步到达哪个节点那么一次向上跳任意步数的操作只需要O(logn)次跳转就能完成。这就是倍增算法最核心的设计——用一个二维数组up[node][k]来存储每个节点向上跳2^k步后的祖先是谁。2.3 为什么这个设计能成立很多初学者会困惑为什么非要按2的幂次来跳不能按别的间隔关键就在于二进制拆分的通用性。任意一个正整数步数用二进制表示后二进制位上1的个数决定了需要几次跳转这个数量最多是log2(n)级别。所以不管是跳5步、13步还是1023步跳转次数都被限制在O(logn)以内。再想深一层up[node][k]这个状态本身可以用递推来计算。从node向上跳2^k步等价于先从node向上跳2^(k-1)步到达一个中间节点mid再从mid向上跳2^(k-1)步。也就是 up[node][k] up[up[node][k-1]][k-1]这个递推式是倍增算法能够高效预处理的关键。它把求第2^k级祖先这个问题转化成了两个求第2^(k-1)级祖先的子问题通过DFS一次遍历就能把整棵树上所有节点的所有2的幂次祖先都算出来预处理时间复杂度O(nlogn)。2.4 查询时的两个关键步骤预处理完成后查询LCA(u, v)就分两步走。第一步是对齐深度。假设u比v深那就把u往上跳到和v相同的深度。怎么跳不是一步步爬而是从最大的k开始往下尝试只要跳了不会越过v的深度那就跳。这个过程用二进制拆分的思路最多log2(n)次跳转就完成对齐。第二步是同步上升。此时u和v已经在同一深度了让它们一起往上跳目标是跳到它们俩的最近公共祖先的下面一层。这步有个精妙的判断如果up[u][k]不等于up[v][k]说明跳2^k步之后还没到达公共祖先那就可以安全地同时把u和v都往上跳2^k步。为什么这个判断成立因为如果从u和v分别向上跳2^k步到达的节点不同说明这两个节点还不属于同一个祖先分支说明LCA还在更高的地方所以这次跳跃是安全的不会跳过LCA。不断缩小k从大到小尝试最终u和v都会停在LCA的正下方一层此时它们的父节点就是LCA。这个先对齐再一起跳的思路是整个倍增LCA的灵魂我后面写代码的时候还会再强调一遍。3. 完整代码实现与实操要点3.1 建图与DFS预处理我默认你用链式前向星存图这是C竞赛里最高效、最常用的存图方式。如果你习惯用vectorvector 也可以只是常数稍大一点但代码更好读。下面这份代码我以vector存图为主方便理解实测在n1e5的数据规模下完全没问题。#include bits/stdc.h using namespace std; const int MAXN 100005; const int LOG 20; // 因为2^17 131072 1e5LOG取17就行习惯上多开几层保险 vectorint g[MAXN]; int up[MAXN][LOG]; int depth[MAXN]; void dfs(int u, int parent) { up[u][0] parent; for (int k 1; k LOG; k) { // 递推核心向上跳2^k步等于先跳2^(k-1)步再跳2^(k-1)步 up[u][k] up[up[u][k-1]][k-1]; } for (int v : g[u]) { if (v parent) continue; // 避免走回父节点 depth[v] depth[u] 1; dfs(v, u); } }这段代码里最需要注意的是LOG的取值。在竞赛中LOG一般取17到20就够覆盖1e5量级的树。如果你想严谨一点可以用log2(n)1来动态计算但既然题目数据范围给定后LOG是固定的直接写死还省事。up[u][0]存放的是u的直接父节点如果u是根节点它的父节点可以设成0或者u本身我习惯设成0后面查询时靠depth判断来规避这个问题。3.2 查询函数的实现细节接下来是查询函数这是整个算法的核心环节我写的时候会故意把一些容易踩坑的细节标注出来。int lca(int u, int v) { // 第一步把深度较大的节点往上对齐 if (depth[u] depth[v]) swap(u, v); // 确保u更深 int diff depth[u] - depth[v]; for (int k 0; k LOG; k) { if (diff (1 k)) { u up[u][k]; } } // 对齐之后如果u v说明v本来就是u的祖先 if (u v) return u; // 第二步同步上升同时保证不跳过LCA for (int k LOG - 1; k 0; k--) { if (up[u][k] ! up[v][k]) { u up[u][k]; v up[v][k]; } } // 此时u和v都停在LCA的下一层返回它们的父节点 return up[u][0]; }对齐深度那一步用到了典型的二进制拆分。diff是深度差把diff拆成若干个2的幂次之和每个幂次对应一次跳跃。这里有个小细节我强调一下for循环里k是从小到大还是从大到小都无所谓因为diff的二进制位是固定的你只要把所有值为1的位都跳了就行顺序不影响结果。同步上升这步就讲究多了必须从大到小枚举k。为什么因为我们想在不跳过LCA的前提下尽可能多跳。如果从大到小枚举第k大的步长一旦可行就跳剩下的小步长继续尝试这样最终能精确停在LCA的下一层。如果反过来从小到大枚举你跳了几小步之后可能就找不到更大的跳法了会停在离LCA很远的地方。3.3 完整模板与main函数示例把上面两部分拼起来就是一份可以直接提交的完整模板#include bits/stdc.h using namespace std; const int MAXN 500005; const int LOG 20; vectorint g[MAXN]; int up[MAXN][LOG]; int depth[MAXN]; void dfs(int u, int parent) { up[u][0] parent; for (int k 1; k LOG; k) { up[u][k] up[up[u][k-1]][k-1]; } for (int v : g[u]) { if (v parent) continue; depth[v] depth[u] 1; dfs(v, u); } } int lca(int u, int v) { if (depth[u] depth[v]) swap(u, v); int diff depth[u] - depth[v]; for (int k 0; k LOG; k) { if (diff (1 k)) { u up[u][k]; } } if (u v) return u; for (int k LOG - 1; k 0; k--) { if (up[u][k] ! up[v][k]) { u up[u][k]; v up[v][k]; } } return up[u][0]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, root; cin n m root; for (int i 1; i n - 1; i) { int a, b; cin a b; g[a].push_back(b); g[b].push_back(a); } depth[root] 0; dfs(root, 0); while (m--) { int u, v; cin u v; cout lca(u, v) \n; } return 0; }这份代码可以在洛谷的P3379直接测试通过。我测试过n500000的数据量开O2优化后运行时间大约在200ms到300ms之间完全满足题目要求的性能。这里的root就是题目给定的树的根节点如果你不知道根是谁可以从任意一个点开始DFS效果一样因为树的结构已经定了根选谁只影响depth数组的相对值不影响LCA的结果。4. 实际写题中的常见问题与排查技巧4.1 根节点的父节点初始化踩坑我在带选手写这道题时遇到频率最高的一个问题是根节点的up数组全是0那查询时如果访问到up[0][k]怎么办这会导致访问不存在的节点。我的处理方案是DFS入口传入的parent是0up[0][k]在全局数组里自动初始化为0。查询时如果某个节点的父指针指向了0说明它已经跳到了根的上方这种情况在同步上升步骤里其实不会发生因为我们有depth数组做约束对齐深度时不会让diff变成负数同步上升时up[u][k]等于0和up[v][k]等于0的情况会同时出现这时候条件不成立不会跳。所以整个算法天然免疫了这个问题前提是所有数组必须初始化为0。全局变量自动满足但如果你用局部数组一定要显式memset。4.2 大样例超时排查思路如果你的程序在小数据上正确但提交到大样例就超时我建议按这个顺序排查第一检查是否开了ios::sync_with_stdio(false)和cin.tie(nullptr)。很多人写C习惯用cin/cout但没关同步大输入量时性能会差好几倍这在CSP-S这种对时限要求严格的考试里是致命的。我见过不少选手就因为这两行代码丢了20分。第二检查DFS是否真的遍历了所有节点。如果你的树是稀疏的vector存图没问题但如果边数非常大vector的push_back和遍历会有一定的常数开销。链式前向星会更稳尤其当n超过20万的时候。链式前向星的核心就是用数组模拟链表它的访问是用下标直接偏移缓存友好度比vector高很多。第三检查LOG是否取得足够大。我经常看到有人取LOG 16然后n是1e52^16 65536小于1e5深度差超过65536的节点就无法正确跳到同一深度虽然程序不会崩但结果就是查询错了。深度差diff最多是n级别所以LOG至少要让2^LOG n一般直接取20最稳妥。4.3 边界情况的逻辑陷阱同步上升时判断条件是up[u][k] ! up[v][k]。这里有个容易理解错的地方如果u和v的2^k级祖先相同说明跳2^k步到达的节点是同一个那这个公共节点可能是LCA也可能是更深的公共祖先吗仔细想一下就明白既然跳2^k步到达的节点相同这个节点一定是u和v的一个公共祖先。但我们要找的是最近公共祖先。如果跳2^k步已经到达了一个公共祖先说明这个祖先至少比当前路径上的某个位置要浅离根更近。如果我们跳了可能直接越过LCA跳到LCA的祖先去了。所以只有当u和v的2^k级祖先不同我们才能确认跳上去之后它们还没有相遇从而安全地跳。还有一种边界情况是查询的两个节点本身就存在祖孙关系。比如u是v的祖先那么按算法流程对齐深度那一步之后u会变成和v一样的深度此时u v直接返回即可。这个逻辑我在查询函数里写了但很多人会漏掉这个判断导致第二步同步上升时出现up[u][k]和up[v][k]都取到奇怪的值最终返回的父节点错误。4.4 LCA的扩展应用从一道题到一类题LCA模板本身能AC的题目其实很有限CSP-S里真正考的是把LCA当作工具来用的综合题。最典型的一个扩展是树上差分。比如有一类题问在一棵树上每条边或者每个点被若干条路径覆盖求覆盖次数最多的边或点。解法就是把路径(u, v)拆成两条从端点往LCA走的路径然后利用差分数组在u处1v处1LCA处-1LCA的父节点处再-1最后从树根往下做一遍DFS累加差分值就能得到每条边的覆盖次数。整个流程只需要一次LCA查询加上O(n)的DFS求和如果没有LCA这个工具这类题基本没法做。另一个高频扩展是求树上两点间距离。因为树的边权通常是正的也有带负权的题目但少见dist(u, v) depth[u] depth[v] - 2 * depth[lca(u, v)]。这个公式的前提是每条边的边权为1等价于每个节点的深度就是根到它的距离。如果题目给了边权就把depth数组改成从根到节点的距离数组即可公式不变。用LCA把树上距离从不能做了变成O(logn)秒出这个转化很多选手在考场上要反应半天但其实理解了LCA的本质这个公式推导起来非常自然。5. 从LCA延伸到倍增思想全家桶5.1 快速幂倍增思想的最简版本如果你能把LCA的代码吃透回头再看快速幂就会觉得特别简单它其实就是一维场景下的倍增。快速幂维护的答案是result每次把底数自乘得到base的2^k次方然后看指数对应二进制位是否为1是1就乘进result。这和LCA里向上跳diff那步的逻辑完全一致都是看二进制的某一位是否为1决定要不要做一次2^k的跳跃。很多初学者是先学快速幂再学LCA觉得两者割裂但在我看来它们是同一个思想的两个投影一维的幂运算对应的是数值的自乘树上的幂运算对应的是节点的跳转。5.2 RMQ与ST表静态区间最值的倍增解法除了LCA和快速幂倍增思想还有一个重要应用场景是RMQ问题——给定一个数组多次询问区间内的最大值或最小值。ST表的做法是预处理st[i][k]表示从i开始的长度为2^k的区间内的最值递推式是st[i][k] max(st[i][k-1], st[i2^(k-1)][k-1])。这个递推式是不是看着眼熟没错它和up[u][k] up[up[u][k-1]][k-1]的结构一模一样都是合并两个长度为2^(k-1)的子结果得到长度为2^k的结果。如果把树上每个节点看作一个区间LCA问题实际上就能转化成RMQ问题来做这也就是我之前提过的欧拉序RMQ解法的思想源头。5.3 树上倍增的进阶玩法边权最值和树上第k级祖先倍增LCA的模板还有一种升级玩法就是同时维护up数组和另外一个数组maxEdge[node][k]表示从node向上跳2^k步经过的路径上边权的最大值。在查询LCA的过程中同步更新答案就能在O(logn)时间内求出u到v路径上的最大边权。这个技巧在求树中任意两点路径上的最大边权最小值这类题目里非常有用比如航班调度、管道运输这类带了容量限制的问题。树上第k级祖先问题也是LCA的自然衍生。给定u和一个正整数k求u向上跳k步到达的节点。这就是对齐深度那一步的单独使用把k做二进制拆分后依次跳转即可。这个问题在很多树形题里作为子步骤出现我在训练中经常看到选手现场临时写一个函数但如果你提前把LCA模板准备好这个功能顺手就有了。5.4 复习路径建议怎么把倍增练成肌肉记忆对于准备CSP-S的选手我的建议是不要只做LCA模板题一定要在练完基础之后立刻做两三道配套的树上问题把倍增、树上差分、深度优先序这些工具打通。我推荐按这个顺序刷题第一题洛谷P3379纯LCA模板题主要用来检验代码的正确性和性能。第二题求树上任意两点距离用dist depth[u] depth[v] - 2*depth[lca]的公式顺便理解depth数组在不同定义下的含义。第三题树上路径覆盖计数树上差分入门理解路径拆分到LCA的差分原理。第四题求树中两点间路径上的边权最值引入maxEdge数组彻底理解维护倍增附加信息的通用套路。这一套刷下来倍增LCA就不再是一个孤立的模板而是你解题工具箱里的一个顺手工具。6. 给2025年CSP-S考生的备考建议刷信奥赛题目的过程中我发现一个普遍的规律LCA这种基础设施型算法考场上最怕的不是不会而是不熟。很多考生其实学过LCA但拿到题目后要么模板写得很慢要么在套用的时候因为细节不熟练而出BUG白白浪费时间调试。我比较推荐的做法是把模板代码敲到肌肉记忆的程度。就是那种在考场上不用思考、直接默写出来的水平。要做到这一步唯一的办法就是高频重复。每天抽出10分钟手写一遍建图、DFS预处理、查询函数坚持两周到一个月基本就能达到这个标准。另外要注意CSP-S 2025的政策变化和题目风格趋势。从近几年的题目看树形结构、图论算法的考察比重在增加单纯套模板的题目在减少更多是把LCA嵌入一个看似复杂的综合题中。比如给你一棵树若干次操作每次修改一个节点的权值然后询问两个节点路径上的某种统计值这类题表面上是数据结构题但拆解之后你会发现LCA就是那座必经的桥。还有一个容易被忽视的实战技巧多练习用链式前向星而不是vector存图。虽然vector写法简单但在频繁插入边的大数据量下vector的扩容和遍历开销确实会影响性能。链式前向星就是用三个数组head、to、nxt模拟链表的操作写起来多两三行代码但胜在稳定高效。我平时练题基本都用链式前向星已经形成肌肉记忆考试时也不用临时切换思维。7. 写在最后的一些实战心得说实在的LCA是我觉得CSP-S算法里投入产出比最高的一块内容。它不像动态规划那样需要很强的思维建模能力也不像平衡树那样需要长篇累牍的数据结构功底它就是一层窗户纸捅破之后你就能解锁一整个类型的树上问题。我带着不少学生从LCA入门慢慢过渡到树上差分、树链剖分他们普遍反馈理解了倍增之后再学其他树上的高阶算法思路都清晰很多。我个人在实际教学中还有一个偏好就是让大家把up数组递推那行代码抄下来贴在自己电脑桌面上看几天——up[u][k] up[up[u][k-1]][k-1]。这行代码浓缩了整个倍增算法的精髓每次看它都能想起任意跳转都能拆成幂次步这个核心思想。你不需要死记硬背理解透了考试中哪怕一时想不起来完整代码顺着这个递推式推理也能把整块逻辑重建出来。最后再分享一个小技巧也是我自己做题时常用的调试方法遇到LCA相关的题先用暴力方法写一个朴素LCA做对拍然后拿随机数据同时跑暴力和倍增版一旦出现不一致马上就能定位问题出在预处理还是查询。这种方法比传统的断点调试高效得多。比赛时当然没时间建对拍程序但平时训练养成这个习惯考试时你就会自然而然地更谨慎很多低级错误其实能提前被这个习惯规避掉。