题意： 已知一个树形的地图，要在其间建设一条公路，每个公路上的点只经过一次，问如何建工路使得所有点到公路的最长距离最短。

分析： 看成是找树上所有点中距离最远的路径，主要是两次广搜，第一次找到一个端点，第二次找到另一个，第二次找的过程中记录路径，

         便于最后一次遍历全图找到答案。

#include 
     
      #include 
      
       #define maxn 100005#define clr(x)memset(x,0,sizeof(x))struct node{    int to, next, w;}q[1000000];int tot;int head[maxn];void add(int s, int u, int wi){    q[tot].to = u;    q[tot].next = head[s];    q[tot].w = wi;    head[s] = tot++;}struct P{    int xu, di;}que[maxn],xx,tt;bool v[maxn];int pre[maxn];int main(){    int n, i, e, st;    int front, rear, son;    int a, b, wi;    int tmp, res;    while (scanf("%d",&n),n)    {        tot = 1;        clr(head);        for (i=0; i
       
         tmp)                    {                        tmp = tt.di;                        st = tt.xu;                    }                }            }        }        front = rear = 0;        tt.xu = st;        tt.di = 0;        que[rear++] = tt;        clr(pre);        pre[tt.xu] = -1;        tmp = 0;        while (front < rear)        {            xx = que[front++];            for (i=head[xx.xu]; i; i=q[i].next)            {                tt.xu = q[i].to;                if (!pre[tt.xu])                {                    tt.di = xx.di+q[i].w;                    pre[tt.xu] = xx.xu;                    que[rear++] = tt;                    if (tt.di > tmp)                    {                        tmp = tt.di;                        st = tt.xu;                    }                }            }        }        clr(v);        e = st;        v[st] = true;        while (pre[st] != -1)        {            v[pre[st]] = true;            st = pre[st];        }        res = 0;        front = rear = 0;        while (pre[e] != -1)        {            e = pre[e];            tt.xu = e;            tt.di = 0;            front = rear = 0;            que[rear++] = tt;            while (front < rear)            {                xx = que[front++];                for (i=head[xx.xu]; i; i=q[i].next)                {                    tt.xu = q[i].to;                    if (!v[tt.xu])                    {                        tt.di = q[i].w+xx.di;                        v[tt.xu] = true;                        que[rear++] = tt;                        if (tt.di > res)                            res = tt.di;                    }                }            }        }        printf("%d\n",res);    }    return 0;}