light oj 1257 树的直径

以前写过一个证明，直接贴过来吧
主要是利用了反证法：
假设 s-t这条路径为树的直径，或者称为树上的最长路
现有结论，从任意一点u出发搜到的最远的点一定是s、t中的一点，然后在从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜就可以找出树的最长路
证明：
1    设u为s-t路径上的一点，结论显然成立，否则设搜到的最远点为T则
dis(u,T) >dis(u,s)     且 dis(u,T)>dis(u,t)   则最长路不是s-t了，与假设矛盾
2   设u不为s-t路径上的点
    首先明确，假如u走到了s-t路径上的一点，那么接下来的路径肯定都在s-t上了，而且终点为s或t，在1中已经证明过了
    所以现在又有两种情况了：
    1：u走到了s-t路径上的某点，假设为X，最后肯定走到某个端点，假设是t ，则路径总长度为dis(u,X)+dis(X,t)
    2：u走到最远点的路径u-T与s-t无交点，则dis(u-T) >dis(u,X)+dis(X,t);显然，如果这个式子成立，
    则dis(u,T)+dis(s,X)+dis(u,X)>dis(s,X)+dis(X,t)=dis(s,t)最长路不是s-t矛盾
    附上一张第二种情况的图

这道题让你求出距离每个点最远的点之间距离是多少，因为每个点走的最长路的重点肯定是直径上的某个端点，所以，写个bfs不断的搜吧
[cpp]
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 30010;
vector<pair<int,int> > edge[maxn];
int dis1[maxn],dis2[maxn];
int n;
bool vis[maxn];
void bfs(int s,int &t,int dis[]){
    fill(vis,vis+n,false);
    queue<int> Q;
    Q.push(s);vis[s]=true;
    dis[s]=0;
    int Max=0;
    while(!Q.empty()){
        int fr=Q.front();Q.pop();
        int sz=edge[fr].size();
        for(int i=0;i<sz;i++){
            int v=edge[fr][i].first,w=edge[fr][i].second;
            if(vis[v]) continue;
            dis[v]=dis[fr]+w;
            if(dis[v]>Max) t=v,Max=dis[v];
            vis[v]=true;
            Q.push(v);
        }
    }
}
int main()
{
    int t,ca=1,a,b,w;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++) edge[i].clear();
        for(int i=0;i<n-1;i++)
        {
            scanf("%d%d%d",&a,&b,&w);
            edge[a].push_back(make_pair(b,w));
            edge[b].push_back(make_pair(a,w));
        }
        int u,v,x;
        bfs(0,u,dis1);
        bfs(u,v,dis1);
        bfs(v,x,dis2);
        printf("Case %d:\n",ca++);
        for(int i=0;i<n;i++)
        {
            printf("%d\n",max(dis1[i],dis2[i]));
        }
    }
    return 0;
}

作者：haha593572013

补充：软件开发 , C++ ,