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;
}