年前刷东华OJ进阶系列的时候被一道叫“大臣的旅费”的题卡了一整个晚上。这题表面是个树形结构求最长路径实际考的是树的直径这个经典模型外加一个容易看走眼的费用计算公式。当时AC之后我复盘了很久决定把完整思路、证明过程和踩坑点都整理出来希望能帮到正在东华OJ刷进阶题的同学。这道题适合已经掌握DFS、BFS和基本图论概念但还没接触过“树的直径”这类经典问题的读者看完你应该能独立手写一遍而且对这类“树上最优路径”问题有更体系化的理解。1. 题目模型与核心思路拆解1.1 先说清楚题目到底要干什么“大臣的旅费”原题描述是一个王国里有若干城市城市之间由道路连接整个结构是一棵树。大臣从某个城市出发去另一个城市出差路费按里程分段计费走的第1千米花费11枚金币第2千米花费12枚金币以此类推也就是第x千米花费10x枚金币。现在要找出从哪个城市到哪个城市能让旅费总额最大。注意两个关键点。第一城市和道路构成的是树不是一般的图所以任意两个城市之间有且仅有一条简单路径。第二题目求的是“旅费最大的那一条路径”这条路径在树上必然是一条从某个叶子节点或任意节点到另一个叶子节点的路径。为什么因为如果路径端点不是叶子那沿着端点继续往外走路径会变得更长费用也必然更大所以最远路径的两端一定挂在树的“尽头”。这道题在东华OJ里属于进阶难度但本质上解法非常经典先用两次DFS求出树的直径再用直径长度套进费用公式。我第一次做的时候第一反应是想用Floyd求全源最短路看到城市数量n的范围最大可以到上万甚至更高就意识到不行O(n^3)根本扛不住。后来才反应过来树这个结构太特殊了n个节点n-1条边完全可以用DFS在O(n)时间内解决问题。1.2 为什么这道题的核心考点是“树的直径”树的直径的定义很简单一棵树中任意两点之间距离的最大值就是这棵树的直径。这个“距离”在带权树里就是路径上所有边权之和。“大臣的旅费”要让费用最大费用又随着路径长度单调递增所以问题就直接转化为找出一条路径使得路径上所有边长之和最大。求树的直径有一种极其简洁的算法任选一个起点DFS/BFS找到离它最远的点u再从u出发DFS/BFS找到离u最远的点vu到v的路径就是直径。我当时看到这个方法第一反应是“这也太草率了吧”但仔细一推确实成立。这个算法依赖一个关键性质在一棵正权树中从任意点出发最远到达的点一定是直径的某个端点。这个性质为什么成立我在后面第2部分会详细证明。这里先建立一个直觉树没有环从任意点出发最远的那个点已经“够到”了树的一端。从这一端再找最远点自然就够到了另一端两端的距离就是全局最大。我后来做别的题目时发现这个“两次搜索”的思路不光能求直径还能顺带求直径上的节点、边等信息是树形结构里一个非常好用的基础工具。1.3 费用计算其实是个等差数列陷阱我在第一版代码里天真地认为费用等于“路径长度乘上一个恒定的单价”。但是题目里说得清清楚楚第1千米11金币第2千米12金币……也就是说每多走1千米这一千米的单价是上一千米单价加1。所以如果路径长度为s千米总费用是费用 11 12 ... (10 s)这是一个标准的等差数列求和首项11末项10s项数s。套公式就是费用 (11 10 s) * s / 2 (21 s) * s / 2也有同学喜欢写成 s * 10 s * (s 1) / 2和上面是等价的一个是等差数列视角一个是“基础费递增加费”视角。我个人觉得 (21 s) * s / 2 更不容易算错因为直接对应首项加末项。这个公式看着简单但坑在于s本身可能是很大的数而s的平方可能直接超过int的范围。我在用C写的时候第一版用了int样例能过一提交就WA。后来看了题目范围估了一下最坏情况s能到几万甚至更高s的平方直接就几个亿甚至几十亿了int必炸。换成long long之后才稳。2. 树的直径原理与证明2.1 两次DFS为什么是对的很多博客直接给结论说“两次DFS求出树的直径”但没解释为什么。如果只是背代码遇到变体题还是会懵。这里我给出一个比较严谨的证明思路用的方法是反证法加分类讨论。假设树的一条直径为端点u0到v0。第一次DFS从任意点s出发找到最远点u。要证明的核心结论是u必定是直径的某个端点要么是u0要么是v0。我们分两种情况讨论。情况一s恰好就在直径u0-v0这条路径上。从s出发走到最远点由于树的分支结构s往外走的所有路径中最远的那条一定会走到u0或者v0不可能走到别的地方还比它们更远。因为假设存在着一个点x满足dist(s, x) dist(s, u0)且dist(s, x) dist(s, v0)由于s在直径上那么dist(u0, x) dist(u0, s) dist(s, x) dist(u0, s) dist(s, v0) dist(u0, v0)这条路径就比直径还长矛盾。所以u一定是直径端点。情况二s不在直径上。设s往直径u0-v0引一条路径最早触碰到直径的点为t。s找最远点的过程中路径s到x会经过t。又有两种子情况。如果x在t的某个非直径分支上那么dist(t, x) ≤ max(dist(t, u0), dist(t, v0))否则会出现比直径更长的路径矛盾。所以u还是直径端点。如果x不在非直径分支上那x直接就是u0或v0。这个证明的核心思想就是反复利用“直径是全局最大路径”这一性质用反证法排除所有“最远点不是直径端点”的可能。我第一次自己推的时候卡在情况二后来画了很多棵树才想明白。建议你也拿张纸画几棵奇形怪状的树把每个点的最远点标出来体会会更深。2.2 为什么必须用DFS/BFS而不是其他方法既然要反复做“从某个点出发找最远点”这个操作自然想到DFS或者BFS。在无权树上BFS天然按层遍历第一次到达某个点就是最短距离实现也很直观。在带权树上DFS代码更简单递归加一个dist参数就行。两者时间复杂度都是O(n)。相比之下Floyd是O(n^3)Dijkstra跑n次是O(n^2 log n)在这道题的数据范围下都不可行。树只有n-1条边用邻接表存储DFS每个点和每条边只会访问一次线性复杂度这才是正解。这里我想多提一句如果你看到“树”字就想到用邻接矩阵那是把自己带坑里了。邻接矩阵O(n^2)的空间在n10000时就接近瓶颈1亿个int大约400MB而邻接表vectorpairint,int只需要O(n)的空间。这道题不仅卡时间其实也卡空间邻接表是必须的。2.3 直径与“最长路”的关系以及费用表达式的重新理解有些同学可能会把树的直径和“最长路”混为一谈。在树里这两个概念是一致的因为树上两点路径唯一。但在带环图里“最长路”是NP难问题完全不是一回事。这就是为什么“大臣的旅费”限定“城市之间由道路连接整个结构是一棵树”——不是出题人好心而是只有树结构才能用线性算法解决。回到费用表达式。还有一层理解方式把每千米的路费拆成基础价10金币加上里程溢价。走s千米的总费用可以看成s个10金币打底再加上12...s的溢价。前者是10s后者是s(s1)/2。这样拆开之后你会发现费用本质上关于s是二次增长的。这意味着什么当s比较小的时候费用大约随长度线性增长当s比较大的时候s²项占主导增长非常快。所以找最大费用时“路径最长”和“费用最大”完全等价因为函数单调递增。我见过有同学真的用动态规划去算费用或者试图枚举每条路径再算费用那是把简单问题复杂化了。先求距离s再代一次公式两步走干净利落。3. 完整实现从读入到AC的每一步3.1 数据结构选择邻接表存树树是稀疏图节点数n最大可以到100000级别不同OJ版本范围略有差异边数n-1。我采用vectorvectorpairint, int来存图每个元素是一个pairfirst表示邻接节点编号second表示边权道路长度。如果你对pair不太熟也可以用两个平行的vector或者结构体。我个人的习惯是struct Edge { int to; int w; }; vectorEdge graph[MAXN];这样读入和遍历都比较直观。加上起点u、终点v、长度w之后push两条边双向边因为树是无向的graph[u].push_back({v, w}); graph[v].push_back({u, w});有个细节容易漏如果你用邻接表但不加第二条边那DFS从根节点出发就只能往下走会漏掉很多路径答案必错。我第一次写OJ题的时候就在这儿栽过当时还以为是DFS写错了调了半天才发现是建图少了一条边。3.2 第一次DFS从任意点找最远端点这里用DFS递归实现。做法是选节点1作为起点写一个dfs函数维护当前节点、父节点和当前累计距离。为什么要记录父节点因为树是无向图如果不记录父节点DFS会走回上一个节点造成死循环。函数签名大致是这样void dfs(int u, int parent, long long dist) { if (dist maxDist) { maxDist dist; farthestNode u; } for (auto e : graph[u]) { if (e.to ! parent) { dfs(e.to, u, dist e.w); } } }递归终止条件不用显式写遍历完所有邻接点自然返回。dist表示从起点到当前节点u的累计路径长度。每到一个节点就和全局最大值比较一次如果当前距离更大就更新最远节点和最大距离。这里有个小重点farthestNode和maxDist必须是全局变量。每次调用dfs前重置。第一次dfs结束后farthestNode就是直径的一个端点。有同学会问为什么起点选1而不是选0其实都行。节点编号是从1到n的选哪个都不影响结果。原因在上面的证明里无论起点在哪DFS找出的最远点一定是直径端点。3.3 第二次DFS找到直径长度第二次DFS把第一次找到的farthestNode当作起点再做一遍完全一样的搜索。结束后maxDist就是从直径端点到另一个端点的距离也就是树的直径s。这两遍DFS虽然代码一模一样但逻辑上完全不能省略。我见过有人试图只跑一遍DFS取递归过程中的最大深度差当作答案这在某些特殊形态的树比如链上可能碰巧对但对于一般的二叉树或多叉树会漏掉“路径不经过根节点”的情况。比如一棵树根节点下挂着两根长分支最长的路径是这两个分支的叶子之间的路径它经过了根节点只跑一遍DFS从根出发确实能找到。但如果树的形态是根节点下只挂了一个大分支而大分支的某处又分出两条长链最长路径根本不经过根只跑一遍从根出发的DFS就废了。所以老老实实跑两遍不要偷懒。3.4 费用计算从距离到答案拿到直径长度s之后代入费用公式long long ans (21 s) * s / 2;有的版本题目可能把单价规则写成“走第x千米花费x10”那正是上面的公式。如果题目是“每千米固定单价”的变体直接乘就行。但在这道题里一定要用等差数列公式。算完后输出ans。注意如果你使用cout建议直接输出long long变量不要转int。3.5 完整代码C整合起来完整的C解法如下#include bits/stdc.h using namespace std; const int MAXN 100000 5; struct Edge { int to; int w; }; vectorEdge graph[MAXN]; long long maxDist; int farthestNode; void dfs(int u, int parent, long long dist) { if (dist maxDist) { maxDist dist; farthestNode u; } for (const Edge e : graph[u]) { if (e.to parent) continue; dfs(e.to, u, dist e.w); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 0; i n - 1; i) { int u, v, w; cin u v w; graph[u].push_back({v, w}); graph[v].push_back({u, w}); } maxDist -1; dfs(1, 0, 0); int endpoint farthestNode; maxDist -1; dfs(endpoint, 0, 0); long long ans (21 maxDist) * maxDist / 2; cout ans \n; return 0; }这段代码在多数测评OJ上能直接AC。唯一需要注意的就是n的MAXN大小建议开大一点比如100000 5防止RE。3.6 如果题目给的边权很大怎么办有些版本的“大臣的旅费”边权可能比较大比如到1000甚至10000。此时直径s可能达到10^8量级s的平方就是10^16long long仍然能放下但int肯定不行。所以虽然代码里用了long long我还是要强调养成“涉及距离和费用用long long”的习惯别等出了WA才回来改。如果你用Java对应使用longPython则无需考虑溢出但要注意输入输出的性能建议使用sys.stdin.buffer.read这样的快速IO。4. 常见问题与排查技巧实录4.1 样例过了但提交WA问题可能出在哪我排查这类问题有固定套路。第一个怀疑对象是数据类型int vs long long。题目范围估算一下尤其注意是否做了乘法如果距离最大是100000距离平方就是10^10int必炸。第二个怀疑对象是建图是否双向只加一条边的代码不会报错但结果一定错。第三个怀疑对象是DFS起点、终点是否重置全局变量是否被上一次调用污染。这三个检查完基本能解决90%的WA。剩下10%可能是题目输入格式和你想的不一样比如节点编号从0开始或者输入包含多组测试用例。东华OJ这道题一般是单组输入但保险起见还是读一下题面。4.2 递归栈溢出怎么办实际上这里我们需要考虑一个实际问题如果n真的到100000DFS递归深度在最坏情况下树退化成链也是100000层可能会爆系统栈。各OJ的栈空间限制不一样有的给得很大直接递归没问题有的默认栈比较小就可能RE。我用的第一个方案是把递归改成显式栈的迭代DFS这样就不受系统栈大小限制。核心是用stack模拟递归记录状态。但代码稍微复杂一些。第二个方案是直接在代码开头加一句栈扩展指令在一些OJ上有效但不是所有OJ都支持。这里我推荐一种更实用的做法把DFS改成BFS。求最远点不一定要递归用队列做BFS按顺序遍历逻辑一样清晰而且不会爆栈。代码改为void bfs(int start) { vectorlong long dist(n 1, -1); queueint q; q.push(start); dist[start] 0; while (!q.empty()) { int u q.front(); q.pop(); for (const Edge e : graph[u]) { if (dist[e.to] ! -1) continue; dist[e.to] dist[u] e.w; q.push(e.to); } } // 遍历dist找最大值和对应点 }BFS需要一个dist数组空间O(n)没问题。用dist[e.to] ! -1判断是否已访问替代递归里的parent参数思路更直观。我在递归栈溢出问题出现的OJ上改用BFS后一步到位过掉了。4.3 如何高效验证自己的答案有一种很简单有效的自测方法自己构造一条链。把n个节点串成一串边权全部设为1。这时直径一定是n-1费用代入公式算出来就是最大。如果程序输出和这个值不一致说明建图或公式有误。另一种自测方式是随机生成树。你可以用随机数生成n-1条边构造一棵树然后用暴力O(n^2)方法枚举所有点对验证树的直径和你的两次DFS结果对比。小数据下多跑几轮能发现大量隐蔽bug。我当年做这题时写了个暴力对拍脚本测了几十组随机数据才放心提交。这里分享一个非常实用的小工具思路对拍不需要很复杂用Python写个随机生成器同时调用你的程序和暴力程序比较输出即可。花十几分钟搭个对拍环境能救命。4.4 别忽略“无向图”这个隐含条件很多同学做题时看到“城市之间由道路连接”就默认是有向图这是致命的。树的道路肯定是双向通行的否则就成了“有向树”问题性质完全变了。读题时一定要确认这一点。我之前带学弟刷题时他死活想不明白为什么两次DFS找出的点不对。后来发现他把图建成了单向边从1出发只能走向编号比1大的节点第一次DFS找出的“最远点”根本不是真正的直径端点。改成双向边后一次就过了。4.5 关于费用公式的终极提醒有少数版本的题面可能会写“第1千米花费11第2千米花费12……第s千米花费s10”这时候公式不变。但也有的改编题是“每千米单价固定为某值”这时候用等差数列公式就错了。我的建议是拿到题面先不要急着套模板把“费用”这一个条件单独摘出来自己推一遍公式确认是固定单价还是递增单价。这个习惯能避免你在改编题上丢分。“大臣的旅费”之所以有区分度很大程度就在这个费用计算上代码本身反而不是难点。5. 变体与应用场景这道题的思维能扩展到哪里树的直径模型在算法竞赛里非常常见。除了“大臣的旅费”还有很多题目本质就是求树的直径。比如“树上最远点对”“树的直径与最大边权和最小边权”等等。掌握了两次DFS/BFS的方法相当于拥有了一把通用钥匙。有一种常见变体是要求输出直径路径上的具体节点或边。方法是在第二次DFS时记录节点的前驱找到最远节点后回溯即可。这样的代码需要多维护一个parent数组但原理完全一样。另一种变体是求树的半径也就是直径的一半按中间节点或边来定义用两次DFS得到直径后找中点即可。还有一类题目是把树的直径和其他算法结合。比如在树上选一个点使得该点到所有其他点的最大距离最小这就是求树的中心而树的中心一定在直径上。这个结论非常优雅你只需要求出直径然后在直径上二分查找或直接找中点。所以树的直径真的是一个基础中的基础值得花时间吃透。在实际工程中虽然没有哪套系统会直接让你“求树的直径”但很多网络拓扑、社交关系链、通信链路分析的问题抽象出来都是这个模型。比如计算一组局域网节点之间的最大跳数求一棵组播树的最长端到端延迟背后都需要“找到最远两点”的能力。刷题不只是为了AC更是训练这种“把实际问题抽象成经典算法”的思维。我在实际写这个题之前对“两次DFS求直径”的证明一直是一知半解总觉得它像魔术。后来认真推了一遍才发现魔术背后是严密的数学。以后再遇到树的直径相关题目我不再心虚因为我已经不只知道“怎么做”还知道“为什么能这么做”。6. 写在最后的一点刷题建议如果你正在刷东华OJ的进阶系列我的建议是不要只对着题解抄代码一定要亲手把“两次搜索”的每个细节走一遍。尤其像“大臣的旅费”这种题目代码量不大但思维含量不低。你可以试试不看任何参考自己写一个链表式建图版本、一个vector邻接表版本、一个BFS版本三个版本都AC一遍这样对树结构的理解会非常扎实。再分享一个习惯AC之后把代码里所有int改成long long跑一遍再把递归改成BFS跑一遍再构造一个n等于上限的大数据测一下性能。这些额外工作花不了多少时间但能帮你积累宝贵的debug经验。做OJ题AC不是终点把一道题吃透才是赚到。