从首都出发遍历所有城市(可不返回),最小化走过的道路总长。
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,终点任意 |
道路:1–2 长 6、1–3 长 1、3–4 长 5。
Σl = 6 + 1 + 5 = 12
若全部走两遍:2 × 12 = 24
基准 24
城市 1:0
城市 2:走边 1–2 → 6
城市 3:走边 1–3 → 1
城市 4:1–3 → 1,再 3–4 → 1 + 5 = 6
距离 = {0, 6, 1, 6}
maxDist = max(0, 6, 1, 6) = 6
答案 = 24 − 6 = 18
✅ 答案 18
| 城市 | 到根距离 | 备注 |
|---|---|---|
| 1(根) | 0 | 起点 |
| 2 | 6 | 直接相连 |
| 3 | 1 | 直接相连 |
| 4 | 6 | 1 → 3 → 4 = 1 + 5 = 6,是最远的之一 |
24 − 6 = 18 ✓
道路:1–2、2–3、3–4、7–6、6–5、5–1,长度都是 1。
共 6 条边,每条长 1
Σl = 6 → 2 × 6 = 12
基准 12
到 2:1;到 3:2;到 4:3
到 5:1;到 6:2;到 7:3
所以这棵树其实是"两条长度为 3 的链"挂在一起
maxDist = 3
答案 = 12 − 3 = 9
✅ 答案 9
可以从 1 走到 4(或 7),把另一条链"完整走一个来回"
2 × 总边长 − 根到最远点的距离
2Σl − maxDist;而这个下界可以构造达到——以最远点为终点做一次深度优先遍历,沿途其他分支都走"来回"即可。枚举访问顺序 / 状压 DP 找最短遍历路径
| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 结论公式 | O(n) | ✅ 稳过 |
| 搜索/状压 | 指数级 | ❌ 不可行 |
第一行输入 n,随后 n−1 行输入每条边(u v 长度)。
点按钮开始 →
#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 仍是初值)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 18 | 题面样例 1 |
7 | 9 | 题面样例 2(两条链拼在一起) |
1 | 0 | 只有首都,不用走路 |
2 | 5 | 一条边:下去就行,不用回来 |
3 | 12 | 两条等长分支:走完一条回来再去另一条 → 4×2 + 4 = 12 |
邻接表需要存 2(n−1) 条边,加上 dis、vis 数组。
✅ 约 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。"终点是否必须回到出发点"直接决定答案公式,这是这类题最需要读清的条件。)