---

hdu3721: Building Roads

　　Time Limit: 10 Sec

　　Memory Limit: 128 MB

Description

　　 There is a magic planet in the space. There is a magical country on the planet. There are N cities in the country. The country is magical because there are exactly N-1 magic roads between the N cities, and from each city, it is possible to visit any other city. But after the huge expansion of the country, the road system seems to be messy. The moderator decided to rebuild the road system.

　　 As a worker, I cannot do too much things. I could just move one road to another position connecting arbitrary 2 cities using my magic, keeping its length unchanged. Of course, afterwards all the N cities have to be still connected. I wonder how to move in order to make the farthest distance between any two cities minimum. Could you solve it for me?

　

Input

　　 The first line of the input is one integer T (T ≤ 10), and then T test cases follow.

Each test case begins with a line contains only one integer N (N ≤ 2500), means there are N magic cities. The cities are numbered from 0 to N-1.

Following N-1 lines, each line has 3 integers a, b and c, means there is a magic road between a and b with distance c. (0 <= a, b < N, 0 < c <= 1000)

　

Output

　　 For each test case, output the case number and the corresponding minimum farthest distance. See sample for detailed format.

　

Sample Input

　　 2

　　 4

　　 0 1 2

　　 1 2 2

　　 2 3 2

　　 5

　　 0 1 1

　　 1 2 2

　　 2 3 3

　　 3 4 4

　

Sample Output

　　Case 1: 4

　　Case 2: 7

　　

HINT

题目地址：

题目大意： 题目很简洁了：）

题解：

　　做法：

　　枚举删哪一条边

　　分成了两颗树

　　求两颗树的中心连起来

　　构成的树符合题目要求

　　如何求树的中心

　　1.从 i 出发向上，即终点不在以 i 为根的子树内的最长路径 up[i]

　　2.从 i 出发向下，即终点在以 i 为根的子树内的最长路径 d1[i] 和次长路径 d2[i]（c1[i],c2[i]记录从哪转移过来）

　　首先，一便树形 dp 算出 d1,d2,c1,c2

　　　　　若d1[u]<d1[v]+e[i].val ——> d2[u]=d1[u],c2[u]=c1[u],

　　　　　　　　　　　　　　　　　 　d1[u]=d1[v]+dis[u][v],c1[u]=v

　　否则，若d2[u]<d1[v]+e[i].val ——> d2[u]=d1[v]+dis[u][v],c2[u]=v;

　　d1,d2,c1,c2相对好求，如何求 up

　　如果 fa[u] 的向下最长链不是从 v 过来的 ——> up[u]=max(d1[fa[u]],up[fa[u]])+dis[fa[u]][u]

　　如果 fa[u] 的向下最长链是从 v 过来的 　——> up[u]=max(d2[fa[u]],up[fa[u]])+dis[fa[u]][u]

　　画图看看

　　

　　如何在此基础上求树的直径

　　我们只要遍历树上每一个点，直径是 \(mx=max\) { \(d1[u]+d2[u]\) } \(（u \in V）\)

---

AC代码

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N=2505,inf=25e5+5;int Q,n;int U[N],V[N],W[N];bool vis[N];inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}struct edge{    int to,val,next;}e[N+N];int cnt_edge,last[N];bool flag[N+N];inline void add_edge(int u,int v,int w){    e[++cnt_edge]=(edge){v,w,last[u]};last[u]=cnt_edge;flag[cnt_edge]=1;    e[++cnt_edge]=(edge){u,w,last[v]};last[v]=cnt_edge;flag[cnt_edge]=1;}int d1[N],d2[N],c1[N];void dfs(int u,int fa){    d1[u]=d2[u]=0;                                  //赋值前清0    for(int i=last[u];i;i=e[i].next)        if(flag[i]){            int v=e[i].to;            if(v==fa)continue;            dfs(v,u);                               //因为是从儿子更新自己先做儿子            if(d1[u]
      
     
    

　　作者：

　　出处：

　　本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。