匿名用户·2026/5/16markdown1# 货物运输 题解 2 3## 题目分析 4 5本题给定一棵包含 $n$ 个节点的树，边带权值。要求从首都（1号节点）出发，遍历所有城市（即访问所有节点），途中可以多次经过同一个节点，最后无需返回首都。目标是最小化经过的道路总长度。 6 7换句话说，我们需要找到一条从固定起点 $1$ 出发、覆盖树上所有节点的路径，并使得路径总长度最小。 8 9## 解题思路 10 11### 1. 问题转化 12 13在树上遍历所有节点，如果要求**最终必须回到起点**，那么根据树的性质，每一条边都至少要被经过两次（一去一回），因此最短路径总长度为 **$2 \times$ 树上所有边权之和**。 14 15但本题允许**最后不返回起点**，这意味着我们可以节省一条从起点到某个终点的“返程”路径。显然，为了让节省的长度最大，我们应该让终点离起点越远越好。这样，从起点到终点的路径上的边只需要走一次，而所有其它边仍然要走两次。 16 17因此，最小总长度为： 18 19\[ 20\text{ans} = 2 \times \sum_{e \in E} w_e - \text{max\_dist} 21\] 22 23其中 $\text{max\_dist}$ 表示从起点 $1$ 到树上任意节点的最长距离（即**树中以 $1$ 为根的最大深度**）。 24 25### 2. 算法说明 26 271. **建图**：使用邻接表存储树结构，每条边存储邻居节点编号及边权。 282. **求总边权和**：在读入边的过程中累加所有边权得到 $s$。 293. **求最大深度**：从起点 $1$ 开始做一遍深度优先搜索（DFS），计算从根到每个节点的距离，并维护最大值 $mx$。 304. **计算答案**：输出 $2 \times s - mx$。 31 32### 3. 为什么不需要考虑其他路径？ 33 34有些同学可能会想：能不能通过走某些边只走一次，而让另外一些边不走两次？由于树没有环，要访问所有节点，除了起点到终点这条路径上的边可以走一次，其余每条边都必须走两次（进入子树并返回）。因此上述策略是最优的，证明思路如下： 35 36- 访问每个子树时，必须进入子树并最终离开（除非终点在该子树内），进入和离开需要经过连接子树的边两次。 37- 只有终点所在的子树路径上的边可以只走一次。 38- 选择离根最远的节点作为终点，能最大化只走一次的路径长度，从而最小化总长度。 39 40## 时间复杂度分析 41 42- 读入边并累加边权和：$O(n)$ 43- 一次 DFS 遍历所有节点：$O(n)$ 44- 总时间复杂度：$O(n)$，空间复杂度：$O(n)$ 45 46在 $n \le 10^5$ 的数据范围下，该算法可以高效运行。 47 48## 参考代码及解释 49 50```cpp 51#include <algorithm> 52#include <cstdio> 53#include <vector> 54 55using namespace std; 56 57const int N = 1e5 + 5; 58 59int n; 60vector<vector<pair<int, int>>> e; // 邻接表，pair<邻居, 边权> 61 62long long s, mx; // s: 总边权和, mx: 从根出发的最大距离 63 64// 深度优先搜索，计算从根到各点的距离 65// u: 当前节点, f: 父节点, d: 当前走到的距离 66void dfs(int u, int f, long long d) { 67 mx = max(d, mx); // 更新最大距离 68 for (auto p : e[u]) { 69 if (p.first != f) { // 避免回到父节点 70 dfs(p.first, u, d + p.second); 71 } 72 } 73} 74 75int main() { 76 scanf("%d", &n); 77 e.resize(n + 1); 78 for (int i = 1; i < n; i++) { 79 int u, v, w; 80 scanf("%d%d%d", &u, &v, &w); 81 e[u].emplace_back(make_pair(v, w)); 82 e[v].emplace_back(make_pair(u, w)); 83 s += w; // 累加边权 84 } 85 dfs(1, 0, 0); // 从根 1 开始遍历 86 printf("%lld\n", s * 2 - mx); 87 return 0; 88}
vector<vector<pair<int, int>>> e 建图，每个元素是一个 pair，存储相邻节点编号和边权。mx = max(d, mx) 更新最远距离。s * 2 - mx，注意使用 long long 防止溢出（li≤109，n 条边，总和可达 1014 级别）。本题看似复杂，但通过将“遍历所有节点”转化为对树边的访问次数的分析，可以发现它等价于求 2×总边权和−从起点出发的最长路径。这是树上遍历类问题的一个经典结论，适合作为树基础算法的综合练习题。