1. 问题引入从“机房”到“树上的距离”去年备赛蓝桥杯做到这道决赛题时第一眼看到“机房”这个标题我差点以为走错了片场。这听起来像是个网络布线或者硬件配置的题目。但仔细读完题才发现它内核是一个经典的图论问题只不过披上了一层生活化的外衣。题目大意是一栋大楼的机房网络可以抽象成一棵树每个节点代表一台交换机节点之间的边代表网线。信息从一台交换机传输到另一台每经过一条边即一段网线就会产生1单位的延迟。现在我们需要回答多组查询任意给定树上的两个节点交换机u和v计算信息从u传输到v所经过的总延迟也就是它们在这棵树上的最短路径长度。这本质上就是求树上任意两点间的距离。对于学过图论的同学脑子里可能立刻蹦出“LCA最近公共祖先”这个词。没错这是解决此类问题的标准利器。但当时在考场上或者现在你自己尝试实现时可能会遇到几个很实际的问题为什么非得用LCA用DFS每次查询都跑一遍不行吗LCA又有好几种实现方式倍增、Tarjan、树链剖分该选哪个选好了之后具体怎么把路径长度算出来这些就是我想在这篇分享里彻底讲清楚的东西。这不是一篇单纯的题解而是结合我自己的踩坑和优化经验带你走一遍从暴力思路到高效解法的完整思考和实践过程。2. 暴力DFS的诱惑与陷阱为什么我们不能“每次都搜一遍”拿到问题最直观的想法可能就是深度优先搜索DFS。对于每次询问(u, v)我们从u点开始DFS寻找v点并记录走过的边数找到v时这个边数就是距离。这个逻辑完全正确写起来也简单。// 假设使用邻接表存树graph[u]存储与u相连的所有节点 vectorvectorint graph; int dfs_find(int current, int target, int parent, int depth) { if (current target) { return depth; // 找到目标返回当前累积深度距离 } for (int neighbor : graph[current]) { if (neighbor parent) continue; // 防止走回头路 int res dfs_find(neighbor, target, current, depth 1); if (res ! -1) return res; // 找到了层层返回结果 } return -1; // 这条支路没找到 } // 对于每次查询 int distance dfs_find(u, v, -1, 0);看起来很美对吧但它的时间复杂度是 O(n) 每次查询其中n是树的节点数。如果树有10^5个节点而查询次数q也有10^5那么总复杂度就是 O(n * q) 10^10这显然会超时通常竞赛要求1秒内操作次数在10^7~10^8量级。这里就引出了第一个核心经验在处理树上的多次路径查询时必须避免每次查询都遍历整棵树或大部分树。我们需要一种预处理机制使得每次查询能在远小于O(n)的时间内完成理想情况是O(log n)甚至O(1)。那么树上两点u和v的路径有什么特点呢它一定会经过u和v的“最近公共祖先”LCA。想象一下家族族谱u和v的LCA就是他们往上追溯最早遇到的那位共同祖先。在树结构中从u到v的路径等于从u上行到LCA再从LCA下行到v。因此dist(u, v) depth[u] depth[v] - 2 * depth[lca(u, v)]。其中depth[x]表示节点x的深度根节点深度为0。这样一来问题就转化了我们需要快速得到任意两个节点的深度以及它们的LCA。深度可以在一次DFS预处理中轻松得到。所以问题的核心就变成了——如何快速求解多组LCA查询。3. LCA算法选型倍增法为何成为竞赛首选能快速求LCA的算法有好几种我们需要根据题目特点静态树、多次查询来选择。Tarjan离线算法能在O(n q)的时间复杂度内处理所有查询非常高效。但它需要一次性读入所有查询是“离线”算法。在蓝桥杯等在线判题环境中有时查询是实时给出的虽然本题通常也是全部给出但实现起来相对复杂调试不便。树链剖分同样可以高效求LCA并且能支持树的动态修改本题不需要。代码量比倍增法大但常数小效率高。对于想追求极致运行速度或者已经熟练掌握树链剖分的选手是一个好选择。倍增法预处理时间复杂度O(n log n)每次查询O(log n)。对于n, q在10^5级别的情况总复杂度O((nq) log n)完全可接受。它的优势在于思路直观代码模板化程度高易于理解和记忆。在紧张的竞赛环境中可靠性和编码速度往往比微小的常数优化更重要。因此倍增法成为了绝大多数选手解决静态树LCA问题的首选。倍增法的核心思想是“二进制拆分”。我们维护一个数组fa[u][k]表示节点u向上跳2^k步所到达的祖先节点。通过这个数组我们可以将u和v快速提升到同一深度然后一起向上跳找到LCA。注意这里有一个初学者极易混淆的点。fa[u][0]存储的是u的父节点。fa[u][k] (k0)可以通过递推公式计算fa[u][k] fa[ fa[u][k-1] ][k-1]。意思是u向上跳2^k步等于先向上跳2^(k-1)步到达一个中间节点再从那个中间节点向上跳2^(k-1)步。这个递推关系是倍增法的基石务必理解。4. 实战倍增法求LCA的完整实现与细节剖析理论说完了我们来看代码。我会把每一步为什么这么做以及可能遇到的坑都讲清楚。4.1 数据结构定义与输入首先树是无向的我们用邻接表存储。因为要处理大量查询我们使用vector数组。#include iostream #include vector #include cmath #include cstring // 如果使用memset初始化fa数组 using namespace std; const int MAXN 100010; // 根据题目数据范围设定通常多开一点 const int MAXLOG 20; // 2^20 10^6足够覆盖一般数据范围 vectorint graph[MAXN]; // 邻接表存树 int depth[MAXN]; // 每个节点的深度 int fa[MAXN][MAXLOG]; // 倍增祖先数组 int n, m; // n: 节点数 m: 查询次数输入部分题目通常会给n-1条边构建树。注意根节点不一定是1但我们可以任意指定一个节点为根通常就选1因为树上距离的计算与根的选择无关只要所有计算基于同一个根即可。void init() { cin n m; for (int i 0; i n-1; i) { int u, v; cin u v; graph[u].push_back(v); graph[v].push_back(u); // 无向边 } }4.2 DFS预处理计算深度和直接父节点我们需要一次DFS来初始化depth数组和fa[u][0]即父节点。这里用递归DFS代码简洁。void dfs(int u, int parent) { fa[u][0] parent; // 记录父节点 depth[u] (parent -1) ? 0 : depth[parent] 1; // 根深度为0 // 遍历子节点 for (int v : graph[u]) { if (v parent) continue; // 防止走回父节点 dfs(v, u); } }在主函数中我们从根节点例如1开始调用dfs(1, -1);。这里-1表示根节点没有父节点。4.3 倍增数组的递推填充这是关键步骤。我们已经有了fa[u][0]现在要利用递推关系fa[u][k] fa[ fa[u][k-1] ][k-1]来填充k0的部分。void preprocess() { // 先进行DFS得到depth和fa[][0] dfs(1, -1); // 假设1是根 // 计算最大的k值2^k 最大深度 int maxLog (int)(log(n) / log(2)) 1; // 或者直接使用预设的MAXLOG // 递推填充fa数组 for (int k 1; k maxLog; k) { for (int u 1; u n; u) { if (fa[u][k-1] ! -1) { // 如果u的2^(k-1)级祖先存在 fa[u][k] fa[ fa[u][k-1] ][k-1]; } else { fa[u][k] -1; // 不存在则记为-1 } } } }踩坑点1递推顺序。一定要先枚举k跳的步数再枚举节点u。因为计算fa[u][k]时需要用到fa[u][k-1]和fa[ fa[u][k-1] ][k-1]而fa[ fa[u][k-1] ][k-1]在本次k循环中当u遍历到fa[u][k-1]这个节点时它的fa[ fa[u][k-1] ][k-1]可能还没有被计算如果先枚举u的话。先枚举k可以保证在计算第k层时所有节点的第k-1层祖先信息都已就绪。踩坑点2祖先不存在的情况。当向上跳的步数超过了根节点祖先就是-1或0取决于你的定义。必须在代码中处理这种情况否则会数组越界。上面代码中的判断if (fa[u][k-1] ! -1)就是干这个的。4.4 LCA查询函数实现现在来实现最核心的lca(u, v)函数。步骤分解如下统一深度如果u比v深就交换u和v保证v是更深或等深的那个。然后将v向上跳直到和u同一深度。特判如果此时u v那么u或v就是LCA。同步上跳u和v从最大的可能步数maxLog开始尝试向上跳。如果跳了2^k步后u和v的祖先不同那就执行这次跳跃。这样能保证它们最后停留在LCA的下一层。返回父节点循环结束后u和v的父节点就是它们的LCA。int lca(int u, int v) { // 1. 让v成为更深的节点 if (depth[u] depth[v]) { swap(u, v); } // 2. 将v提升到与u同一深度 int diff depth[v] - depth[u]; for (int k 0; k MAXLOG; k) { if (diff (1 k)) { // 利用二进制位判断是否需要跳2^k步 v fa[v][k]; } } // 3. 如果此时相同u就是LCA if (u v) return u; // 4. 同步上跳 for (int k MAXLOG - 1; k 0; --k) { // 如果祖先不同就一起跳上去 if (fa[u][k] ! fa[v][k]) { u fa[u][k]; v fa[v][k]; } } // 5. 此时u和v的父节点就是LCA return fa[u][0]; }关键技巧二进制拆分提升深度。在将v提升到与u同深度的步骤中我们不是一步一步往上跳而是利用diff的二进制表示。diff (1 k)检查diff的第k位是否为1。如果是1说明需要向上跳2^k步。这比循环diff次要高效得多O(log n) vs O(n)。关键技巧从大到小尝试跳跃。在同步上跳时我们从最大的kMAXLOG-1开始尝试。如果跳了2^k步后u和v变得相同说明跳多了跳过了LCA所以我们不跳。只有当跳了之后u和v仍不同我们才执行跳跃。这样可以保证我们最终停留在LCA的直系儿子节点上。4.5 计算距离并回答查询有了LCA距离计算就一行公式int getDistance(int u, int v) { int ancestor lca(u, v); return depth[u] depth[v] - 2 * depth[ancestor]; }最后读入m次查询每次计算并输出距离即可。int main() { init(); // 读入数据建树 preprocess(); // DFS预处理并填充倍增数组 for (int i 0; i m; i) { int u, v; cin u v; cout getDistance(u, v) endl; } return 0; }5. 性能分析与边界条件测试让我们分析一下这个算法的效率预处理DFS遍历所有边和节点O(n)。填充倍增数组是O(n log n)。所以预处理总复杂度O(n log n)。每次查询lca函数中有两个循环每个循环最多执行MAXLOG(约20) 次所以是O(log n)。计算距离是O(1)。总体对于n, q 10^5预处理约10^5 * 20 2*10^6次操作查询约10^5 * 20 2*10^6次操作总共约4百万次远在1秒时限内。边界条件与测试根节点查询查询(1, x)。LCA应该是1。我们的算法能正确处理因为在统一深度后u1, vxuv不成立进入同步上跳。由于fa[1][k]都是 -1所以fa[u][k] ! fa[v][k]的条件可能不触发因为-1 -1循环结束后fa[1][0]是-1这里有个问题。我们通常把根节点的父节点设为0或-1。在lca函数最后返回fa[u][0]时如果u是根节点fa[u][0]是-1这不符合预期。修复在初始化时将根节点的父节点fa[root][0]设为root自身或者在进行fa[u][k] ! fa[v][k]判断时要额外考虑-1的情况。更常见的做法是将根节点的深度设为1并且fa[root][0] 0。这样在同步上跳时因为fa[root][k]始终是0而其他节点的祖先不会是0除非也是根所以判断fa[u][k] ! fa[v][k]能正常工作。最后返回fa[u][0]对于根节点和其他节点的LCA都能得到正确结果根节点与任何节点的LCA是根fa[非根节点][0]会指向根或更上层的节点。这是实现中一个非常细微但重要的点。我推荐将根节点深度设为1并令fa[root][0] 0。相同节点查询查询(x, x)。距离应为0。我们的getDistance函数能正确计算因为lca(x, x) x公式结果为depth[x] depth[x] - 2*depth[x] 0。链状树退化成链表这是最坏情况深度可能达到n。但我们的倍增法是基于深度的对数进行跳跃所以查询时间依然是O(log n)不受树形状影响这是其巨大优势。6. 从解题到举一反三LCA与树上问题的扩展解决了“机房”这道题你掌握的不只是一个算法模板更是一把解决众多树上问题的钥匙。LCA是许多高级树上操作的基础。树上两点路径权值和如果每条边有一个权值比如网线的长度求u到v路径的总长度。我们可以在DFS预处理时额外维护一个dis[u]表示根节点到u的路径总权值。那么dist(u, v) dis[u] dis[v] - 2 * dis[lca(u, v)]。这和距离公式如出一辙。树上差分一类常见问题是“给树上一条路径上的所有节点增加一个值最后询问每个节点的值”。这可以通过将路径u-v的修改转化为对u,v,lca(u,v),fa[lca(u,v)][0]四个点的修改最后进行一次DFS来快速实现。这在处理多次区间修改、单点查询的树上问题时效率极高。结合树链剖分当问题升级为“修改树上一条路径的权值”或“查询路径上节点权值的最值”时就需要树链剖分配合线段树来实现了而树链剖分本身也需要快速求LCA。回过头看“机房”这道题它用生活场景包装了一个经典的图论模型考察的就是选手对树这种数据结构的理解、对高效查询算法LCA的掌握以及将实际问题抽象建模的能力。在竞赛中遇到“求树上距离”、“求树上路径信息”这类描述LCA几乎就是标准答案的第一联想。我个人在实现倍增法时最大的教训就是初始化根节点父节点和递推顺序这两个细节。一旦这里出错调试起来非常痛苦因为错误可能在某些特定查询如涉及根节点的查询时才出现。我的建议是写好后用一个小样例比如一个3个节点的链手工模拟一遍算法的每一步验证fa数组的填充和lca函数的逻辑。理解透彻后这个模板就可以成为你解决一系列树上问题的可靠工具。 从暴力DFS到倍增法：详解LCA算法求解树上任意两点距离
1. 问题引入从“机房”到“树上的距离”去年备赛蓝桥杯做到这道决赛题时第一眼看到“机房”这个标题我差点以为走错了片场。这听起来像是个网络布线或者硬件配置的题目。但仔细读完题才发现它内核是一个经典的图论问题只不过披上了一层生活化的外衣。题目大意是一栋大楼的机房网络可以抽象成一棵树每个节点代表一台交换机节点之间的边代表网线。信息从一台交换机传输到另一台每经过一条边即一段网线就会产生1单位的延迟。现在我们需要回答多组查询任意给定树上的两个节点交换机u和v计算信息从u传输到v所经过的总延迟也就是它们在这棵树上的最短路径长度。这本质上就是求树上任意两点间的距离。对于学过图论的同学脑子里可能立刻蹦出“LCA最近公共祖先”这个词。没错这是解决此类问题的标准利器。但当时在考场上或者现在你自己尝试实现时可能会遇到几个很实际的问题为什么非得用LCA用DFS每次查询都跑一遍不行吗LCA又有好几种实现方式倍增、Tarjan、树链剖分该选哪个选好了之后具体怎么把路径长度算出来这些就是我想在这篇分享里彻底讲清楚的东西。这不是一篇单纯的题解而是结合我自己的踩坑和优化经验带你走一遍从暴力思路到高效解法的完整思考和实践过程。2. 暴力DFS的诱惑与陷阱为什么我们不能“每次都搜一遍”拿到问题最直观的想法可能就是深度优先搜索DFS。对于每次询问(u, v)我们从u点开始DFS寻找v点并记录走过的边数找到v时这个边数就是距离。这个逻辑完全正确写起来也简单。// 假设使用邻接表存树graph[u]存储与u相连的所有节点 vectorvectorint graph; int dfs_find(int current, int target, int parent, int depth) { if (current target) { return depth; // 找到目标返回当前累积深度距离 } for (int neighbor : graph[current]) { if (neighbor parent) continue; // 防止走回头路 int res dfs_find(neighbor, target, current, depth 1); if (res ! -1) return res; // 找到了层层返回结果 } return -1; // 这条支路没找到 } // 对于每次查询 int distance dfs_find(u, v, -1, 0);看起来很美对吧但它的时间复杂度是 O(n) 每次查询其中n是树的节点数。如果树有10^5个节点而查询次数q也有10^5那么总复杂度就是 O(n * q) 10^10这显然会超时通常竞赛要求1秒内操作次数在10^7~10^8量级。这里就引出了第一个核心经验在处理树上的多次路径查询时必须避免每次查询都遍历整棵树或大部分树。我们需要一种预处理机制使得每次查询能在远小于O(n)的时间内完成理想情况是O(log n)甚至O(1)。那么树上两点u和v的路径有什么特点呢它一定会经过u和v的“最近公共祖先”LCA。想象一下家族族谱u和v的LCA就是他们往上追溯最早遇到的那位共同祖先。在树结构中从u到v的路径等于从u上行到LCA再从LCA下行到v。因此dist(u, v) depth[u] depth[v] - 2 * depth[lca(u, v)]。其中depth[x]表示节点x的深度根节点深度为0。这样一来问题就转化了我们需要快速得到任意两个节点的深度以及它们的LCA。深度可以在一次DFS预处理中轻松得到。所以问题的核心就变成了——如何快速求解多组LCA查询。3. LCA算法选型倍增法为何成为竞赛首选能快速求LCA的算法有好几种我们需要根据题目特点静态树、多次查询来选择。Tarjan离线算法能在O(n q)的时间复杂度内处理所有查询非常高效。但它需要一次性读入所有查询是“离线”算法。在蓝桥杯等在线判题环境中有时查询是实时给出的虽然本题通常也是全部给出但实现起来相对复杂调试不便。树链剖分同样可以高效求LCA并且能支持树的动态修改本题不需要。代码量比倍增法大但常数小效率高。对于想追求极致运行速度或者已经熟练掌握树链剖分的选手是一个好选择。倍增法预处理时间复杂度O(n log n)每次查询O(log n)。对于n, q在10^5级别的情况总复杂度O((nq) log n)完全可接受。它的优势在于思路直观代码模板化程度高易于理解和记忆。在紧张的竞赛环境中可靠性和编码速度往往比微小的常数优化更重要。因此倍增法成为了绝大多数选手解决静态树LCA问题的首选。倍增法的核心思想是“二进制拆分”。我们维护一个数组fa[u][k]表示节点u向上跳2^k步所到达的祖先节点。通过这个数组我们可以将u和v快速提升到同一深度然后一起向上跳找到LCA。注意这里有一个初学者极易混淆的点。fa[u][0]存储的是u的父节点。fa[u][k] (k0)可以通过递推公式计算fa[u][k] fa[ fa[u][k-1] ][k-1]。意思是u向上跳2^k步等于先向上跳2^(k-1)步到达一个中间节点再从那个中间节点向上跳2^(k-1)步。这个递推关系是倍增法的基石务必理解。4. 实战倍增法求LCA的完整实现与细节剖析理论说完了我们来看代码。我会把每一步为什么这么做以及可能遇到的坑都讲清楚。4.1 数据结构定义与输入首先树是无向的我们用邻接表存储。因为要处理大量查询我们使用vector数组。#include iostream #include vector #include cmath #include cstring // 如果使用memset初始化fa数组 using namespace std; const int MAXN 100010; // 根据题目数据范围设定通常多开一点 const int MAXLOG 20; // 2^20 10^6足够覆盖一般数据范围 vectorint graph[MAXN]; // 邻接表存树 int depth[MAXN]; // 每个节点的深度 int fa[MAXN][MAXLOG]; // 倍增祖先数组 int n, m; // n: 节点数 m: 查询次数输入部分题目通常会给n-1条边构建树。注意根节点不一定是1但我们可以任意指定一个节点为根通常就选1因为树上距离的计算与根的选择无关只要所有计算基于同一个根即可。void init() { cin n m; for (int i 0; i n-1; i) { int u, v; cin u v; graph[u].push_back(v); graph[v].push_back(u); // 无向边 } }4.2 DFS预处理计算深度和直接父节点我们需要一次DFS来初始化depth数组和fa[u][0]即父节点。这里用递归DFS代码简洁。void dfs(int u, int parent) { fa[u][0] parent; // 记录父节点 depth[u] (parent -1) ? 0 : depth[parent] 1; // 根深度为0 // 遍历子节点 for (int v : graph[u]) { if (v parent) continue; // 防止走回父节点 dfs(v, u); } }在主函数中我们从根节点例如1开始调用dfs(1, -1);。这里-1表示根节点没有父节点。4.3 倍增数组的递推填充这是关键步骤。我们已经有了fa[u][0]现在要利用递推关系fa[u][k] fa[ fa[u][k-1] ][k-1]来填充k0的部分。void preprocess() { // 先进行DFS得到depth和fa[][0] dfs(1, -1); // 假设1是根 // 计算最大的k值2^k 最大深度 int maxLog (int)(log(n) / log(2)) 1; // 或者直接使用预设的MAXLOG // 递推填充fa数组 for (int k 1; k maxLog; k) { for (int u 1; u n; u) { if (fa[u][k-1] ! -1) { // 如果u的2^(k-1)级祖先存在 fa[u][k] fa[ fa[u][k-1] ][k-1]; } else { fa[u][k] -1; // 不存在则记为-1 } } } }踩坑点1递推顺序。一定要先枚举k跳的步数再枚举节点u。因为计算fa[u][k]时需要用到fa[u][k-1]和fa[ fa[u][k-1] ][k-1]而fa[ fa[u][k-1] ][k-1]在本次k循环中当u遍历到fa[u][k-1]这个节点时它的fa[ fa[u][k-1] ][k-1]可能还没有被计算如果先枚举u的话。先枚举k可以保证在计算第k层时所有节点的第k-1层祖先信息都已就绪。踩坑点2祖先不存在的情况。当向上跳的步数超过了根节点祖先就是-1或0取决于你的定义。必须在代码中处理这种情况否则会数组越界。上面代码中的判断if (fa[u][k-1] ! -1)就是干这个的。4.4 LCA查询函数实现现在来实现最核心的lca(u, v)函数。步骤分解如下统一深度如果u比v深就交换u和v保证v是更深或等深的那个。然后将v向上跳直到和u同一深度。特判如果此时u v那么u或v就是LCA。同步上跳u和v从最大的可能步数maxLog开始尝试向上跳。如果跳了2^k步后u和v的祖先不同那就执行这次跳跃。这样能保证它们最后停留在LCA的下一层。返回父节点循环结束后u和v的父节点就是它们的LCA。int lca(int u, int v) { // 1. 让v成为更深的节点 if (depth[u] depth[v]) { swap(u, v); } // 2. 将v提升到与u同一深度 int diff depth[v] - depth[u]; for (int k 0; k MAXLOG; k) { if (diff (1 k)) { // 利用二进制位判断是否需要跳2^k步 v fa[v][k]; } } // 3. 如果此时相同u就是LCA if (u v) return u; // 4. 同步上跳 for (int k MAXLOG - 1; k 0; --k) { // 如果祖先不同就一起跳上去 if (fa[u][k] ! fa[v][k]) { u fa[u][k]; v fa[v][k]; } } // 5. 此时u和v的父节点就是LCA return fa[u][0]; }关键技巧二进制拆分提升深度。在将v提升到与u同深度的步骤中我们不是一步一步往上跳而是利用diff的二进制表示。diff (1 k)检查diff的第k位是否为1。如果是1说明需要向上跳2^k步。这比循环diff次要高效得多O(log n) vs O(n)。关键技巧从大到小尝试跳跃。在同步上跳时我们从最大的kMAXLOG-1开始尝试。如果跳了2^k步后u和v变得相同说明跳多了跳过了LCA所以我们不跳。只有当跳了之后u和v仍不同我们才执行跳跃。这样可以保证我们最终停留在LCA的直系儿子节点上。4.5 计算距离并回答查询有了LCA距离计算就一行公式int getDistance(int u, int v) { int ancestor lca(u, v); return depth[u] depth[v] - 2 * depth[ancestor]; }最后读入m次查询每次计算并输出距离即可。int main() { init(); // 读入数据建树 preprocess(); // DFS预处理并填充倍增数组 for (int i 0; i m; i) { int u, v; cin u v; cout getDistance(u, v) endl; } return 0; }5. 性能分析与边界条件测试让我们分析一下这个算法的效率预处理DFS遍历所有边和节点O(n)。填充倍增数组是O(n log n)。所以预处理总复杂度O(n log n)。每次查询lca函数中有两个循环每个循环最多执行MAXLOG(约20) 次所以是O(log n)。计算距离是O(1)。总体对于n, q 10^5预处理约10^5 * 20 2*10^6次操作查询约10^5 * 20 2*10^6次操作总共约4百万次远在1秒时限内。边界条件与测试根节点查询查询(1, x)。LCA应该是1。我们的算法能正确处理因为在统一深度后u1, vxuv不成立进入同步上跳。由于fa[1][k]都是 -1所以fa[u][k] ! fa[v][k]的条件可能不触发因为-1 -1循环结束后fa[1][0]是-1这里有个问题。我们通常把根节点的父节点设为0或-1。在lca函数最后返回fa[u][0]时如果u是根节点fa[u][0]是-1这不符合预期。修复在初始化时将根节点的父节点fa[root][0]设为root自身或者在进行fa[u][k] ! fa[v][k]判断时要额外考虑-1的情况。更常见的做法是将根节点的深度设为1并且fa[root][0] 0。这样在同步上跳时因为fa[root][k]始终是0而其他节点的祖先不会是0除非也是根所以判断fa[u][k] ! fa[v][k]能正常工作。最后返回fa[u][0]对于根节点和其他节点的LCA都能得到正确结果根节点与任何节点的LCA是根fa[非根节点][0]会指向根或更上层的节点。这是实现中一个非常细微但重要的点。我推荐将根节点深度设为1并令fa[root][0] 0。相同节点查询查询(x, x)。距离应为0。我们的getDistance函数能正确计算因为lca(x, x) x公式结果为depth[x] depth[x] - 2*depth[x] 0。链状树退化成链表这是最坏情况深度可能达到n。但我们的倍增法是基于深度的对数进行跳跃所以查询时间依然是O(log n)不受树形状影响这是其巨大优势。6. 从解题到举一反三LCA与树上问题的扩展解决了“机房”这道题你掌握的不只是一个算法模板更是一把解决众多树上问题的钥匙。LCA是许多高级树上操作的基础。树上两点路径权值和如果每条边有一个权值比如网线的长度求u到v路径的总长度。我们可以在DFS预处理时额外维护一个dis[u]表示根节点到u的路径总权值。那么dist(u, v) dis[u] dis[v] - 2 * dis[lca(u, v)]。这和距离公式如出一辙。树上差分一类常见问题是“给树上一条路径上的所有节点增加一个值最后询问每个节点的值”。这可以通过将路径u-v的修改转化为对u,v,lca(u,v),fa[lca(u,v)][0]四个点的修改最后进行一次DFS来快速实现。这在处理多次区间修改、单点查询的树上问题时效率极高。结合树链剖分当问题升级为“修改树上一条路径的权值”或“查询路径上节点权值的最值”时就需要树链剖分配合线段树来实现了而树链剖分本身也需要快速求LCA。回过头看“机房”这道题它用生活场景包装了一个经典的图论模型考察的就是选手对树这种数据结构的理解、对高效查询算法LCA的掌握以及将实际问题抽象建模的能力。在竞赛中遇到“求树上距离”、“求树上路径信息”这类描述LCA几乎就是标准答案的第一联想。我个人在实现倍增法时最大的教训就是初始化根节点父节点和递推顺序这两个细节。一旦这里出错调试起来非常痛苦因为错误可能在某些特定查询如涉及根节点的查询时才出现。我的建议是写好后用一个小样例比如一个3个节点的链手工模拟一遍算法的每一步验证fa数组的填充和lca函数的逻辑。理解透彻后这个模板就可以成为你解决一系列树上问题的可靠工具。