打完比赛复盘的时候最怕的就是“当时明明觉得有思路却写不出来”的题。2025 ICPC 香港站这道 C 题就是这样。我一开始习惯性地往“枚举所有路径 树剖维护最大值”的方向想结果代码越写越复杂最后也没能在赛场上调通。赛后重新梳理了一遍发现这道题真正的解法并不需要高级数据结构核心就是三件事贡献法、按边权排序、并查集维护连通块。这篇文章尝试把我完整的推导过程、C 实现以及踩过的坑写清楚适合准备 ICPC/CCPC 区域赛的选手也适合想系统练习“树上路径统计”类问题的同学。1. 题目定位与复习价值1.1 为什么写这道题的复盘区域赛的 C 题往往处在“会的人觉得不难不会的人卡死”的位置。它不是纯签到但也没有到银牌题那种需要冷门算法的程度。真正卡人的地方通常在思维转换你能不能从“求所有路径”切换到“统计每条边的贡献”。这道题就是一个非常典型的例子。如果只看题面很多人的第一反应是用倍增、树链剖分、点分治去处理路径最值。但一旦数据范围到 2e5 甚至更大这些做法的代码量和调试成本都会变得很高。而用“贡献法 并查集”来实现核心代码只有几十行并且不需要递归遍历整棵树天然避开了 DFS 爆栈的问题。对备赛选手来说这道题的复习价值主要在三方面熟练使用“贡献法”拆解统计问题掌握按权值排序 并查集维护连通块的离线套路理解同权边必须分组处理的原因。这三条在很多区域赛题目里都会反复出现值得单独拿出来写一篇复盘。1.2 知识点清单这道题涉及的知识点并不冷门但组合起来很典型知识点作用贡献法把“路径统计”转化为“每条边被多少路径作为最大边”离线排序按边权从小到大处理保证当前边是连通块之间的“最大边”并查集维护每个连通块的节点数量同权边分组处理处理边权相同的场景保证答案不重不漏复杂度分析排序 O(m log m)并查集近似线性如果你能把这几个点串起来那么这道题的核心就已经掌握了。2. 问题模型与解题约定2.1 题意假设由于赛后很多论坛的讨论版本并不完全一致这里先给出本文所用的题目模型给定一棵 n 个节点的树每条边有一个正整数权值求所有点对之间路径上最大边权的和结果对 1e97 取模。如果你拿到的题面细节和这个模型有差异也不要紧。本文重点不是背诵某个具体题面而是把这一类“路径最大边权统计”问题的通用解法讲透代码稍作修改就能套到大多数变体上。数据范围方面本文按 n 2e5、边权 1e9 来设计实现。实际比赛时请以官方题面为准但复杂度模型基本一致。2.2 输入输出格式输入格式如下第一行一个整数 n表示节点数接下来 n-1 行每行三个整数 u, v, w表示节点 u 和 v 之间有一条权值为 w 的边。输出为一个整数表示所有点对路径最大边权之和取模后的结果。对应的标准输入示例5 1 2 5 2 3 1 3 4 2 4 5 4节点编号默认从 1 开始。这个输入格式和大多数树形题保持一致方便直接用各种树的生成器来造数据。2.3 暴力做法分析在说优化之前先看一个最简单的暴力版本枚举所有点对DFS 求出路径上的最大边权累加到答案里。伪代码如下long long ans 0; for (int s 1; s n; s) { dfs(s, -1, 0); // 从 s 出发累计到每个点的路径最大边权 }这个做法的复杂度是 O(n^2)。当 n 只有 2000 时可以用当 n 到 2e5 时完全不可行。但暴力并不仅仅是用来得分的它还有两个重要价值帮助验证思路是否正确给优化版本的代码做对拍。所以即使已经有了正解也推荐保留一个暴力版本在本地随机数据上对拍。3. 核心思路拆解3.1 从枚举路径到枚举边这道题最关键的思维转换是把“对所有点对路径求最大值之和”换成“枚举每条边统计它被多少条路径作为最大值”。为什么可以这样换因为每一条路径的最大值本质上都对应着某条具体的边。如果我们能确定“某条边”是哪些路径的最大值就能把每条边的贡献加起来。按边权从小到大加入边当前加入的边是 (u, v, w)加入之前u 和 v 分别属于两个不同的连通块那么分别从 u 所在连通块和 v 所在连通块各取一个点这两个点之间的路径一定经过当前这条边由于之前加入的边权都小于等于 w这条路径上的最大边权就是 w。于是这条边对答案的贡献就是贡献 w * 左连通块点数 * 右连通块点数用并查集维护每个连通块的点数就能在每次合并时 O(1) 地计算出贡献。这就是“按权值排序 贡献法”的核心。3.2 按边权排序的意义如果边权互不相同整个过程会非常直观把边按权值从小到大排序一条一条处理每次合并两个连通块并累加贡献。但真实题目不会每次都保证边权互不相同。如果存在权值相同的边事情会稍微复杂一些。假设有三条边权值都是 5它们把 A、B、C 三个连通块连成一个组件。那么 A、B、C 中任意两个不同连通块之间的路径其最大边权都是 5。此时不能简单按“先处理哪一条都行”的顺序来合并因为三条边之间没有先后关系必须把整个同权批次一起处理。这就引出了同权边分组处理的必要性。3.3 用并查集维护连通块大小先定义一个并查集结构维护 parent 和 szparent[x] 表示 x 所在连通块的根sz[x] 表示 x 作为根时这个连通块有多少个节点只有根节点的 sz 有意义非根节点的 sz 可以清零。初始时每个节点是一个独立连通块sz[i] 1。当处理一条权值为 w 的边 (u, v) 时ru find(u); rv find(v); 贡献 w * sz[ru] * sz[rv]; unite(ru, rv);这个公式非常简洁。前提是 ru 和 rv 不同。3.4 同权边为什么必须分组直接按“一条一条合并”来处理同权边会出错。原因在于我们把“当前边”当成路径的最大值是基于“之前加入的边权都更小”这一前提。但如果两条边权值相同在处理第二条边时第一条同权边已经被合并进连通块里了。此时第二条边连接的两个连通块之间路径最大边权确实还是 w贡献公式依然正确。但问题出在第一条边和第二条边形成的闭环场景中。举个例子假设 A、B、C 三个连通块通过两条权值均为 w 的边连接成一条链A - B - C。如果先处理 A-B贡献是 w * sz[A] * sz[B]再处理 B-C贡献是 w * sz[AB] * sz[C]。最终总贡献 w * (sz[A]*sz[B] (sz[A]sz[B])*sz[C])展开后是 w * sz[A]*sz[B] w * sz[A]*sz[C] w * sz[B]*sz[C]。这看起来和 A、B、C 两两相乘是一样的似乎没问题。那什么时候会出错呢考虑 A、B、C、D 四个连通块边为 A-B、B-C、C-A、C-D且这四条边权值全部相同。由于 A、B、C 形成一个环任意两个连通块之间的路径最大边权仍然是 w。如果按任意顺序一条条合并虽然最终贡献的公式在某些顺序下碰巧正确但在更复杂的场景下可能会把本应属于同一批次的边拆散导致统计混乱。更严谨的处理方式是把所有权值相同的边作为一个批次整体处理先把每条同权边两端的“当前并查集根节点”取出来用一个临时并查集把这些根节点按照同权边的连接关系聚成若干个组件对于每个组件统计组件内各个原连通块的大小组件内任意两个不同原连通块之间的点对路径最大边权都等于当前权值 w用组合数公式计算贡献然后再真正合并主并查集。这样就能保证同权边之间不分先后贡献不重不漏。4. 完整实现4.1 数据结构核心数据结构是两个并查集主并查集维护每个节点当前所属的连通块以及连通块大小临时并查集只在处理同权边批次时使用用来识别“这一批边把哪些根节点连成了一个组件”。主并查集的合并时机要特别注意必须先统计完整个同权批次的贡献再真正合并。不能在处理同权边时边统计边合并否则前面提到的同权边问题就会重新出现。下面是完整可运行的 C17 代码。4.2 主算法代码#include bits/stdc.h using namespace std; struct DSU { vectorint parent, sz; DSU(int n) { parent.resize(n 1); sz.assign(n 1, 1); for (int i 0; i n; i) parent[i] i; } int find(int x) { while (parent[x] ! x) { parent[x] parent[parent[x]]; x parent[x]; } return x; } void unite(int a, int b) { a find(a); b find(b); if (a b) return; if (sz[a] sz[b]) swap(a, b); parent[b] a; sz[a] sz[b]; sz[b] 0; } }; struct Edge { int u, v; long long w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; if (!(cin n)) return 0; vectorEdge edges; edges.reserve(n - 1); for (int i 1; i n; i) { int u, v; long long w; cin u v w; edges.push_back({u, v, w}); } sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) { return a.w b.w; }); DSU dsu(n); const long long MOD 1000000007LL; long long ans 0; int m (int)edges.size(); int p 0; while (p m) { int q p; while (q m edges[q].w edges[p].w) q; // 第一步收集当前批次中涉及的原连通块根节点 vectorint roots; unordered_mapint, int id; vectorpairint, int tmpEdges; for (int k p; k q; k) { int ru dsu.find(edges[k].u); int rv dsu.find(edges[k].v); if (ru rv) continue; if (!id.count(ru)) { id[ru] (int)roots.size(); roots.push_back(ru); } if (!id.count(rv)) { id[rv] (int)roots.size(); roots.push_back(rv); } tmpEdges.push_back({id[ru], id[rv]}); } int cnt (int)roots.size(); // 第二步用临时并查集把同权边涉及的根节点分组 vectorint tmpParent(cnt); for (int i 0; i cnt; i) tmpParent[i] i; functionint(int) tmpFind [](int x) { while (tmpParent[x] ! x) { tmpParent[x] tmpParent[tmpParent[x]]; x tmpParent[x]; } return x; }; auto tmpUnite [](int a, int b) { a tmpFind(a); b tmpFind(b); if (a ! b) tmpParent[a] b; }; for (auto [a, b] : tmpEdges) { tmpUnite(a, b); } // 第三步统计每个组件内部的点数 vectorlong long compSize(cnt, 0), compSq(cnt, 0); for (int i 0; i cnt; i) { int c tmpFind(i); long long s dsu.sz[roots[i]]; compSize[c] s; compSq[c] s * s; } // 第四步组件内任意两个不同原连通块之间的点对 // 它们路径的最大边权一定是当前权值 for (int c 0; c cnt; c) { if (compSize[c] 1) continue; __int128 ways128 (__int128)compSize[c] * compSize[c] - compSq[c]; long long ways (long long)(ways128 / 2); ans (ans (ways % MOD) * (edges[p].w % MOD)) % MOD; } // 第五步所有贡献统计完再真正合并主并查集 vectorint rootOfComp(cnt, -1); for (int i 0; i cnt; i) { int c tmpFind(i); if (rootOfComp[c] -1) { rootOfComp[c] roots[i]; } else { dsu.unite(rootOfComp[c], roots[i]); } } p q; } cout ans \n; return 0; }代码看起来有点长但核心逻辑非常清晰外层循环按权值批次处理前四步都在“不修改主并查集”的前提下完成贡献统计第五步才真正合并连通块。这里有几个细节值得强调roots存储的是主并查集在当前批次处理前的根节点dsu.sz[roots[i]]取出的是这些根节点在“本批次之前”的连通块大小临时并查集只在当前批次内生效批次结束后可以直接丢弃。4.3 运行与自测用前面提到的样例跑一下预期输出是 37。5 1 2 5 2 3 1 3 4 2 4 5 4运行结果37再看一个包含同权边的样例4 1 2 3 2 3 3 3 4 1这个样例中1-2 和 2-3 两条边权值都是 3必须按同权批次处理。暴力手算所有 6 条路径的最大边权和是(1,2): 3(1,3): 3(1,4): 3(2,3): 3(2,4): 3(3,4): 1总和为 16。运行代码后输出16说明同权分组处理可以正确处理这类数据。注意这两个样例是我为了验证逻辑自己构造的不是官方示例。但它们的规模很适合用来做算法正确性的初步检查。5. 复杂度分析与对拍验证5.1 复杂度说明完成这道题的时间复杂度由三部分构成对所有边排序O(m log m)其中 m n-1主循环中每条边最多被 find 若干次并查集带路径压缩和按大小合并操作近似 O(m α(m))临时并查集操作也只在当前批次内进行总操作次数与边数同阶。综合下来整体复杂度是 O(n log n)。空间复杂度为 O(n)主要存储并查集和边数组。对于 n2e5 的数据这个复杂度在区域赛通常 1~2 秒的时间限制内都可以通过。5.2 对拍脚本写正解时强烈建议配一个暴力对拍脚本。以下 Python 脚本会生成随机小树调用编译好的sol程序并和暴力结果对比。import random import subprocess import sys sys.setrecursionlimit(1 25) def brute(n, edges): g [[] for _ in range(n 1)] for u, v, w in edges: g[u].append((v, w)) g[v].append((u, w)) total 0 for s in range(1, n 1): def dfs(u, p, mx): nonlocal total if u ! s: total mx for v, w in g[u]: if v p: continue dfs(v, u, max(mx, w)) dfs(s, -1, 0) return total def run_sol(): with open(in.txt) as f: out subprocess.check_output([./sol], stdinf).decode().strip() return int(out) for _ in range(2000): n random.randint(2, 8) edges [] for v in range(2, n 1): u random.randint(1, v - 1) w random.randint(1, 10) edges.append((u, v, w)) with open(in.txt, w) as f: f.write(f{n}\n) for u, v, w in edges: f.write(f{u} {v} {w}\n) got run_sol() expect brute(n, edges) % (10**9 7) if got ! expect: print(WA) print(n) for e in edges: print(*e) print(got, got, expect, expect) break else: print(all ok)使用方式g -O2 -stdc17 sol.cpp -o sol python3 brute_check.py如果脚本输出all ok说明在 2000 组随机小数据上没有出错。这个步骤虽然简单却是竞赛里保证正确率最有效的手段之一。5.3 边界测试建议对拍随机小数据通过后还要专门测几类边界数据n1没有边答案应该是 0n2只有一条边答案是这条边的权值一条链树退化成链所有点对路径最大边权都接近最大权值星形图所有点都连在一个中心点上所有边权相同如果忘了分组处理这个数据很容易暴露问题边权随机但范围很大用来检查是否用了 int 导致溢出。这些测试不一定会暴露逻辑错误但能帮助发现代码里的隐藏问题尤其是溢出和初始化问题。6. 常见错误与调试清单6.1 错误现象速查表问题现象常见原因解决思路答案偏小同权边逐条合并导致部分路径没有被算进同一批次把同权边按批次整体处理用临时并查集分组答案偏大合并后重复计算同一批次的连通块贡献先统计完贡献再真正合并主并查集使用 int 导致负数或溢出答案和中间乘积超过 int 范围统一使用 long long必要时用 __int128临时并查集编号冲突不同根节点映射到同一个临时编号用 unordered_map 或全局数组维护根到编号的映射递归 DFS 爆栈数据是一条长链递归深度太大本方案不需要 DFS天然避免该问题对拍脚本可手动提高递归限制ans 忘记取模题目要求取模但累加时只在最后取模每次累加贡献时同步取模6.2 调试小技巧当你发现对拍结果不对时不要直接盯大样例先做以下几步在每组同权批次统计完成后用cerr输出当前权值、组件大小和贡献检查合并前后的sz是否符合预期如果代码逻辑用到了unordered_map确认映射以后取出的编号是否稳定在暴力脚本中尽量把随机数种子固定住方便复现某一组 WA 数据。其中最常见的问题其实只有一个主并查集合并得太早。只要记住“先算贡献后合并”这个原则大部分错误都能避免。7. 进阶拓展克鲁斯卡尔重构树7.1 重构树是什么这道题还有另一个视角克鲁斯卡尔重构树。做法是把边按权值从小到大排序初始每个节点是独立连通块。处理一条边 (u, v, w) 时新建一个权值为 w 的虚点把它连接到 u 所在连通块的根和 v 所在连通块的根同时合并 u 和 v 所在的连通块。最终你会得到一棵新的树原图的节点是叶子每条原图的边对应一个内部节点。这棵树有一个重要性质原图中两个节点之间的路径最大边权等于它们在重构树上的 LCA 的权值。7.2 本题与重构树的关系如果使用重构树原问题就可以转化成对每个内部节点统计它的左右子树大小乘积乘上该内部节点的权值累加即可。这和并查集的贡献公式实际上是同一个过程只是重构树把“离线排序 并查集”的过程显式地保存成了一棵树。好处是它可以支持在线查询给你任意两个点问路径最大边权直接回答 LCA 权值。很多出题人会把这类题包装成“在线询问”版本此时克鲁斯卡尔重构树就是标准解法。7.3 可以迁移的同类问题掌握了这个套路之后下面这些题都可以用类似思路解决求所有点对路径最小边权和按边权从大到小排序贡献公式不变求所有点对路径最大边权的最小值瓶颈路就是最小生成树上的问题给定若干询问求两点之间路径最大边权用重构树 LCA求所有以某条边为最大边的路径数量并查集维护可达块即可。这类问题的共性在于离线排序后边与边之间存在严格的“大小关系”于是能够用连通块合并来约束贡献范围。8. 竞赛习惯与工程建议8.1 拿到题目后的分析顺序复盘这道题我总结出的做题顺序是先看数据范围估算期望复杂度花两分钟想一个最暴力的做法用来对拍找一找“能不能让每个元素独立贡献”而不是直接枚举所有组合如果有排序相关的条件尝试离线处理写代码前先画一画同权边会不会造成歧义。这套流程看起来简单但能避免很多无效的深挖。8.2 写代码时的工程细节竞赛代码虽然短但也有一些值得坚持的习惯变量名尽量见名知义parent、sz、compSize比p、s、c更不容易写错所有中间乘法都用 long long权值和大小相乘时优先考虑 __int128主并查集的合并操作要集中在统计结束以后临时并查集不要复用主并查集的 parent 数组否则会被路径压缩干扰对拍脚本里保存第一组 WA 数据然后单独跑这组数据定位问题。这些习惯在压力很大的 ICPC 赛场上非常有用能帮你减少因为低级错误浪费的时间。9. 复盘总结这道 C 题让我印象最深的一点是它不考任何冷门算法但如果你一上来就盯着“路径最大值”看思路很容易卡死。而一旦切换到“每条边贡献了多少条路径”所有步骤都变得顺理成章。建议读者不要只抄代码而是自己重新推一遍贡献公式然后用对拍脚本验证。尤其要把同权边分组处理单独拎出来做几组测试因为这是最容易被忽略、也是最容易出错的点。下次再遇到“最大边权贡献”“最小边权贡献”相关的树上统计题先想想能不能按权值排序 并查集维护连通块你会在赛场上省下很多时间。