题目描述 味味最近对树很感兴趣，什么是树呢？树就是有n个节点和n-1条边形成的无环连通无向图。
味味在研究过程中想知道，对于一个无根树，当节点i作为根的时候树的高是多少。所谓树高指的是从根节点出发，到离根节点最远叶子节点所经过的节点的总数,详见输入输出样例1。味味现在遇到了一些烦心的事情，不想再继续思考了，请你帮助她解决这个问题。
输入 共N行。 第1行为一个正整数N，表示树的节点个数。 第2行到第N行里，每行两个用空格隔开的正整数a和b，表示a与b有连边。
输出 共N行，第i行表示以节点i为根时的树高。
样例输入 4 1 4 2 4 3 4 样例输出 3 3 3 2 提示 对于 100%的数据有 1≤N≤500000，1≤a，b≤N。
久违的感觉。。。 先一遍预处理出以1为根的固定的一棵树，每个点f1[i]表示此时往下的深度 然后对于每个点，它还可以从父亲-爷爷那条线过来，也可以从自己的兄弟处过来，这些用f2表示 很难说清楚，可以自己画图思考一下，思考清楚的话处理的方式也就明白了。
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; int n,x,y,tot; int head[500005],Next[1000005],to[1000005]; int f1[500005],f2[500005]; void add(int x,int y) { tot++; Next[tot]=head[x]; to[tot]=y; head[x]=tot; } void visit(int x,int pre) { f1[x]=1; for(int i=head[x];i!=-1;i=Next[i]) if(to[i]!=pre) { visit(to[i],x); f1[x]=max(f1[x],f1[to[i]]+1); } } void dp(int k,int pre) { if(k!=1) f2[k]=max(f2[k],f2[pre]+1); int s1=0,x1=0,s2=0,x2=0; for(int i=head[k];i!=-1;i=Next[i]) if(to[i]!=pre) { if(f1[to[i]]>s1) { s2=s1; x2=x1; s1=f1[to[i]]; x1=to[i]; } else if(f1[to[i]]>s2) { s2=f1[to[i]]; x2=to[i]; } } for(int i=head[k];i!=-1;i=Next[i]) if(to[i]!=pre) { if(to[i]!=x1) f2[to[i]]=max(f2[to[i]],s1+2); else f2[to[i]]=max(f2[to[i]],s2+2); } for(int i=head[k];i!=-1;i=Next[i]) if(to[i]!=pre) dp(to[i],k); } int main() { cin>>n; for(int i=1;i<=n;i++) head[i]=-1; for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } visit(1,0); f2[1]=1; dp(1,0); for(int i=1;i<=n;i++) printf("%d\n",max(f1[i],f2[i])); return 0; }