题目描述
A 国有 n 座城市，依次以 1,2,…,n 编号，其中 1 号城市为首都。这 n 座城市由 n−1 条双向道路连接，第 i 条道路（1≤i<n）连接编号为 ui,vi 的两座城市，道路长度为 li。任意两座城市间均可通过双向道路到达。
现在 A 国需要从首都向各个城市运送货物。具体来说，满载货物的车队会从首都开出，经过一座城市时将对应的货物送出，因此车队需要经过所有城市。A 国希望你设计一条路线，在从首都出发经过所有城市的前提下，最小化经过的道路长度总和。注意一座城市可以经过多次，车队最后可以不返回首都。
输入格式
第一行，一个正整数 n，表示 A 国的城市数量。
接下来 n−1 行，每行三个正整数 ui,vi,li，表示一条双向道路连接编号为 ui,vi 的两座城市，道路长度为 li。
输出格式
一行，一个整数，表示你设计的路线所经过的道路长度总和。
输入输出样例
输入 #1
4 1 2 6 1 3 1 3 4 5
输出 #1
18
输入 #2
7 1 2 1 2 3 1 3 4 1 7 6 1 6 5 1 5 1 1
输出 #2
9
说明/提示
对于 30% 的测试点，保证 1≤n≤8。
对于另外 30% 的测试点，保证仅与一条双向道路连接的城市恰有两座。
对于所有测试点，保证 1≤n≤105，1≤ui,vi≤n，1≤li≤109。
题目大意
在树结构中，从根节点（首都1）出发遍历所有节点，最小化路径长度（无需返回根）。
考纲知识点
数据结构（树的遍历、树的最长路径）、递归/ DFS
解题思路
1.树的特性：树无环，遍历所有节点必须经过每条边至少一次；
2.最小路径推导：
若需返回根节点，路径长度为 “总边权和 ×2”（每条边去一次、回一次）；
题目要求无需返回根节点，因此可减去 “根到最远节点的路径长度”（最长路径，无需返回）；
步骤：
·计算所有边的总长度s；
·用DFS 找到根节点1 到任意节点的最长路径长度mx；
·最小路径长度= 2×s - mx。
【参考程序】
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n;
vector<vector<pair<int, int>>> e;
long long s, mx;
void dfs(int u, int f, long long d) {
mx = max(mx, d);
for (auto p : e[u]) {
if (p.first != f) dfs(p.first, u, d + p.second);
}
}
int main() {
scanf("%d", &n);
e.resize(n + 1);
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u].emplace_back(make_pair(v, w));
e[v].emplace_back(make_pair(u, w));
s += w;
}
dfs(1, 0, 0);
printf("%lld\n", s * 2 - mx);
return 0;
}