前两天刷题的时候碰见一道题号 #596、题名叫road的图论题读完题面第一反应就是经典的“最小瓶颈路”。题目本身不长但想把它讲透彻背后牵扯出的是最小生成树、树上倍增、Kruskal 重构树一整套东西。这篇文章就把当时从读题到 AC 的完整思考过程摊开写一遍既适合刚接触图论的读者也适合想复习“最小瓶颈路”这类题型的选手。题面可以抽象成一句话给定一个带权无向连通图每次询问两个点之间所有路径中路径上最大边权的最小值是多少。这种问法看起来有点像最短路但“最大边权最小”这六个字一出来就该放弃 Dijkstra 那一套了。下面从题目本身开始逐步拆到代码层面再讲几个我实测时踩过的坑。1. 从题面到算法road 这道题到底在问什么1.1 “最大边权最小”不是最短路先明确一点这题问的不是路径总长度最短而是要求你选出的一条路中最重的边尽量轻。举个例子如果路径 A 的总长度是 100但最重单边是 5路径 B 的总长度是 20但最重单边是 19。那么在这道题的语义下路径 A 是更优的因为它的“短板”更短。我最早学图论的时候遇到这种“最小化最大值”的模型第一反应往往是二分答案每次二分一个限制 X只走边权不超过 X 的边判断两个点是否连通。单次查询用并查集或 BFS 都能做到 O(m)但如果有 q 次询问总复杂度就是 O(q m log C)其中 C 是边权范围。数据规模一旦到 n、m、q 都是 10^5 级别这种思路只能拿部分分甚至会超时到怀疑人生。还有一种更直观的暴力每次询问跑一遍“类 Dijkstra”把记录最短距离改成记录路径上的最大边权用小根堆扩展。单次 O(m log n)q 次就是 O(q m log n)10^5 乘 10^5完全不可行。所以必须找到一个预处理结构让每次询问都在 O(log n) 甚至 O(1) 内完成。1.2 按边权排序一个关键视角回到问题的本质。假设我们把图中的边按照边权从小到大排序然后一条一条加进“空图”里。对于一次询问 (u, v)考虑这样一个时刻当加到某条权值为 w 的边时u 和 v 第一次在“已经加入的边”构成的无向图中连通。这个时刻的 w 是什么它就是答案。原因很简单。在加入所有权值小于 w 的边之后u 和 v 仍然不连通说明任何一条由“全小于 w 的边”组成的路径都不存在也就是说答案不可能小于 w而加入权值为 w 的这条边后u 和 v 连通了说明存在一条所有边都不超过 w 的路径答案不可能大于 w。两边一夹答案正好等于 w。这个观察非常关键它把所有问题都拉回到了 Kruskal 算法的执行过程上按边权从小到大枚举边用并查集维护连通性。u 和 v 第一次被合并进同一个连通块时当前正在处理的边权就是询问答案。这比“先二分再判断连通”优雅得多也是最小生成树能解决这个问题的根本原因。1.3 为什么最小生成树上的路径就是答案有了 1.2 的观察自然想到一个做法对原图跑一遍 Kruskal 求出最小生成树然后在树上回答询问。为什么可以这么做假设原图中的最小瓶颈路答案是 W。在原图里所有边权小于 W 的边合在一起一定不能让 u 和 v 连通否则答案就会更小。而 Kruskal 是从小到大加边的因此在生成树上u 到 v 的路径中不可能全部由小于 W 的边组成。又因为生成树的路径是一条真实存在的路径它的最大边权不可能小于全局最优值 W。两个条件合起来生成树上路径的最大边权必然恰好是 W。这其实也等价于“最小生成树是所有点对之间最小瓶颈路的并集”是图论里一个经典结论。如果你以前只把 Kruskal 当作求最小生成树的工具这一刻它会打开另一扇门Kruskal 的过程本身就是在逐步回答“两个点什么时候第一次连通”的问题。2. 两条实现路线MST 加树上倍增 与 Kruskal 重构树知道答案在最小生成树上之后剩下的问题就是如何在树上快速求任意两点路径上的最大边权。2.1 路线一最小生成树 树上倍增思路很直白先用 Kruskal 建出最小生成树然后对这颗树做倍增预处理。每个节点向上跳 2^j 步时不仅记录祖先节点编号还记录这一段路径上的最大边权。查询时先把两个点跳到同一深度再一起向上跳顺便合并每段的最大值。核心代码大概是这个样子的struct Edge { int to, w; }; vectorEdge tree[MAXN]; int fa[MAXN][LOG]; int mx[MAXN][LOG]; int depth[MAXN]; void dfs(int u, int f) { fa[u][0] f; depth[u] depth[f] 1; for (int i 1; i LOG; i) { fa[u][i] fa[fa[u][i - 1]][i - 1]; mx[u][i] max(mx[u][i - 1], mx[fa[u][i - 1]][i - 1]); } for (auto e : tree[u]) { if (e.to f) continue; mx[e.to][0] e.w; dfs(e.to, u); } } int query(int u, int v) { int ans 0; if (depth[u] depth[v]) swap(u, v); for (int i LOG - 1; i 0; i--) { if (depth[fa[u][i]] depth[v]) { ans max(ans, mx[u][i]); u fa[u][i]; } } if (u v) return ans; for (int i LOG - 1; i 0; i--) { if (fa[u][i] ! fa[v][i]) { ans max(ans, mx[u][i]); ans max(ans, mx[v][i]); u fa[u][i]; v fa[v][i]; } } ans max(ans, mx[u][0]); ans max(ans, mx[v][0]); return ans; }这种写法很符合直觉很多教材和题解都会给这个方案。它的优点是代码逻辑清晰缺点是“最大值路径”这个信息必须跟着倍增表一起维护一不小心就会漏更新某一层。我见过的初学者错误里至少有一半是mx[u][i] max(mx[u][i - 1], mx[fa[u][i - 1]][i - 1])这一行写成了mx[u][i] mx[u][i - 1]导致查询结果偏小。2.2 路线二Kruskal 重构树 LCA第二种思路更巧妙它不用在树边上维护最大值而是把边权“变成点权”。Kruskal 重构树的过程是这样的一开始有 n 个孤立点编号 1 到 n它们没有任何权值。然后按边权从小到大枚举原图的边设当前边连接 u 和 v如果它们已经在同一个并查集里就跳过否则新建一个节点 tot把 tot 的点权设为当前边权然后在重构树上把 tot 连到 fu 和 fv 的根节点上最后让并查集里 fu 和 fv 的父节点都指向 tot。等所有边都处理完原图点集对应的叶子节点就长在了一棵“大根堆”形态的树上越往上走点权越大。对于任意两个原图中的点 u、v它们在重构树上的 LCA 点权恰好就是 Kruskal 过程中这两个点第一次连通时的那条边权也就是最小瓶颈路的答案。这样一来问题被彻底转换成了“静态树的 LCA 查询”完全不用维护边上的最大值。查询部分就是纯模板路径最大值信息天然编码在树的形状里了。2.3 两种方案的选型对比对比维度MST 树上倍增Kruskal 重构树预处理复杂度O(m log m n log n)O(m log m n log n)单次查询复杂度O(log n)O(log n)代码理解难度中等需要在倍增时额外维护最大值中等偏上需要理解重构树含义扩展性只能求路径边权最值可配合 DFS 序、可持久化、离线批量处理空间占用O(n log n)O(n log n)但节点数翻倍到 2n如果只是单做这一道题两条路都能 AC差别不大。但从“以后做题还能不能复用”的角度看我更倾向于 Kruskal 重构树。因为重构树本质上把“动态连通性变化过程”变成了一棵静态树很多离线图论题一旦能转化成这种形式后续操作空间会大很多。比如后面要讲的“只经过边权不超过 x 的边能到达哪些点”用重构树就是查一个子树的事。3. 重构树方案的代码逐段拆解3.1 数据结构准备与并查集细节先看一眼整体结构。因为重构树最多会新建 n-1 个节点所以树的存储空间要开到 2n 甚至 2n5这是最容易踩的坑之一。const int LOG 20; const int MAXN 100000 10; const int MAXV MAXN * 2; struct Edge { int u, v, w; bool operator (const Edge o) const { return w o.w; } }; int n, m, q; Edge edges[MAXN * 2]; int parent[MAXV]; long long val[MAXV]; vectorint tree[MAXV]; int depth[MAXV]; int fa[MAXV][LOG]; int tot;注意这里的parent是并查集数组和后面倍增表里的fa是两个概念不要混。并查集的初始化作用域必须覆盖到 2n因为后面的新建节点编号会一路涨到接近 2n如果你只初始化了 1 到 n新建节点在第一次 find 时就会因为parent[i] 0而出问题。void init_union_find() { for (int i 1; i 2 * n; i) { parent[i] i; } } int find_root(int x) { while (parent[x] ! x) { parent[x] parent[parent[x]]; x parent[x]; } return x; }路径压缩我偏好这种“半压缩”写法它不会像递归版 find 那样在极端数据下爆栈效率也足够。3.2 构建重构树的主流程建树部分就是把 Kruskal 的合并过程“变形”一下。void build_rebuild_tree() { sort(edges, edges m); tot n; for (int i 0; i m; i) { int fu find_root(edges[i].u); int fv find_root(edges[i].v); if (fu fv) continue; tot; val[tot] edges[i].w; parent[fu] tot; parent[fv] tot; tree[tot].push_back(fu); tree[tot].push_back(fv); } }每次合并时fu和fv是两棵重构子树的根新建的tot成为它们的父亲。这里的val[tot] edges[i].w是整个算法的灵魂LCA 的权值就是答案靠的就是这一行。建完树后tot就是整棵重构树的根前提是原图连通。有一点需要解释为什么两个集合的代表点fu、fv可以直接作为tot的孩子因为fu和fv分别是之前的合并过程中产生的“最高点”它们各自代表了一整棵子树。在整个过程里并查集的 find 返回的都是当前这棵子树的根所以新节点连到的永远是树根最终形成一棵完整的树而不是一个森林加一堆散边。3.3 DFS 预处理与 LCA 查询建完树后需要预处理倍增表和深度。这里我推荐用迭代 DFS 而不是递归原因后面踩坑部分会详细说。void dfs_iterative(int root) { vectorint order; order.push_back(root); depth[root] 1; for (int idx 0; idx (int)order.size(); idx) { int u order[idx]; for (int v : tree[u]) { depth[v] depth[u] 1; fa[v][0] u; order.push_back(v); } } for (int i 1; i LOG; i) { for (int u 1; u tot; u) { fa[u][i] fa[fa[u][i - 1]][i - 1]; } } }LCA 查询就是标准倍增写法唯一区别在于最后返回的是g lca(u, v)然后输出val[g]。int lca(int u, int v) { if (depth[u] depth[v]) swap(u, v); int delta depth[u] - depth[v]; for (int i 0; i LOG; i) { if (delta (1 i)) { u fa[u][i]; } } if (u v) return u; for (int i LOG - 1; i 0; i--) { if (fa[u][i] ! fa[v][i]) { u fa[u][i]; v fa[v][i]; } } return fa[u][0]; }主程序部分就比较机械了读入边排序建树预处理读入 q 组询问并输出val[lca(u, v)]。整份代码的核心逻辑比 MST倍增那版少了很多“维护最大值”的环节反倒不容易写错。4. 实测中的四个坑从段错误到 TLE这一节完全来自我实际提交时的经历。题目本身不算难但这几个坑每个都能让你白白耗上一个多小时。4.1 数组大小只开 n一段离奇的 WA第一次提交时我把tree、val、parent都开成了MAXN也就是 1e5 大小。结果本地样例全过一交上去就随机 WA。当时第一反应是算法理解错了反复检查 LCA 也没问题。后来用大数据手动跑才意识到问题重构树的总结点数最多是2n - 1新建节点编号从 n1 开始递增到接近 2n。所有和节点编号有关的数组都必须按 2n 来开。数组不够大的时候越界写入不一定马上崩溃而是会把相邻内存里的数据改坏。parent数组越界写可能把edges排序后的内容覆盖掉tree越界写可能把fa表改出异常。这种错误现象极其迷惑不是 RE 而是随机 WA。排查思路也很简单先在本地把 n 开到 10^5然后跑一个随机图再拿暴力程序对拍。一旦数组越界对拍结果立刻崩溃或者不对。把数组从MAXN改成MAXV MAXN * 2之后问题直接消失。所以遇到“结果随机变化”的题第一件事检查所有和节点数挂钩的数组有没有按两倍开。4.2 递归 DFS 爆栈TLE 的隐形元凶建完重构树之后要预处理深度和倍增表。我第一次用的是递归 DFS因为在链状数据下重构树深度能到 2n递归层数直接破万。在部分评测环境下递归深度 1e5 以上就会爆栈表现为程序无输出或者直接 TLE。它不是超时而是递归调用栈溢出后程序异常退出浪费了预处理时间却没得到结果。我一开始以为是倍增表构建太慢优化了半天最后才发现是dfs函数本身挂了。解决方式有两种。第一种是显式加栈空间在代码开头写平台相关的扩栈指令第二种是改成迭代写法。我后来固定用迭代 DFS一劳永逸代码也没有复杂多少就是用数组模拟了一个遍历栈vectorint stk {root}; while (!stk.empty()) { int u stk.back(); stk.pop_back(); for (int v : tree[u]) { depth[v] depth[u] 1; fa[v][0] u; stk.push_back(v); } }这种写法在比赛里更省心不用依赖环境参数。4.3 重边、自环和“看似不连通”的图题目保证图连通但实际构造数据时可能会出现重边和自环。重边对并查集没有任何影响因为两端已经连通时会直接 continue自环也一样fu fv直接跳过。不过要注意自环和重边的存在会影响边排序后的枚举顺序但不会影响最终答案因为最小瓶颈路只在连通性有意义多余的边不会让“第一次连通”的时刻提前。真正需要警惕的是图不连通。如果原图是森林重构树也会变成一片森林tot这个变量只会是最后一棵树的根而不是全局根。这时如果你只从tot开始 DFS部分节点深度会是 0LCA 查询结果就是错的。稳妥做法是建树结束后遍历一遍 1 到 tot对所有depth[i] 0的根节点分别做 DFS。当然题目如果保证连通这一步可以省略但写上也不算浪费。4.4 查询 u v 和边权数据类型的细节还有一个容易忽略的小问题如果询问里出现 u v答案应该是 0因为从点到自身不需要经过任何边。在重构树方案里叶子节点的val初始值设成 0恰好能让lca(u, u)返回 u 本身输出 0语义正好对。如果你把叶子节点val初始化成某个大常数就必须在查询里特判if (u v) puts(0)。至于数据类型题目边权上限可能到 10^9答案用 int 也能存但我建议统一long long。特别是以后遇到边权到 10^18 的变体题int 就会炸掉。输出的时候用%lld别写%d这个低级错误造成的 WA 有时候比算法错误更难发现因为只有大数据才会出现数值溢出的差异。5. 最小瓶颈路与重构树的通法延伸5.1 从“最大边权最小”到“最小边权最大”如果把题意反过来要求路径上最小边权的最大值模型完全对称按边权从大到小排序建立重构树LCA 点权依然对应答案。很多同学学完这题之后只会套原来的模板遇到反向问题就懵了。实际上你只要想明白“第一次连通的时刻对应的是最小瓶颈还是最大瓶颈”就能判断排序方向。核心思维是排序方向决定合并顺序合并顺序决定 LCA 点权的意义。这种“最小化最大值 / 最大化最小值”的模型在二分答案、网络流、最小割、生成树里到处都是。road 这道题本质上就是最小生成树这个知识点的“另一种说法”一旦看穿很多题目都会变得亲切起来。5.2 重构树的扩展玩法Kruskal 重构树最有价值的地方在于它把边权限制转化成了子树归属问题。例如问“从点 u 出发只经过权值不超过 x 的边能到达哪些点”在重构树上就等价于找 u 向上跳到的最后一个权值不超过 x 的祖先然后这个祖先的整棵子树就是答案。配合 DFS 序和树状数组可以批量处理大量离线询问。再比如有些题要求“任意两点之间所有路径中最大边权小于等于 x 的路径是否存在”这可以直接转化成重构树上两个点的 LCA 权值是否小于等于 x单次 O(log n) 解决。如果不建重构树每次用二分加并查集做的话复杂度会高一个数量级。我个人的习惯是一看到“两个点之间路径边权最值”或者“动态加边 连通性 边权限制”这类字眼优先想一想是否能用 Kruskal 重构树。建树过程就是一次排序加并查集后续所有问题都在静态树上处理思维负担会小很多。5.3 比赛中的决策参考如果只是在考场上快速拿分MST倍增 的代码更短适合时间紧的时候写。如果题目还带有“多次询问、强制在线、可持久化”这些字眼重构树的扩展性更好。还有一种折中如果只是查询点数很多而边数中等可以先建最小生成树再倍增这道题完全够用。就这道 road 而言我最终选择重构树方案并不是因为它更快而是因为它的结论更干净LCA 即答案不需要写任何“求路径最大值”的代码。对于志在进阶的选手我强烈建议把重构树这板斧练熟很多看似复杂的离线图论题最后都会落到这几个经典套路的组合上。