其实这道题我在刷蓝桥杯历年真题的时候第一眼看到就被骗了。你以为要处理什么马车路线、城市路网的复杂图论吗并不是剥开题目描述之后它实际上是一个很经典的“树的直径”模型而且这个知识点在省赛A组出现的频率非常高。如果你正准备刷蓝桥杯真题尤其是C组或者Python组这道“大臣的旅费”可以说是一道非常有代表性的题目它不像模拟题那样考你耐心而是直接考你能不能把现实问题抽象成树结构并写出高效的遍历逻辑。这篇文章我就用完整拆解的方式把题意、算法原理、代码实现、常见坑一次讲透保证你下次碰到“求树上最远两点距离”这类题能直接套模板。1. 题目在说什么题意重述与费用推导1.1 从题干里能读到什么关键信息题干背景我尽量不说废话直接提炼出几个关键点有 n 个城市城市之间有 n-1 条路而且整个道路网络是连通的。每条路有长度单位是“千米”。大臣从任意一个城市出发去另一个城市路费不是按固定“每千米多少钱”来算而是采用阶梯递增走第 1 千米花费 11 元走第 2 千米花费 12 元走第 3 千米花费 13 元也就是第 k 千米花费 (10 k) 元。题目要求计算从某个城市到另一个城市最多需要多少路费。这里最重要的抽象就是n 个节点n-1 条边且连通——这不就是一棵树吗只要看到这个条件就应该条件反射想到“树”。树的结构带给我们一个很好的性质任意两个节点之间的路径是唯一的不存在两条不同的路都能从 A 走到 B。所以“最多路费”这个问题就转化成了“这棵树上哪条路径最长”也就是求树的直径。为什么不是图论里的最短路因为在树里没有“绕路”这个概念A 到 B 只有一条简单路径没有多种选择。我们真正要做的就是找到距离最远的那一对点。1.2 旅费公式等差数列约束下的数学模型很多新手会在最后一步翻车因为他们千辛万苦算出了最长距离 L结果直接 cout L丢了一半的分。题目要的是路费不是距离。路费按递增方式计算第 1 千米11 元第 2 千米12 元第 3 千米13 元……第 L 千米(10 L) 元这是一个首项为 11、末项为 (10 L)、项数为 L 的等差数列。按照等差数列求和公式总路费 (首项 末项) × 项数 ÷ 2总路费 (11 10 L) × L ÷ 2总路费 (21 L) × L ÷ 2也可以把它拆开写成更不容易溢出的计算形式总路费 L × 10 L × (L 1) / 2两种写法结果一样。我个人习惯用后面这个L × 10 是“每千米额外的基础 10 元”L × (L 1) / 2 是依次累加的 1 到 L 那部分。例如 L 2 时实际路费应该是 11 12 23 元套公式2 × 10 2 × 3 / 2 20 3 23完全一致。这里有一个隐藏很深的坑题目里 n 可以达到上万甚至十万级别道路长度也可能到上千那么树的直径 L 可能达到 10^7 这个量级再套公式算总路费是 10^7 × 10 10^7 × (10^7 1) / 2早就超过 int 的范围了。所以所有涉及距离和费用的变量一律用 long long这一点非常关键。2. 核心算法思路为什么是“树的直径”2.1 两遍DFS求直径的完整原理树的直径定义就是树上最远的两个节点之间的距离。求直径有很多种方法最经典的算法是“两遍 DFS”或“两遍 BFS”从任意一个节点 u 出发通过 DFS/BFS 找到离 u 最远的节点 s。再从 s 出发通过 DFS/BFS 找到离 s 最远的节点 t。s 到 t 的距离就是树的直径。为什么这个算法是对的我记得第一次看到这个结论的时候也觉得有点“玄学”总怕第一遍找的 s 不是直径端点。但仔细想一下在一棵正权树上从任意点出发找到的最远点一定位于某条直径的端点。这个结论可以用反证法证明过程这里不展开细说但是结论要记住。正是因为所有边权都是正数两次 DFS 才能成立如果存在负权边这个结论会被破坏需要改用树形 DP 或者其他方法。好在这道题所有路程都是正数所以可以直接用两遍 DFS实现简单又不容易出错。注意这个节点 s 是哪一个并不重要关键是它一定在直径的一端。所以从 s 再跑一遍找到离它最远的 ts 到 t 的距离就是整棵树的直径。整个过程的时间复杂度是 O(n)因为两遍遍历每遍每个点每条边都访问一次。2.2 备选方案树形DP求直径除了两遍 DFS还有一种常见做法是树形 DP。设 dp[u] 表示以 u 为根的子树中从 u 往下走到某个叶子节点的最长距离。那么对于每个节点 u遍历它的子节点 v更新答案的时候用ans max(ans, dp[u] dp[v] w)然后再更新dp[u] max(dp[u], dp[v] w)这里 dp[v] w 就是从 u 出发经过 v 这条边能走到的最远距离。每次在合并两条不同子树路径的时候就有机会让两条路径“拼”起来形成一条经过 u 的最长链这就是直径的候选值。跟两遍 DFS 相比树形 DP 的好处是即使边权是负数它也能处理因为它是通过“拼路径”而不是依赖“最远点必在直径端点”这个性质。不过这道题完全用不上负权而且树形 DP 的代码稍长一点很多蓝桥杯选手反而容易在递归更新顺序上写错。我个人建议比赛里看到这种正权树求直径优先写两遍 DFS代码短、思路直观、容错率高。2.3 算法选型为什么两遍DFS更契合本题这道题给的数据范围虽然不大但考试现场的思考成本很重要。两遍 DFS 只要维护一个 dist 数组代码量控制在 30 行以内不容易出 bug。树形 DP 则需要考虑子树合并顺序而且最后得到的是“最长路径长度”而不是某个端点的位置。如果题目只是要求输出距离或费用树形 DP 也行但两遍 DFS 还能顺便让你记录下直径端点后续如果要输出路径改造起来也更方便。另一个原因是蓝桥杯省赛的判题环境对递归栈的默认大小在不同版本编译器上不太一样但 n 在 10^4 到 10^5 这个范围时C 默认递归深度一般够用。如果你实在担心递归爆栈第二遍 DFS 可以改成 BFS队列实现稳得很。关于递归栈的问题我在后面第三节详细讲。3. 完整实现与工程细节3.1 邻接表建图选vector还是链式前向星先确认一个基本问题这是一棵树可以看作稀疏图n 个点只有 n-1 条无向边。存图的时候不能开 n × n 的二维数组因为 n 上万之后内存直接爆掉。正确做法是邻接表。C 选手最常见的两种邻接表写法vector 存 pairvectorpairint, int g[N];每次加边g[x].push_back({y, z}); g[y].push_back({x, z});链式前向星用 head、to、w、nxt 数组模拟链表。我自己的习惯是在蓝桥杯这种单机判题场景vector 写法足够代码也更直观。链式前向星更省内存、遍历更快但代码量明显增加而且容易写错数组下标。以前我在洛谷刷题时也遇到过大 n 的题vector 加 reserve 之后性能完全能打。所以不是性能极端吃紧的题别用链式前向星折磨自己。Python 选手就直接用列表套列表g [[] for _ in range(n 1)]每个元素存(邻接点, 边权)的元组简单清晰。3.2 C完整代码与逐段注释下面这份代码是完整可提交的 C17 版本核心思路就是两遍 DFS#include bits/stdc.h using namespace std; const int N 100005; int n; vectorpairint, int g[N]; long long dist[N]; void dfs(int u, int fa) { for (auto edge : g[u]) { int v edge.first; int w edge.second; if (v fa) continue; dist[v] dist[u] w; dfs(v, u); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 0; i n - 1; i) { int x, y, z; cin x y z; g[x].push_back({y, z}); g[y].push_back({x, z}); } // 第一遍从1出发找最远点s dfs(1, 0); int s 1; for (int i 1; i n; i) { if (dist[i] dist[s]) s i; } // 第二遍从s出发找最远点得到最长距离 maxD memset(dist, 0, sizeof(dist)); dfs(s, 0); long long maxD 0; for (int i 1; i n; i) { maxD max(maxD, dist[i]); } // 等差数列求和第1千米11元第2千米12元...第maxD千米(10maxD)元 long long ans maxD * 10 maxD * (maxD 1) / 2; cout ans endl; return 0; }这里有一个小细节是 dfs 传参的时候传入父节点 fa是为了避免在无向图遍历时走回父节点否则会死循环。如果你用 BFS 写法就需要一个 visited 数组或者记录父节点原理一样。很多人在第一遍 DFS 之后清空 dist 数组会用循环for (int i 1; i n; i) dist[i] 0;其实 memset 也可以但注意 memset 是按字节清的对 long long 数组清零没有问题。这里我对 dist 用了 memset本质上是把所有字节置 0long long 类型的 0 的二进制表示本来就全 0所以安全。3.3 数据规模与long long避坑为什么强调 long long我用一个极限数据推算一下。假设蓝桥杯数据里 n 为 10000每条路径长度最大可能到几千甚至更大树的直径 maxD 很可能达到 10^7。套公式maxD 10000000 时ans 10000000 × 10 10000000 × 10000001 / 2ans ≈ 100000000 50000005000000ans ≈ 50000105000000这个数字是 5 × 10^13 级别int 最多只能存到 2.1 × 10^9差了整整一万倍。所以只要你想拿满分距离变量、答案变量都必须是 long long。还有一个容易忽略的点maxD * (maxD 1) / 2如果所有变量都是 int计算过程中就会溢出即使最后赋值给 long long 也已经晚了。因为 C 的运算结果是按操作数类型决定的两个 int 相乘的结果还是 int溢出发生在赋值给 long long 之前。所以务必要让 maxD 本身是 long long或者强制转换。我上面代码里 maxD 直接是 long long所以没问题。Python 就没有这个困扰因为 Python 的 int 是大整数不会溢出但同样要注意效率。3.4 DFS爆栈风险什么时候改用BFS或迭代平时在本地测试小数据递归 DFS 怎么递归都没事。一旦 n 到 10^5、10^6树的形状如果是一条链递归深度就会接近 n。C 默认的函数调用栈空间通常只有 8MB 左右递归层数太深就会爆栈程序直接崩溃。这时候有两种解决思路第一种递归改 BFS。因为树的直径两遍 BFS 也能做BFS 用队列模拟不涉及函数递归栈安全性最高。void bfs(int s) { queueint q; vectorbool vis(n 1, false); dist[s] 0; vis[s] true; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (auto edge : g[u]) { int v edge.first; int w edge.second; if (vis[v]) continue; vis[v] true; dist[v] dist[u] w; q.push(v); } } }第二种加大递归栈。Linux 下的 G 可以使用ulimit -s unlimited或者编译选项但蓝桥杯的判题环境你没法控制所以最稳妥的还是用 BFS。还有一个折中方案在代码开头手动扩栈。C 里可以这样写#pragma comment(linker, /STACK:102400000,102400000)但这个只对 Windows 下的 MSVC 有效Linux 下 GCC 通常忽略。所以实际比赛中我还是推荐 BFS代码虽然多了一点但完全不需要担心递归爆栈性价比很高。4. 验证与调试从样例到造数据4.1 手算样例验证题目自带的样例我重新摆出来方便对照输入5 1 2 2 1 3 1 2 4 5 2 5 4这个样例构成的树最长路径是哪一条我画一下节点关系1 连接 2边长 2和 3边长 12 连接 4边长 5和 5边长 4从节点 4 到节点 5 的距离是 5 2 4 11。从节点 4 到节点 3 的距离是 5 2 1 8。从节点 5 到节点 3 的距离是 4 2 1 7。所以直径明显是 4 到 5距离 L 11。套费用公式ans 11 × 10 11 × 12 / 2 110 66 176题目样例输出确实是 176说明公式和算法都对。4.2 自造测试样例的思路在本地调试的时候不要只跑题目自带的样例那样测不出来边界问题。我会自己造几组数据第一组最简单只有 2 个城市1 条路。2 1 2 5这组数据直接验证答案是否为 5 × 10 5 × 6 / 2 50 15 65。程序如果输出 65说明基本流程没问题。第二组链状结构极端深度6 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1这是 6 个点连成一条直线直径就是 1 到 6距离 5答案 65。如果把 n 换成 100000就能顺便测试递归会不会爆栈。第三组星形结构5 1 2 1 1 3 2 1 4 3 1 5 4这是所有节点都直接连到中心节点 1那么直径是 4 3 7 或者 4 2 6 里最大的节点 5 到节点 4 的距离是 4 3 7答案 7 × 10 7 × 8 / 2 70 28 98。这几种数据分别覆盖了简单情况、极端深度、多分支聚合能帮你快速定位算法和代码里的大部分问题。4.3 沙盘推演一个典型的调试过程我记得有一年我重新刷这道题的时候第一遍代码写完直接提交结果只过了一半的数据。排查了一下发现是变量类型的问题我计算 ans 的时候把 maxD 定义成了 int然后在公式里先做了 int 乘法再赋给 long long直接溢出。另一个印象很深的坑是第一遍 DFS 之后我的 dist 数组没有清干净。因为第二遍 DFS 又从起点 s 开始加起点 s 的 dist 应该为 0但如果不清空旧值还在第二遍从 s 出发访问相邻节点时算出的 dist 会凭空多出一段距离。这个问题在数据量小的时候不容易发现一旦树的路径变长结果就差得很离谱。所以调试的时候最好的办法就是在第一遍 DFS 后打印 s 的位置和第二遍 DFS 后的 dist 数组用自造的小样例对照每一个节点的距离是否和手算一致。一旦发现某个节点 dist 不对优先检查是不是忘了判断父节点或者是不是 dist 没有清零。5. 常见问题速查与避坑实录5.1 高发错误清单与解决方法我把这道题容易踩的坑整理成了一张表提交之前可以对照自查问题现象根本原因解决方法答案偏小且在大数据时变成负数int 类型在乘法或加法过程中溢出所有距离、费用变量使用 long long程序栈溢出崩溃树退化成链递归深度过大改用 BFS或使用迭代栈实现 DFS答案比预期大很多两次 DFS 之间的 dist 没有清零第二遍 DFS 前重置 dist 数组遍历死循环无向图 DFS 时没跳过父节点记录 fa 参数v fa 时 continue输出的是距离而不是费用忽略题目要求只求了最长距离最后一步用等差数列公式计算费用建图之后漏了反向边无向边只加了一次导致部分点不可达x-y 和 y-x 都要加入邻接表输入 n 的含义理解错误以为 n 是边数循环 n 次读边n 是点数边数是 n-1循环 n-1 次这里面最让人头疼的就是第三类dist 没清干净。因为当你的树比较平衡、深度不大时第一遍 DFS 后 dist 里有些点的距离可能没有参与第二遍运算导致答案碰巧是正确的但一旦数据变成链状旧 dist 值会影响所有后续点。我的建议是把“清空 dist”和“第二遍 DFS”这两步绑定在一起写完第二遍 DFS 的调用之后立刻检查之前有没有清空。还有一个比较隐蔽的问题是有的蓝桥杯版本题目会给出多组测试数据吗这道题是不会的但如果你在练习平台上做题要养成分组读入的习惯注意是否有多组样例。不要因为不是多组测试就忽略输入缓冲的问题ios::sync_with_stdio(false)记得加能加快不少速度。5.2 这道题背后的蓝桥刷题建议刷蓝桥杯真题的时候我一直觉得最重要的不是刷题数量而是你能不能把一个经典模型真正吃透。比如“大臣的旅费”这道题本质是树上最长路径但换个包装它又可以变成“求树上最远的两个苹果之间的距离”“求某种网络里的最大延迟”等等。如果你只是背代码不理解两遍 DFS 的原理遇到变形题照样不会做。所以我在刷题的时候有个习惯每道经典题除了 AC还会额外想想它能变形成什么样子比如把边权改成点权怎么办把树改成基环树怎么办把求最长路改成求次长路怎么办。这些思考才是真正提升算法水平的地方。另外很多初学者刷题有一个误区一开始就刷难题结果被打击到怀疑人生。正确的打开方式是先保证简单题和中等题的正确率和速度再用经典题来建立模型库。“大臣的旅费”这种题就是非常值得放进模型库的它既考了图的基本存储又考了树的经典结论还考了数学公式推导和数据范围判断一题顶四题。我个人在实际编程里还有一个体会无论用 C 还是 Python都要养成“边写边验证”的习惯。这道题你不妨先用 Python 写一版列表存图加递归函数总共不超过 30 行跑通后总结出思路再用 C 实现细节优化。这个过程能帮你建立很扎实的代码感觉。最后再分享一个小技巧每次提交蓝桥杯的题目之前先把样例复制到本地跑一遍一定要亲眼看到输出和预期完全一致再交。很多人省赛丢分不是不会做而是输出了多余空格、没开 long long、数组开小这些小问题完全可以在本地被提前揪出来。