思路

题目要遍历到所有结点，在一棵树中，通过画图可以发现，根节点是起点，终点任意。最后我们求出的路径一定是所有结点之间的路径要走两遍（因为要走完全部路程），而起点到终点的距离只需要走一遍即可。
假设树中所有结点之间的距离为 $Sum$，起点到任意结点的距离为 $ P $，我们要求的最短距离 $S$ 即为：
$$ S_{min} = 2 \times sum - P_{max} $$
故求出根节点到其他节点的最大距离即可。通过dfs遍历得到所有结果带入公式即可。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, M = 2e5 + 10;

int h[N], e[M], ne[M], w[M], idx;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

// 递归求出从根节点到其他节点的距离的最大值
int dfs(int u, int fa)
{
    int path = 0;       // 存储从根节点开始到其他结点路径的最大值
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;      // 递归遍历到当前节点的父结点时跳过不参与计算防止计算重复路径
        path = max(path, dfs(j, u) + w[i]);     // 更新距离的最大值
    }
    return path;
}

int main()
{
    memset(h, -1, sizeof h);        // 初始将邻接表置空
    int n;
    LL sum;                         // 存储所有距离的两倍
    cin >> n;
    for (int i = 1; i<n; i++)
    {
        int a, b ,c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
        sum += 2 * c;
    }
    cout << sum - dfs(1, -1);
    return 0;
}