本文共 1634 字，大约阅读时间需要 5 分钟。

链接：

时间限制：C/C++ 1秒，其他语言2秒

题目描述

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

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

输入描述:

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

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

保证数据是一棵树

输出描述:

一行一个整数，表示答案

示例1

输入

复制

41 2 11 3 11 4 2

输出

复制

5

说明

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

备注:

1≤n≤2×10^5

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

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

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

#include 
   
    #include 
    
     #include 
     
      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 longvoid 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
      
        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
       
        > 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;}