题目描述 味味最近对树很感兴趣，什么是树呢？树就是有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。
题解 树上dp，转移根，记录往上走的最大深度。
代码
#include<bits/stdc++.h> #define N 500005 using namespace std; inline int read() { int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } int tot,n,ans[N],ret[N*2],Next[N*2],Head[N]; int dep[N],fa[N]; int ins(int u,int v) { tot++;ret[tot]=v;Next[tot]=Head[u];Head[u]=tot; } void dfs1(int u) { dep[u]=1; for (int i=Head[u];i;i=Next[i]) { int v=ret[i]; if (fa[u]!=v) { fa[v]=u; dfs1(v); dep[u]=max(dep[v]+1,dep[u]); } } } void dfs2(int u,int d) { ans[u]=d+1;int max1=0,max2=0,to1=0,to2=0; for (int i=Head[u];i;i=Next[i]) { int v=ret[i]; if (fa[u]!=v) { ans[u]=max(ans[u],dep[v]+1); if (dep[v]>max1) { max2=max1;to2=to1; max1=dep[v];to1=v; } else if (dep[v]>max2) max2=dep[v],to2=v; } } for (int i=Head[u];i;i=Next[i]) { int v=ret[i]; if (fa[u]!=v) { if (to1!=v) dfs2(v,max(d+1,max1+1)); else dfs2(v,max(d+1,max2+1)); } } } int main() { n=read(); for (int i=1;i<n;i++) { int u=read(),v=read(); ins(u,v);ins(v,u); } dfs1(1); dfs2(1,0); for (int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; }