链接：https://ac.nowcoder.com/acm/contest/369/C
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

小A给你了一棵树，对于这棵树上的每一条边，你都可以将它复制任意（可以为0）次（即在这条边连接的两个点之间再加一条边权相同的边），求所有可能新形成的图中欧拉路的最短长度

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

输入描述:

第一行一个数 n ，表示节点个数

接下来 n-1 行，每行三个整数 u,v,w，表示有一条 u 到 v 边权为 w 的无向边

保证数据是一棵树

输出描述:

一行一个整数，表示答案

示例1

输入

复制

4
1 2 1
1 3 1
1 4 2

输出

复制

5

说明

一种可能的方案为复制 <1,2,1> 这条边一次，欧拉路为4->1->2->1->3

备注:

1≤n≤2×10^5
1≤ui,vi≤n
1≤wi≤10^4

题意：树加边求最小权值的欧拉路

题解：树加边求最小权值的欧拉路=树的权值*2-树的直径（当时没想到直径问题，醉了~~）教训：做题要多画图啊，别凭空想象

知道是求直径问题就是水题了~~~上代码：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int MAX = 1e6+100;
struct hh{
    int u,v,w;
    int nt;
}a[MAX];
int dis[MAX],head[MAX];
bool vis[MAX];
int n,tot,point,len;
ll ans;//注意要用long long
void add(int u,int v,int w){
    a[tot].v=v;
    a[tot].u=u;
    a[tot].w=w;
    a[tot].nt=head[u];
    head[u]=tot++;
}
void bfs(int s){//找树的直径模板
    memset(vis,false,sizeof(vis));//第二次要初始化，第一次一块带上了，嘻嘻~~不超时
    memset(dis,0,sizeof(dis));//第二次要初始化，第一次一块带上了，嘻嘻~~不超时
    queue<int> q;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for (int i = head[x]; ~i; i = a[i].nt){
            int y=a[i].v;
            if(!vis[y]){
                dis[y]=dis[x]+a[i].w;
                if(len<dis[y]){
                    len=dis[y];
                    point=y;
                }
                vis[y]=true;
                q.push(y);
            }
        }
    }
}
int main(){
    cin >> n;
    memset(head,-1,sizeof(head));
    for (int i = 0; i < n-1;i++){
        int u,v,w;
        cin >> u >> v >> w;
        add(u,v,w);//无向边，为双向的
        add(v,u,w);
        ans+=w<<1;//树的权值*2
    }
    len=0;
    bfs(1);//找到最远点
    len=0;//len为树的直径~~，记住要初始化！
    bfs(point);//找直径，必须跑两边，记住！！！
    cout << ans-len << endl;
    return 0;
}