这是一道来自OIerBBS的题目..
原帖地址：http://www.oierbbs.com/forum.php?mod=viewthread&tid=512?fromuid=71
（似乎是个很小众的BBS..不从洛谷空降根本到不了..）

（原帖的排版我忍不了。。 把题目的样式重新处理了一遍。。）

题目描述

味味最近对树很感兴趣，什么是树呢？树就是有n个节点和n-1条边形成的无环连通无向图。
味味在研究过程中想知道，对于一个无根树，当节点i作为根的时候树的高是多少。所谓树高指的是从根节点出发，到离根节点最远叶子节点所经过的节点的总数,详见输入输出样例1。味味现在遇到了一些烦心的事情，不想再继续思考了，请你帮助她解决这个问题。

输入格式

输入共N行。
第1行为一个正整数N，表示树的节点个数。
第2行到第N行里，每行两个用空格隔开的正整数a和b，表示a与b有连边。

输出格式

输出共N行，第i行表示以节点i为根时的树高。

样例输入

样例1：
3
1 2
2 3
样例2：
4
1 4
2 4
3 4
样例输出
样例1：
3
2
3
样例2：
3
3
3
2

数据范围（听粗心的菠萝说的）：对于100%的数据，1<=n<=1000
然而我认为的数据范围：应该是 1<=n<=5000000 （强行不和善）

（然而这样排版还是很丑）（逃
来源：oj.jzxx.net（原粗心的菠萝并没有给哪个题.._ (:з」∠) _ 于是去了那个OJ.. 应该是2701..）
题目の传送门：http://oj.jzxx.net/problem.php?id=2701
（这个OJ我都不会用。。。。。。我真傻，真的）

讨论区中的做法：
法1. 暴力枚举每个点为根，搜索树的最大深度 （复杂度：O（n^2））
法2. 平衡树？（其实不知道能不能，其实我没看懂，但应该可以） （复杂度:均摊O（nlogn））
法3. 分块（这个看上去挺靠谱的？编程复杂度低于上面） （复杂度：O（n^1.5））

==========================我是学术的分割线==========================

题目大意

给定一棵无根树，求以每个点为根形成的树的树高。。

题目分析

哦？这不是等价于求树上每个点到树上其他点距离的最大值嘛。。
这就用到了一个知识点：树上任一点到树直径(*)的其中一个端点的距离最远~~
*：直径：树的直径是指树的最长简单路。

所以……这题做完了。（逃

先求直径，然后分别从直径的两端点bfs，对于求得的两个距离取最大值即可。。

直径怎么求？

两遍bfs。先随便选一个点做起点bfs找到距它距离最大的点，再从那个点进行bfs，则这次bfs找到的最长路即为树的直径（即这次找到的距它距离最大的点就是直径的另一个端点）

原理: 设起点为u，第一次bfs找到的终点v一定是树的直径的一个端点（根据某知识点），然后再bfs找到的显然是另一个端点。。

然后分别以直径的两个端点为起点进行bfs遍历树，更新每个节点的距离，然后从两距离中取最大值即可。

细心的你一定发现了，求直径时的第二遍bfs已经是从直径的一个端点出发了，我们完全可以顺带着更新路上的值了，这样我们又少了一遍bfs，这真令人高兴O(∩_∩)O

So，Obviously，经过以上步骤，我们便得到了解答。
复杂度？3遍bfs，均为O（m），因为是树，且边无向，m=（n-1）* 2，所以也就6 *（n-1）吧
总复杂度：O（n）级别（线性）

完美~~

代码实现

STL重度依赖症的代码..（不要问我为什么这三个bfs长得辣么像）

#include <queue>#include <cstdio>#include <cstring>using std::vector;using std::queue;#define gc getchar()#define cl(a,b) memset(a,b,sizeof(a)) const int N=1008;vector<int> e[N];queue<int> q;int d[N],_d[N];inline int gnum(){ int a=0;char c=gc;bool f=0; for(;(c<‘0’||c>’9′)&&c!=’-‘;c=gc); if(c==’-‘) f=1,c=gc; for(;c>=’0’&&c<=’9’;c=gc) a=(a<<1)+(a<<3)+c-‘0’; if(f) return ~a+1; return a;}int bfs1(){ //找一个端点 cl(d,-1); d[1]=0; int mi=1; q.push(1); while(!q.empty()){ int x=q.front(); q.pop(); for(int i=0;i<e[x].size();i++){ int y=e[x][i]; if(d[y]<0){ d[y]=d[x]+1; mi=y; q.push(y); //因为是树形结构，所以不需要像真的最短路一样加判断，一旦搜到一定是最远的（之一） } } } return mi;}int bfs2(int s){ //找另一个端点，更新距这个端点的距离 cl(d,-1); d[s]=1; int mi=s; q.push(s); while(!q.empty()){ int x=q.front(); q.pop(); for(int i=0;i<e[x].size();i++){ int y=e[x][i]; if(d[y]<0){ d[y]=d[x]+1; mi=y; q.push(y); } } } return mi;}void bfs3(int s){ //更新距另一个端点的距离 cl(_d,-1); _d[s]=1; q.push(s); while(!q.empty()){ int x=q.front(); q.pop(); for(int i=0;i<e[x].size();i++){ int y=e[x][i]; if(_d[y]<0){ _d[y]=_d[x]+1; q.push(y); if(_d[y]>d[y]) d[y]=_d[y]; //偷懒ing..要是这个距离大于从另一端的距离就直接覆盖掉.. //反正树形结构一个点只会跑一次.. } } }}int main(){ int n=gnum(); for(int i=1;i<n;i++){ int u=gnum(),v=gnum(); e[u].push_back(v); e[v].push_back(u); } int x=bfs1();int y=bfs2(x);bfs3(y); for(int i=1;i<=n;i++) printf(“%d\n”,d[i]);}//这题真的好简单呢.. 写在后面

基本就是这样了，下面为好学的你们附上关于某求直径方式正确性的证明：
证明: 1) 如果u是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾)
2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了
所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度

其实最重要的是理解某奇妙的知识点

The End.