小A与欧拉路

题解：
欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边只通过恰好一次

问你走完这树上所有的点最短路径是什么。
因为树是没有环的，所以你走到叶子结点的时候需要往回走，也就是再走一遍刚刚走过的路。

所以我们确定一条主道路，遇到分支就走一遍（主道路是不需要走两遍的）。
因为所有长度都是已知的，所以最短路径也就是尽量让这一条主路变长。
想一想最长的一条主路，那不就是树的直径吗。
用所有路径长度*2-树的直径即为答案。
两次dfs求树的直径

/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long

#define endl '\n'
#define Accepted 0
#define AK main()
#define I_can signed
using namespace std;
const int maxn =2e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;

vector<pair<int,int> > edge[maxn];
int ans,sum,node;
bool visited[maxn];
void dfs(int x,int fa,int now){
    if(ans<now){
        ans=now;
        node=x;
    }
    for(auto i:edge[x]){
        int v=i.first;
        int w=i.second;
        if(v==fa) continue;
        if(!visited[v]){
            dfs(v,x,now+w);
        }
    }
}

signed main(){
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int x,y,z;
        cin>>x>>y>>z;
        edge[x].push_back(make_pair(y,z));
        edge[y].push_back(make_pair(x,z));
        sum+=z*2;
    }
    dfs(1,-1,0);
    dfs(node,-1,0);
    cout<<sum-ans<<endl;
    return 0;
}