题意:求每个点的子树中哪一层节点数最多，如果有节点数最多不唯一，取层数最小的。
题解：dus on tree
基本想法是对每一个节点都构建一个deep数组，然后从底向上更新过来，但是这样空间复杂度和时间复杂度都会是O(n^2)无法承受。
然后向办法共用deep数组和记录其数值的数组，那么这时候对于一个节点来说，如果他每次都要重新遍历他所有的子节点，那么时间复杂度仍是O(n^2)，所以考虑保留他某个儿子的火种，那当然是保留其子树最大的儿子节点了，所以每次先dfs其不是子数最大的儿子的节点，而后遍历子数最大的儿子节点，这个顺序不能反，因为你要对先遍历的清空，这是由于你共用了数组，所以每次访问前都要清空cnt数组，但是最后一个可以不清空，因为他没有别的儿子要访问了。
复杂度分析：由于重链是直接继承（大儿子最后访问不清空）的关系，也就是O(1)就可以了，考虑轻链，对于某个点来说，他一直跑一直跑到根节点，至多经过logn条轻链，因为每条轻链都会导致节点总数目*2,所以是logn条，所以总复杂度就是nlogn了
算法的关键点就是利用了重链轻链的思想，重用了数组，适用于查询所有节点的题目。
https://codeforces.com/blog/entry/44351 //codeforce博客链接
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+;
vector<int>G[N];
int n,sz[N],deep[N],c[N],ans[N];
void getsz(int x,int f,int dt){
sz[x]=;
deep[x]=dt;
for(int i=;i<(int)G[x].size();++i) {
int v=G[x][i];
if(v==f) continue;
getsz(v,x,dt+);
sz[x]+=sz[v];
}
}
int mx,id;
void mdy(int x,int y){
c[x]+=y;
if(c[x]>mx) mx=c[x],id=x;
if(c[x]==mx&&x<id) id=x;
}
void add(int u,int p,int x){
mdy(deep[u],x);
for(int i=;i<(int)G[u].size();++i){
int v=G[u][i];
if(v==p) continue;
add(v,u,x);
}
}
void dfs(int u,int p,bool keep){
int big=-,now=;
for(int i=;i<(int)G[u].size();++i) {
int v=G[u][i];
if(v==p) continue;
if(sz[v]>now) now=sz[v],big=v;
}
for(int i=;i<(int)G[u].size();++i) {
int v=G[u][i];
if(v==big||v==p) continue;
dfs(v,u,);
}
if(~big) dfs(big,u,);
mdy(deep[u],);
for(int i=;i<(int)G[u].size();++i) {
int v=G[u][i];
if(v==big||v==p) continue;
add(v,u,);
}
ans[u]=id;
if(!keep){
mdy(deep[u],-);
for(int i=;i<(int)G[u].size();++i){
int v=G[u][i];
if(v==p) continue;
add(v,u,-);
}
mx=id=;
}
}
int main(){
int x,y;
scanf("%d",&n);
for(int i=;i<n;++i) {
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
getsz(,,);
dfs(,,);
for(int i=;i<=n;++i) printf("%d\n",ans[i]-deep[i]);
}