企业官网建设流程全解析

先聊个刷题时常见的感受：东华OJ进阶系列的题，越往后越喜欢考“看起来像模板，实际上要转个弯”的东西。这道“大臣的旅费”就是这样。题面讲的是古代一位大臣要在若干个城市之间出差，城市之间有道路，道路有长度，出差的花费和路程存在一个递增关系，让你算这位大臣可能花掉的最多旅费。我第一次读题，条件反射觉得是“多源最短路径”或者“Floyd全源最短路”，结果一看数据规模，差点把键盘拍烂。真正冷静下来才发现，题目给的是 n 个城市、n-1 条道路，而且保证任意两个城市都能连通——这就是一棵无根树。那问题瞬间变成了：在一棵带权树里找距离最远的两个点，也就是经典的“树的直径”。这篇文章我打算从题意建模、两次遍历求直径的原理、路费公式推导、代码复现到踩坑记录，完整地过一遍，适合刚把DFS/BFS学得差不多、准备进阶图论的同学参考。

1. 先搞清楚题目到底问了什么

1.1 把题面改写成可计算的问题

原题用文言文味道很重的叙述讲了一个出差故事，拆掉故事外皮之后，底层的输入输出结构特别清晰。第一行给一个正整数 n，表示城市数量。后面跟着 n-1 行，每一行是三个整数 p、q、d，表示城市 p 和城市 q 之间有一条长度为 d 公里的双向道路。题目保证 n 个城市通过这些道路连通，不存在孤立城市，也不会出现环。也就是说，任意两个城市之间的通路是唯一的，这就是树的特征。

你要输出的不是“最远距离”本身，而是“最大旅费”。题目里给了明确的费用规则：如果某次行程总路程是 S 公里，那么大臣需要支付的旅费等于 S×10 + S×(S+1)/2。这里的 10 可以理解为每公里固定的车马费，后面的 S×(S+1)/2 是递增的“辛苦费”或者“疲劳补贴”——第 1 公里加 1，第 2 公里加 2，第 3 公里加 3，一直到第 S 公里加 S，累加起来就是 1+2+3+...+S = S×(S+1)/2。所以问题核心是求 S 的最大值，这个最大值就是带权树的直径长度。

1.2 为什么第一反应“最短路”是错的

如果对图论不熟，看到“任意两个城市之间的最大花费”很容易想到 Floyed 或者 Dijkstra。Floyed 可以求所有点对之间的最短路，然后取最大值，但复杂度是 O(n³)。n 哪怕只有 1000，三层循环就要跑 10 亿次，OJ 不给你超时才算奇怪。Dijkstra 做 n 次，复杂度 O(n² log n) 甚至更高，同样扛不住。这个题的正确姿势是利用树的性质——树中任意两点只有唯一一条简单路径，不存在“绕路”的情况，所以“最远距离”不需要在图上搜索所有路径，只需要找到树中相距最远的两个端点，它们之间的路径就是整棵树的直径。树直径的结点对也正好对应着“花费最远”的那两个城市。

2. 两次遍历求树的直径，核心思路在这里

2.1 树的直径到底是什么

在无根树里，我们定义“直径”为：整棵树中任意两个节点之间距离（边权和）的最大值，对应的路径称为直径路径，路径的两个端点称为直径端点。这里有一个很反直觉但非常重要的性质：树的所有直径不一定只有一条，但它们的端点之间有着很强的约束关系，任意两条直径都会共享同一个“中点”区域，而且一条直径的端点一定是某条直径的端点。正是因为这种性质，才可以用“两次遍历”的方法快速把直径找出来。

第一次遍历：从任意一个节点出发（通常选 1 号节点），用 BFS 或 DFS 找到离它最远的节点，记为 A。这个 A 一定是某条直径的一个端点。 第二次遍历：从 A 出发，再去寻找离 A 最远的节点，记为 B。从 A 到 B 的距离就是这棵树的直径长度。

有人会问：为什么任意选一个起点，第一次找出来的“最远点”一定是直径端点？严谨证明要用到反证法和三角形不等式，我在这里说一个直观版本。假设整棵树的真正直径端点是 X 和 Y，任意起点是 S，第一次找到的最远点是 T。如果 T 不是 X 也不是 Y，那么路径 S-T 必然和直径路径 X-Y 有某个交汇点 P。因为 T 是离 S 最远的点，所以 S 到 T 的距离至少不小于 S 到 X、S 到 Y 的距离。比较这几种路径的长度就会发现，从 T 出发到 X 或到 Y 的某一条路径会严格超过直径长度，这就和“X-Y 是直径”矛盾。所以 T 必然也是某个直径端点。这个证明在网上一搜就能找到完整版，考试和面试时记住结论就可以，但要理解它依赖的前提是“树”和“非负边权”。

2.2 用 BFS 还是用 DFS，这里有个大坑

求树的直径既可以写 DFS 也可以写 BFS，思路完全一样，都是两次遍历。但我个人强烈建议在 OJ 上写 BFS，除非你确定数据规模很小。原因很现实：树的深度可能达到 n，如果整棵树退化成链，递归深度就是 10 万甚至 100 万，很多 OJ 的栈空间会直接爆掉，表现为 RE 或者段错误。BFS 用队列模拟，不存在递归栈深的问题，内存占用也很稳定。这道题数据范围如果给到 10 万级别，递归 DFS 风险极大。当然，DFS 的代码看起来更短，如果你想用 DFS，也可以在函数里加上ios::sync_with_stdio(false)等优化，但栈溢出这关不是输入输出优化能解决的。我建议直接用 BFS 一把梭。

2.3 两次遍历和“贪心”的关系

这里要额外提醒一点：两次遍历求直径本质上是利用了树的特殊拓扑结构，不能把它当作通用的“图最远点对”算法。在普通无向图中，任意点出发找最远点、再找最远点，得到的往往不是全局最长路径，而且距离的定义在有环图里也存在多种路径选择。只有在“树”这个前提下，路径唯一，两次遍历才是可靠的。所以写代码之前一定要反复确认题目给的是 n 个点、n-1 条边的连通图，也就是树。

3. 核心细节：建图、公式推导与防溢出

3.1 邻接表怎么搭才不容易出错

这是一个无向带权树，建图的时候必须把一条道路当成两条有向边来存。比如输入3 4 7，表示城市 3 和城市 4 之间有一条长度 7 的公路，那就要在graph[3]里存(4, 7)，同时在graph[4]里存(3, 7)。只存一边会导致遍历时根本走不到另一端的城市，答案毫无悬念地错。

存储结构我推荐vector<vector<pair<int, long long>>>，外层下标是城市编号，内层存“能到达的节点”和“这条边的权值”。如果你对性能要求更高，可以用链式前向星，但在 n 为 10^5 级别时，vector 邻接表已经足够快。唯一要注意的是graph.resize(n+1)，因为城市编号从 1 开始，你如果 resize 成 n，访问graph[n]就越界了，这种错误非常隐蔽，有时候样例能过，大数据点才崩。

3.2 路费公式是怎么来的，为什么要先推清楚

题目给出的费用规则不是直接让你输出最大距离，而是要把最大距离 S 代入一个二次函数。若某次旅行的总路程为 S，总费用 = S×10 + S×(S+1)/2。这个“10”是固定基础费用，可以理解成每公里的车马费；“S×(S+1)/2”是阶梯式的加价，模拟的是“走得越远越辛苦，每多走一公里，这一公里的折损费等于当前公里数”。所以久远的大臣要尽可能选择相距最远的两个城市出差，这样里程 S 最大，费用自然最大。

有一点特别容易踩：计算费用时 S 要用 long long。树有 n 个节点，每两个城市之间的道路距离题目里通常给到 1000 以内，但如果 n=10 万，整棵树被拉成一条链，最大的 S 可能接近 10^8。代入 S×(S+1)/2 后，结果轻松突破 5×10^15，这已经远超 32 位 int 的上限（约 2.1×10^9）。如果你在计算过程中用 int，不仅最终答案会错，甚至中间乘法S * (S + 1)已经溢出成负数，后面怎么算都不对。所以从读入边权开始，就统一用long long或者long long的别名，不要在算到最后才想起来强转。

3.3 起点选了 1 号城市，会不会有问题

不会。第一次 BFS 从任何节点出发都行，因为树是连通的，任意起点都能遍历到所有节点，找出来的“最远点”必然是某个直径端点。从 1 开始只是最常规的写法，你也可以从 0 开始，只要节点编号范围对应上就行。为了避免边界特判，我一般从 1 开始 BFS。如果 n=1，也就是只有一个城市，n-1=0，没有道路，BFS 从 1 出发只会访问到 1，最远距离 S=0，费用也是 0。这个边界情况代码天然能处理，不需要额外判断。

4. 实操复现：C++ 代码与逐步讲解

4.1 BFS 函数怎么设计

写一个 BFS 函数，输入起点 start，作用是返回两个值：离 start 最远的节点编号，以及这个最远距离。距离数组你需要每次 BFS 都重新初始化，别复用上次的结果。我习惯用vector<long long> dist(n+1, -1)，-1 表示这个节点还没被访问过。因为树是连通的，BFS 结束之后所有节点的 dist 都不会是 -1，但还是用 -1 初始化最稳妥，避免出现边权为 0 和未访问状态混淆的情况。

BFS 的过程：把 start 放入队列，dist[start] 设为 0，用一个maxDist变量实时记录当前遇到的最大距离，同时记录对应的farNode。每次从队列头部取出节点 u，遍历它的所有邻居 e，如果dist[e.to] == -1，就把dist[e.to]更新为dist[u] + e.w，然后入队。如果新的距离比 maxDist 大，就更新 maxDist 和 farNode。注意，由于树没有环，每个节点只会被入队一次，不需要额外的 visited 数组，dist 数组本身就已经承担了 visited 的职责。

4.2 完整 AC 代码

下面这段代码在东华OJ上可以直接提交，关键位置我都加了注释。你只需要根据自己机器上的 C++ 版本调整，如果编译器支持 C++11 及以上，auto和vector<pair<int, long long>>都能顺畅运行。

#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Edge { int to; ll w; }; int n; vector<vector<Edge>> graph; // 返回 {最远节点编号, 到该节点的距离} pair<int, ll> bfs(int start) { vector<ll> dist(n + 1, -1); queue<int> q; dist[start] = 0; q.push(start); int farNode = start; ll maxDist = 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; if (dist[e.to] > maxDist) { maxDist = dist[e.to]; farNode = e.to; } q.push(e.to); } } return make_pair(farNode, maxDist); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; graph.resize(n + 1); for (int i = 0; i < n - 1; i++) { int p, q; ll d; cin >> p >> q >> d; graph[p].push_back({q, d}); graph[q].push_back({p, d}); } // 第一次 BFS：从任意节点出发，找到一个直径端点 far pair<int, ll> first = bfs(1); int endpointA = first.first; // 第二次 BFS：从直径端点出发，求另一端点和直径长度 pair<int, ll> second = bfs(endpointA); ll diameter = second.second; // 根据题目的费用公式计算最大旅费 ll ans = diameter * 10 + diameter * (diameter + 1) / 2; cout << ans << "\n"; return 0; }

4.3 逐步解释代码背后的执行流程

假设输入是 5 个城市，道路分别是 1-2（2）、1-3（1）、2-4（3）、2-5（6）。第一次从 1 出发，dist 变成：1=0、2=2、3=1、4=5、5=8。最大的距离是 8，对应节点 5，所以 endpointA 是 5。第二次从 5 出发，dist 变成：5=0、2=6、1=8、4=9、3=9。最大的距离是 9，可能是 4 或 3，任选一个都一样，diameter 记为 9。代入公式，ans = 9×10 + 9×10/2 = 90 + 45 = 135。这就是两个相距最远城市之间大臣的花费。整个流程中，每个节点最多被入队两次，两次 BFS 加起来的复杂度是 O(n)，空间复杂度 O(n)。

4.4 如果 OJ 不止一组测试数据

东华OJ这道题我没有记错的话是单组数据，但你如果平时在别的 OJ 见到同一套题面，也不排除有多组输入。稳健的写法是把cin >> n放进while (cin >> n)循环里，并且在每次处理完一整组数据之后清空 graph。因为每组数据城市数量可能不一样，graph 必须重新resize，否则上一组残留的边会影响下一组。我这里给出的代码默认单组输入，如果你需要改成多组，只要把 main 里面包一层循环，graph 的 resize 放在循环内即可。

5. 踩坑记录与排查技巧

5.1 最隐蔽的问题：距离数组没重置

我第一次用 DFS 写这道题时，犯过一个特别低级的错误：第一次 DFS 跑完之后，dist 数组已经存了一组从起点 1 到各点的距离。第二次 DFS 想直接用同一个 dist 数组，只把起点的 dist 改成 0，结果遍历时发现很多节点 dist 不为 -1，直接被当成“已访问”跳过，第二次遍历根本没法完全展开，得到的“直径”明显偏小。这个问题在 BFS 版本里同样会出现。解决思路很简单：每次 BFS 都新建一个局部 dist，或者手动 fill 成 -1。不要吝啬这一点空间，两次 BFS 各开一个长度为 n+1 的数组，内存完全够用。

5.2 段错误：邻接表只开了一半

题目是无向图，每条道路要存两条有向边。如果你图方便，只在graph[p].push_back({q, d})后没有反向存入graph[q]，那么 BFS 从某个节点出发就只能沿着“单向”走，很多节点根本访问不到，而且对于 n 较大的数据，遍历过程中很可能访问到空的 vector，导致段错误。这个几乎是所有树相关题目新手必踩的坑。排查方式：先用小样例手推一遍，看看从 1 出发是否能到达所有节点，如果发现输出总是偏小或者节点访问不全，第一件事就检查反向边。

5.3 溢出：把 int 换成 long long

可能有的样例数据小，int 能过，但提交之后全红或者只有部分点 AC。这时候就要怀疑是不是数据范围超过了 int。树的直径 S 最大值接近所有边权和，如果 n 是 10 万、每条边权 1000，S 可能接近 10^8，S×(S+1)/2 直接 5×10^15。你不仅要让 diameter 是 long long，graph 里存储的边权也要用 long long。因为dist[u] + e.w这一步如果 e.w 是 int，不会自动提升为 long long 吗？其实在 C++ 中，只要左值 dist[u] 是 long long，右侧的 e.w 会被提升到 long long 再相加，但为了避免隐式转换带来的不直观，我干脆把所有距离、边权都定义为 long long。

5.4 特殊数据：n=1 和链状树

n=1 时没有边，程序读入 0 条道路，第一次 BFS 返回 1 号点，距离 0，第二次 BFS 同样返回 0，输出 0，没问题。链状树是最大的栈溢出风险场景。假如你用递归 DFS 且 n=100000，程序可能在第一次 DFS 就直接爆栈。所以代码里我坚持用 BFS。如果某些 OJ 对 BFS 的 queue 头文件支持不佳，注意包含<queue>或者直接用<bits/stdc++.h>。

5.5 自测数据怎么构造

在提交之前我习惯构造三组数据手测。第一组是最简单的 n=3，三条边的链：1-2 权值 1，2-3 权值 2，期望 S=3，费用 = 30+6=36。第二组是一棵星形树，n=4，中心 1 分别连 2、3、4，权值都是 5，期望 S=10，费用 = 100+55=155。第三组是 n=1，期望输出 0。这三组过了之后再提交，基本能排除绝大多数低级错误。

6. 这题还能怎么玩：扩展与思考

6.1 树形 DP 求直径，另一种思路

两次 BFS 很直观，但有一个前提：边权必须非负。如果题目改成边的长度可以为负，那么“从任意点找最远点”的贪心策略会失效。退一步说，即使边权为正，用树形 DP 也完全可行。思路很简单：任选一个根节点，做一次 DFS，维护dp[u]表示从 u 出发，向它的子树方向走，能走到的最长距离。对于每个子节点 v，边权为 w，先用dp[u] + dp[v] + w更新全局直径 ans，再用dp[v] + w更新dp[u]。这样一次 DFS 就能求出直径。这个做法不需要两次遍历，但理解起来比两次 BFS 稍微绕一点，适合作为进阶练习。

6.2 如果要输出路径怎么办

有些扩展题不只要直径长度，还要输出直径经过的节点。两次 BFS 的做法天然容易扩展：在第二次 BFS 时额外维护一个pre数组，记录每个节点是被哪个节点扩展来的。BFS 结束后，从直径的另一端点 endpointB 沿着 pre 一路回溯到 endpointA，倒序输出的就是完整路径。要注意因为树中路径唯一，pre 不会有分叉。

6.3 如果图不是树，而是带权无向连通图

那这两次 BFS 的方法就完全失效了。原因很简单：图里两个点之间可能有不止一条简单路径，最远点对问题就变成一个非常困难的图论问题，通常涉及 Floyd 或多次 SSAP，复杂度会急剧上升。这也反过来提醒我们，做题第一步永远是识别题目背后的数据结构，知道它是树还是图，决定了整套解法的上限。

我个人做这类题最大的感受是：树的很多性质看起来很“弱”，实际上非常强。比如“路径唯一”，这一个特点直接把所有最短路算法都简化成了树上路径问题。两次 BFS 求直径这个技巧，后来我在很多题里都用到过，包括网络拓扑里的最长链路分析、文件系统里找两个最深文件的路径长度等场景。回到东华OJ这道“大臣的旅费”，核心就三步：读入 n-1 条边建树、两次 BFS 求直径、代入费用公式算答案。把这根链条理顺，代码自然就顺了。