小A与欧拉路(树的直径)

思路：
直接想怎么去加边可能比较难想。
但是虽然欧拉路不太好求，我们可以从欧拉回路着手，因为这是一棵树，如果要找到一条路，必定是每条边都经过两次(因为是一棵树，不存在任何回路，所以回路必须原路返回，即再经过原来的边一次)，那么欧拉回路的权是 。
欧拉回路必然满足欧拉路，接下来怎么从欧拉回路找一条最小权的欧拉路，因为欧拉回路必然是一个环，那么我们只需要在这个环上找到某一段权值和最大，并且每个点只经过一次，使得剩下的路满足欧拉路，那么剩下的路径就是最小权的欧拉路，并且找的一段路径就是树的直径。
树的直径两次BFS即可。
代码：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

const int maxn = 1e6 + 10;
vector<pair<int,int> >G[maxn];
typedef long long int ll;
ll dis[maxn];
void dfs(int u,int fu){
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i].first;
        ll w = G[u][i].second;
        if(v != fu){
            dis[v] = max(dis[u] + w,dis[v]);
            dfs(v,u);
        }
    }
}
void solved(){
    int n;scanf("%d",&n);
    ll ans = 0;
    for(int i = 1; i < n; i++){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        G[u].push_back({v,w});
        G[v].push_back({u,w});
        ans = ans + w * 2;
    }
    dfs(1,0);
    int pos = 1;
    for(int i = 2; i <= n; i++){
        if(dis[i] > dis[pos]) pos = i;
    }
    memset(dis,0,sizeof(dis));
    dfs(pos,0);
    ll res = 0;
    for(int i = 1; i <= n; i++)res = max(res,dis[i]);
    printf("%lld\n",ans - res);
}
int main(){
    solved();
    return 0;
}