GESP 题解库 / 6 级题解 / [GESP202509 六级] 货物运输 · 第 5 / 27 题
GESP202509 六级 · P14076 · 简单

货物运输

从首都出发遍历所有城市(可不返回),最小化走过的道路总长。

📊
n ≤ 10⁵
城市数量
🔢
long long
边长范围
⚡
O(n)
时间复杂度
🎯
2×总边长 − 最长根叶路径
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

A 国有 n 座城市(1 号为首都),由 n−1 条双向道路连成一棵树,第 i 条道路连接 uᵢ、vᵢ,长度为 lᵢ。车队从首都出发,经过每座城市时送出货物,要求经过所有城市,且最后不必返回首都。求经过的道路长度总和的最小值。

💡
人话翻译:这是"树上遍历"的经典结论题。一条边至少要"下去、回来"各一次,所以先按每条边走两遍来算:2 × 总边长。
但最后那段路不需要走回头路——所以我们把最深的那条根到叶路径"省一次"。
答案就是 2 × Σl − maxDist。

🔍 关键词提取

树上遍历欧拉路径最长根叶路径DFS

已知条件

项目说明
输入第一行 n;随后 n−1 行每行 uᵢ、vᵢ、lᵢ
输出经过道路长度总和的最小值
数据范围1 ≤ n ≤ 10⁵
边长1 ≤ lᵢ ≤ 10⁹
起点/终点起点固定为首都市 1,终点任意

需要解决的问题

02
思维导图
整理解题思路的全貌
🚚 2×总边长 − 最长根叶路径
🧠 下界分析
每条边至少走 2 次
因为要下去还要回来
总长至少 2 × Σl
这是基准
✂️ 可以省什么
最后停留点沿途的边只走一次
所以能省下"根到终点"的距离
省得越多越好
所以终点取最远的叶子
✅ 最终公式
答案 = 2 × Σl − maxDist
maxDist = max 根到各点距离
起点固定为根
终点可任选
⚠️ 易错点
写成 2×Σl(忘了可以省)
用 int(可达 10¹⁴)
递归 DFS 爆栈
误以为要返回起点
03
样例手算推导
两个样例的完整计算

🧮 样例 1:4 个城市

道路:1–2 长 6、1–3 长 1、3–4 长 5。

1
第 1 步:总边长

Σl = 6 + 1 + 5 = 12

若全部走两遍:2 × 12 = 24

基准 24

2
第 2 步:各点到根(城市 1)的距离

城市 1:0

城市 2:走边 1–2 → 6

城市 3:走边 1–3 → 1

城市 4:1–3 → 1,再 3–4 → 1 + 5 = 6

距离 = {0, 6, 1, 6}

3
第 3 步:取最大值并相减

maxDist = max(0, 6, 1, 6) = 6

答案 = 24 − 6 = 18

✅ 答案 18

📊 计算汇总

城市到根距离备注
1(根)0起点
26直接相连
31直接相连
461 → 3 → 4 = 1 + 5 = 6,是最远的之一

24 − 6 = 18 ✓

🔑
注意"城市 2 和城市 4 都离根 6",选哪个当终点都行,答案都是 18。这说明"最远距离相同"时方案不唯一,但答案唯一。

🧮 样例 2:一条"折返的链"

道路:1–2、2–3、3–4、7–6、6–5、5–1,长度都是 1。

1
总边长

共 6 条边,每条长 1

Σl = 6 → 2 × 6 = 12

基准 12

2
各点到根的距离

到 2:1;到 3:2;到 4:3

到 5:1;到 6:2;到 7:3

所以这棵树其实是"两条长度为 3 的链"挂在一起

maxDist = 3

3
相减

答案 = 12 − 3 = 9

✅ 答案 9

可以从 1 走到 4(或 7),把另一条链"完整走一个来回"

⚠️
注意样例 2 的形状:题目给的边顺序是打乱的(先出现 7–6、6–5、5–1,再看到 1–2、2–3、3–4),所以不能"按输入顺序"建树,必须用邻接表通用地存图。这是树类题目的常见陷阱。
04
解法对比
结论公式 vs 状压 DP / 暴力搜索

⚔️ 解法对比

🟢 结论公式(推荐) 推荐

2 × 总边长 − 根到最远点的距离

  • 时间 O(n)
  • 一次 DFS/BFS 即可
  • 代码 25 行
  • 有严格的下界证明
💡
严谨的说法:每条边至少走两次(除非它在"最后不回头的路径"上),所以下界是 2Σl − maxDist;而这个下界可以构造达到——以最远点为终点做一次深度优先遍历,沿途其他分支都走"来回"即可。

🟠 搜索所有遍历顺序

枚举访问顺序 / 状压 DP 找最短遍历路径

  • 复杂度指数级
  • n = 10⁵ 完全不可行
  • 只能处理 n ≤ 8 的测试点
  • 属于"杀鸡用牛刀还砍不动"
⚠️
为什么不能搜索:"遍历所有结点的最短路"在一般图上是 NP 难问题,但在树上有简洁结论。树的结构特殊性正是本题能 O(n) 求解的根本原因。

📈 性能对比

方案复杂度可行性
结论公式O(n)✅ 稳过
搜索/状压指数级❌ 不可行
05
算法流程图
统计总边长并求根到最远点距离
开始读入 n 和 n−1 条边;用邻接表存图,累加 Σldis[1] = 0;用栈(或队列)从 1 号城市开始遍历栈非空时取出一个城市 u遍历 u 的每个邻居 vv 是否已经访问过?是 ✓跳过否 ✗dis[v] = dis[u] + 边长,v 入栈maxDist = dis 数组的最大值输出 2 × Σl − maxDist取下一个城市继续遍历
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🚚 最小运输长度

第一行输入 n,随后 n−1 行输入每条边(u v 长度)。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

struct Edge { int to; long long w; };
vector<Edge> g[100005];
long long dis[100005];
bool vis[100005];

int main() {
    int n;
    scanf("%d", &n);

    long long sum = 0;
    for (int i = 0; i < n - 1; i++) {
        int u, v; long long l;
        scanf("%d %d %lld", &u, &v, &l);
        g[u].push_back({v, l});
        g[v].push_back({u, l});          // 双向道路,两边都要存
        sum += l;                        // 每条边都会被算进"两倍"里
    }

    // 用栈做迭代 DFS,避免 n = 10^5 且是链时递归爆栈
    stack<int> st;
    st.push(1);
    dis[1] = 0;
    vis[1] = true;
    long long maxDist = 0;

    while (!st.empty()) {
        int u = st.top(); st.pop();
        maxDist = max(maxDist, dis[u]);
        for (Edge e : g[u]) {
            if (!vis[e.to]) {
                vis[e.to] = true;
                dis[e.to] = dis[u] + e.w;
                st.push(e.to);
            }
        }
    }

    printf("%lld\n", 2 * sum - maxDist);
    return 0;
}
🔑
为什么要用 2 * sum - maxDist 而不是直接累加?因为遍历顺序无穷多,但答案有闭式结论:所有边至少走 2 次(下去回来),唯独"最后不回头的路径"上的边只走 1 次。为了让省的更多,就让这条路径最长——即终点选最远点。
这种"先给出下界、再构造达到下界"的思路是竞赛里证明结论的标准手法。

📖 关键几行怎么看

代码作用为什么这样写
g[u].push_back({v, l}); g[v].push_back({u, l});存双向边道路是双向的
sum += l累加总边长每条边计入"两倍"的基准
stack<int> st迭代 DFS避免递归爆栈
maxDist = max(maxDist, dis[u])记录最远距离它就是可以省下来的那部分
2 * sum - maxDist答案结论公式
⚠️
四个坑:① 只写 2 * sum(忘了终点可以不回头);② 用 int(n × lᵢ 可达 10⁵ × 10⁹ = 10¹⁴);③ 用递归 DFS(n 达 10⁵ 时链状数据会爆栈);④ 只存单向边(导致有些城市遍历不到,dis 仍是初值)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4
1 2 6 / 1 3 1 / 3 4 5
18题面样例 1
7
1 2 1 / 2 3 1 / 3 4 1 / 7 6 1 / 6 5 1 / 5 1 1
9题面样例 2(两条链拼在一起)
10只有首都,不用走路
2
1 2 5
5一条边:下去就行,不用回来
3
1 2 4 / 1 3 4
12两条等长分支:走完一条回来再去另一条 → 4×2 + 4 = 12
✅
自查清单:① 累加了 Σl 吗?② 求了最远距离吗?③ 用 long long 吗?

🚨 易错点清单

⚠️
忘记减 maxDist:终点可以不返回,所以要减掉"根到最远点"的距离。
⚠️
用 int:总长可达 10¹⁴,必须用 long long。
⚠️
递归 DFS:n = 10⁵ 的链状数据会爆栈,用迭代栈。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
n 最大
10⁵
运算量
约 10⁵

时间怎么算的?

空间都用在哪?

邻接表需要存 2(n−1) 条边,加上 dis、vis 数组。

✅ 约 10 万次操作,瞬间完成。本题的关键是想到结论,而不是算法本身。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 树上遍历类问题的常见结论
// 1. 从根出发、走遍所有点、最后回到根:最小长度 = 2 × 总边长
// 2. 从根出发、走遍所有点、最后不必回:最小长度 = 2 × 总边长 − 最远点距离
// 3. 从任意点出发、走遍所有点、最后不必回:
//      2 × 总边长 − 树的直径
//    (第 3 条是更一般的结论,直径用两次 DFS/BFS 求)

// 求树的直径(两次 BFS)
// (1) 从任意点出发 BFS,找到最远的点 A
// (2) 从 A 出发 BFS,找到最远的点 B,AB 距离即直径

// 迭代 DFS 模板(避免爆栈)
stack<int> st; st.push(root); vis[root] = true;
while (!st.empty()) {
    int u = st.top(); st.pop();
    for (auto e : g[u]) if (!vis[e.to]) { vis[e.to] = true; st.push(e.to); }
}

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
树上遍历结论2 × 总边长 − 可省路径所有"走遍全树"的最短路问题
迭代 DFS用栈代替递归n 大且可能链状的树题
直径两次 BFS 求最长路径"任意起点、最后不必回"的遍历
🌟
思考题:如果题目改成"车队最后必须回到首都",答案会怎样?(提示:就不能省任何东西了——每条边都必须"下去再上来",所以答案就是 2 × 总边长。看样例 1:2 × 12 = 24。"终点是否必须回到出发点"直接决定答案公式,这是这类题最需要读清的条件。)