**题意：

      给你一棵树，让你改变一条边，改变之后依然是一棵树，然后问你怎样改变才能让树的直径最短。这里的改变一条边指的是指把一条边长度不变，连在别的两个点上。

思路：
**

首先求出树的直径，把直径上的边记录下来，然后在枚举这些边（枚举别的边没意义）每次枚举我的做法是后建造两棵树，我们只要在这两棵树之间连接一条边就行了，但是怎么连接呢？ 我是先没别求两棵树的直径，然后在找到直径上中间点，然后连接这两棵树的中间点，只有这样才能保证最短，每次连接后的直径就是 两棵树的直径，和当前枚举的边长度+两个树被中间点分开的较长的那一个值的和，他们三个中较长的哪一个，就这样在所有中找到一个最小的就是答案。

#include
#include
#include
#include

#define N_node 2500 + 5
#define N_edge 5000 + 5
#define INF 1000000000
using namespace std**;

typedef struct
{
int** to ,next ,cost; }STAR**;

typedef struct
{
int** a ,b ,c; }EDGE;

STAR E[N_edge];
EDGE edge[N_node]; int list[N_node] ,tot; int s_x[N_node] ,mer[N_node];
map >hash**;

void** add(int a ,int b ,int c) {
E[++tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;

E[++tot].to = a;
E[tot].cost = c;
E[tot].next = list[b];
list[b] = tot**;
}

void** Spfa(int s ,int n) { for(int i = 0 ;i <= n ;i ++)
s_x[i] = INF ,mer[i] = i; int mark[N_node] = {0};
s_x[s] = 0 ,mark[s] = 1;
queueq;
q.push(s); while(!q.empty()) { int xin ,tou;
tou = q.front();
q.pop();
mark[tou] = 0; for(int k = list[tou] ;k ;k = E[k].next) {
xin = E[k].to; if(s_x[xin] > s_x[tou] + E[k].cost) {
s_x[xin] = s_x[tou] + E[k].cost;
mer[xin] = tou; if(!mark[xin]) {
mark[xin] = 1;
q.push(xin**);
}
}
}
}
return ;
}

int** abss(int x) { return x > 0 ? x : -x**;
}

int** maxx(int x ,int y) { return x > y ? x : y**;
}

int main ()
{
int** t ,n ,a ,b ,c ,i ,j; int cas = 1;
scanf("%d" ,&t); while(t--) {
scanf("%d" ,&n);
memset(list ,0 ,sizeof(list));
tot = 1; for(i = 1 ;i < n ;i ++) {
scanf("%d %d %d" ,&edge[i].a ,&edge[i].b ,&edge[i].c);
edge[i].a ++ ,edge[i].b ++;
add(edge[i].a ,edge[i].b ,edge[i].c**);
}

  int** p01 **,**p02**;**  
  Spfa**(**1 **,**n**);  
  int** maxxx **= -**1**;  
  for(**j **=** 1 **;**j **<=** n **;**j **++)  
  if(**maxxx **<** s\_x**\[**j**\] &&** s\_x**\[**j**\] !=** INF**)  
  {**  
     maxxx **=** s\_x**\[**j**\];**  
     p01 **=** j**;  
  }**  
  Spfa**(**p01 **,**n**);**  
  maxxx **= -**1**;  
  for(**j **=** 1 **;**j **<=** n **;**j **++)  
  if(**maxxx **<** s\_x**\[**j**\] &&** s\_x**\[**j**\] !=** INF**)  
  {**  
     maxxx **=** s\_x**\[**j**\];**  
     p02 **=** j**;  
  }  
  int** x **=** p02**;**  
  hash**.**clear**();  
  while(**x **!=** mer**\[**x**\])  
  {**  
     hash**\[**x**\]\[**mer**\[**x**\]\] =** hash**\[**mer**\[**x**\]\]\[**x**\] =** 1**;**  
     x **=** mer**\[**x**\];  
  }

  int** ans **=** INF**;  
  for(**i **=** 1 **;**i **<** n **;**i **++)  
  {  
     if(!**hash**\[**edge**\[**i**\].**a**\]\[**edge**\[**i**\].**b**\]) continue;**  
     memset**(**list **,**0 **,sizeof(**list**)) ,**tot **=** 1**;  
     for(**j **=** 1 **;**j **<** n **;**j **++)  
     if(**j **==** i**) continue;  
     else** add**(**edge**\[**j**\].**a **,**edge**\[**j**\].**b **,**edge**\[**j**\].**c**);

     int** p11 **,**p12 **,**mid1 **,**l1 **,**mid1l**;**  
     Spfa**(**edge**\[**i**\].**a **,**n**);  
     int** max **= -**1**;  
     for(**j **=** 1 **;**j **<=** n **;**j **++)  
     if(**max **<** s\_x**\[**j**\] &&** s\_x**\[**j**\] !=** INF**)  
     {**  
        max **=** s\_x**\[**j**\];**  
        p11 **=** j**;  
     }**  
     Spfa**(**p11 **,**n**);**  
     max **= -**1**;  
     for(**j **=** 1 **;**j **<=** n **;**j **++)  
     if(**max **<** s\_x**\[**j**\] &&** s\_x**\[**j**\] !=** INF**)  
     {**  
        max **=** s\_x**\[**j**\];**  
        p12 **=** j**;  
     }**  
     l1 **=** max**;  
     int** x **=** p12**;  
     int** min **=** INF**;  
     while(**x **!=** mer**\[**x**\])  
     {  
        if(**min **>** abss**(**s\_x**\[**x**\] - (**l1 **-** s\_x**\[**x**\])))  
        {**  
           min **=** abss**(**s\_x**\[**x**\] - (**l1 **-** s\_x**\[**x**\]));**  
           mid1 **=** x**;**  
           mid1l **=** maxx**(**s\_x**\[**x**\] ,**l1 **-** s\_x**\[**x**\]);  
        }**  
        x **=** mer**\[**x**\];  
     }  
     if(**min **>** abss**(**s\_x**\[**x**\] - (**l1 **-** s\_x**\[**x**\])))  
     {**  
        min **=** abss**(**s\_x**\[**x**\] - (**l1 **-** s\_x**\[**x**\]));**  
        mid1 **=** x**;**  
        mid1l **=** maxx**(**s\_x**\[**x**\] ,**l1 **-** s\_x**\[**x**\]);  
     }

     int** p21 **,**p22 **,**mid2 **,**l2 **,**mid2l**;**  
     Spfa**(**edge**\[**i**\].**b **,**n**);**  
     max **= -**1**;  
     for(**j **=** 1 **;**j **<=** n **;**j **++)  
     if(**max **<** s\_x**\[**j**\] &&** s\_x**\[**j**\] !=** INF**)  
     {**  
        max **=** s\_x**\[**j**\];**  
        p21 **=** j**;  
     }**  
     Spfa**(**p21 **,**n**);**  
     max **= -**1**;  
     for(**j **=** 1 **;**j **<=** n **;**j **++)  
     if(**max **<** s\_x**\[**j**\] &&** s\_x**\[**j**\] !=** INF**)  
     {**  
        max **=** s\_x**\[**j**\];**  
        p22 **=** j**;  
     }**  
     l2 **=** max**;**  
     x **=** p22**;**  
     min **=** INF**;  
     while(**x **!=** mer**\[**x**\])  
     {  
        if(**min **>** abss**(**s\_x**\[**x**\] - (**l2 **-** s\_x**\[**x**\])))  
        {**  
           min **=** abss**(**s\_x**\[**x**\] - (**l2 **-** s\_x**\[**x**\]));**  
           mid2 **=** x**;**  
           mid2l **=** maxx**(**s\_x**\[**x**\] ,**l2 **-** s\_x**\[**x**\]);  
        }**  
        x **=** mer**\[**x**\];  
     }  
     if(**min **>** abss**(**s\_x**\[**x**\] - (**l2 **-** s\_x**\[**x**\])))  
     {**  
        min **=** abss**(**s\_x**\[**x**\] - (**l2 **-** s\_x**\[**x**\]));**  
        mid2 **=** x**;**  
        mid2l **=** maxx**(**s\_x**\[**x**\] ,**l2 **-** s\_x**\[**x**\]);  
     }

     int** now **=** maxx**(**maxx**(**l1 **,**l2**) ,**edge**\[**i**\].**c **+** mid1l **+** mid2l**);  
     if(**ans **>** now**)** ans **=** now**;  
  }**  
  printf**(**"Case %d: %d\\n" **,**cas **++ ,**ans**);  

}
return** 0; }