【问题背景】

zhx 和他的妹子出去玩。

【问题描述】

zhx 和他的妹子去一个国家旅游，共有 N 个旅游景点， N-1 条双向连接的道

路将它们联通起来， 每一条道路有固定长度。 一开始 zhx 位于 1 号景点。

现在希望你能够求出旅行长度最小的方案， 使得每个景点至少被访问到一次。

【输入格式】

第一行两个整数 N， 代表景点数目。

接下来 N-1 行， 每行三个整数 s, t, w， 表示有一条从 s 到 t 的双向道路， 长

度为 w。 s 和 t 的编号从 1 开始。

【输出格式】

一行一个整数， 代表能够访问每个景点至少一次的方案的最小旅行长度。

【样例输入】

3

1 2 3

2 3 3

【样例输出】

6

【样例输入】

3

1 2 3

1 3 3

【样例输出】

9

分析：如果要回到原点，那么树上的每条边都至少要走两次.如果不需要回到原点，那么就停留在离根节点最远的点不回来就好了，ans = 边权和*2-最远距离.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn = 100010;int head[maxn], to[maxn], nextt[maxn], w[maxn], tot = 1, n, sum,maxx;void add(int x, int y, int z){    w[tot] = z;    to[tot] = y;    nextt[tot] = head[x];    head[x] = tot++;}void dfs(int u, int from, int dist){    maxx = max(dist, maxx);    for (int i = head[u]; i; i = nextt[i])    {        int v = to[i];        if (v == from)            continue;        dfs(v, u, dist + w[i]);    }}int main(){    scanf("%d", &n);    for (int i = 1; i <= n - 1; i++)    {        int s, t, w;        scanf("%d%d%d", &s, &t, &w);        sum += 2 * w;        add(s, t, w);        add(t, s, w);    }    dfs(1, 0,0);    printf("%d\n", sum - maxx);    return 0;}