Highway Construction

Description

 As head of the Accessible Commuting Movement (ACM), you've been lobbying the mayor to build a new highway in your city. Today is your lucky day, because your request was approved. There is one condition though: You must provide the plan for the best highway artery to construct, or else it's not going to happen! You have a map that shows all communities in your city, each with a unique number, where you may place highway on-ramps. On the map are a set of roadways between pairs of communities, labelled with driving distances, which you may choose to replace with your highway line. Using this network of roadways, there is exactly one route from any one community to another. In other words, there are no two di erent sets of roadways that would lead you from community A to community B.

You can build a single highway that runs back and forth between any two communities of your choosing.  
It will replace the unique set of roadways between those two communities, and an on-ramp will be built at every community along the way. Of course, residents of communities that will not have an on-ramp will have to drive to the nearest one that does in order to access your new highway. 
You know that long commutes are very undesirable, so you are going to build the highway so that longest drive from any community to the nearest on-ramp is minimized. Given a map of your city with the roadways and driving distances, what is the farthest distance from any community that someone would have to drive to get to the nearest on-ramp once your new highway is complete?

Input

 The input consists of multiple test cases. Each test case is a description of a city map, and begins with a single line containing an integer N (2  ≤ N ≤ 100,000), the number of communities in the city. Then N -1 lines follow, each containing three integers, i, j (1 ≤  i, j ≤ N ), and d (1 ≤ d ≤ 10,000).

Each line indicates that communities i and j are connected by a roadway with driving distance d. Input is followed by a single line with N = 0, which should not be processed.

Output

 For each city map, output on a single line the farthest distance from any community to the nearest on-ramp of the new highway.

Sample Input

6
2 1 10
3 1 15
1 4 5
4 5 12
4 6 8
0

Sample Output

10
题意:给出一棵树，每个树边有权值。求一条树干，使得所有叶子节点到这个树干的距离最小。（树干是连个叶子节点之间的一条线）；
分析：假设树的直径L是这条树干S。
证明：反证L不是这个S
那分为两种情况：
1.这个L跟S有交集。交集的两个端点分别为A，B。将AB切断，设L的端点跟A同一侧的为la，S的端点跟A同一侧为sa，则la到A的距离比sa到A的距离更小。因为L中la到A的这段可以被sa到A的这段取代。
这与L是直径构成矛盾。
2.L跟S没交集。设p为L中的一个点，q为S中的一个点。由于是一棵树，我们一定可以找某个p到某个s的一条路径使得L跟S被连通，而且这个路径只有一条。则存在S的一个端点sa到q的距离比L的一个端点la到q的距离（即la到p的路径长度+p到q的路径长度）更长。这与L是直径矛盾，因为L中从p到la那一段可以被p到q再到sa的那一段取代。
反证不成立，假设勉强YY成立。
下面是代码，比较丑陋。因为敲时没能百分百确定能以上结论成立。所以是写的时候比较随意。都是AC了才敢妄下这种YY的证明。
接下来是树的直径求法证明，网上贴的。

树的直径(Diameter)是指树上的最长简单路。
直径的求法：两遍BFS (or DFS)
任选一点u为起点，对树进行BFS遍历，找出离u最远的点v
以v为起点，再进行BFS遍历，找出离v最远的点w。则v到w的路径长度即为树的直径
*简单证明
于是原问题可以在O(E)时间内求出
关键在于证明第一次遍历的正确性，也就是对于任意点u，距离它最远的点v一定是最长路的一端。
如果u在最长路上，那么v一定是最长路的一端。可以用反证法：假设v不是最长路的一端，则存在另一点v’使得(u→v’)是最长路的一部分，于是len(u→v’) > len(u→v)。但这与条件“v是距u最远的点”矛盾。
如果u不在最长路上，则u到其距最远点v的路与最长路一定有一交点c，且(c→v)与最长路的后半段重合，即v一定是最长路的一端
这里自己补充下：设树直径的一点c最先被搜到，设以C为根的子树为Tc则C到树直径的两个端点的距离的最长者X都长于C到任意其他点的距离。包括u到C之间的所有子树（T-tc）的所有点到C的距离y也比X小。所以u为0距离开始搜索后点v跟u最远的肯定是树的一个端点。也是比较yy。
#include <stdio.h>
#include <stdlib.h>
#define Max(a, b) a > b ? a : b
#define Min(a, b) a < b ? a : b
#define maxn 110000
struct T
{
    int v, w, next;
}fn[maxn * 2];
int n, th;
int dis[maxn], g[maxn], visit[maxn], path[maxn];
void setGraph()
{
    th = 0;
    for (int i = 0; i <= 2 * n; i++)
    {
        g[i] = -1;
    }
}
void add(int u, int v, int w)
{
    fn[th].v = v, fn[th].w = w, fn[th].next = g[u], g[u] = th++;
    fn[th].v = u, fn[th].w = w, fn[th].next = g[v], g[v] = th++; 
}
void dfs(int u)
{
    visit[u] = 1;
    int i;
    for (i = g[u]; i != -1; i = fn[i].next)
    {
        if (!visit[fn[i].v])
        {
            path[fn[i].v] = u;
            dis[fn[i].v] = dis[u] + fn[i].w;
            dfs(fn[i].v); 
        }
    }
}
void find(int u, int f)
{
    visit[u] = 1;
    int i, v;
    for (i = g[u]; i != -1; i = fn[i].next)
    {
        v = fn[i].v;
        if (v != f && visit[v] == 0)
        {
            dis[v] = dis[u] + fn[i].w;
            dfs(v);
        }
    }
}
int main()
{
    int i, u, v, w, min, j;
    while (scanf("%d", &n) , n)
    {
        setGraph();
        for (i = 1; i < n; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, w);
        }
        for (i = 1; i <= n; i++)
        {
            visit[i] = 0;
        }
        dis[1] = 0;
        dfs(1);//第一次dfs找树直径的一个端点，这个的path没用的。 
        for (i = 1, min = -1; i <= n; i++)
        {
            if (min < dis[i])
            {
                min = dis[i];
                j = i;
            }
        }
        for (i = 1; i <= n; i++)
        {
            visit[i] = 0;
        }
        dis[j] = 0;
        path[j] = -1;
        dfs(j);//通过端点找另一个端点，并保存路径。 
        for (i = 1, min = -1; i <= n; i++)
        {
            if (min < dis[i])
            {
                min = dis[i];
                j = i;
            }
        }
        for (i = 1; i <= n; i++) visit[i] = 0;
        for (i = j; i != -1; i = path[i])//从直径上搜索计算每个叶子到直径的距离 
        {
            dis[i] = 0;
            find(i, path[i]);
        }
        for (i = 1, min = -1; i <= n; i++)
        {
            if (min < dis[i])
            {
                min = dis[i];
            }
        }
        printf("%d\n", min);    
    }
    return 0;
}