这是一道来自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
数据范围（听LZ说的）：对于100%的数据，1<=n<=1000 然而我认为的数据范围：应该是 1<=n<=5000000 （强行不和善）
（然而这样排版还是很丑）（逃 来源：oj.jzxx.net（原LZ并没有给哪个题.._ (:з」∠) _ 于是去了那个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.
