题意：给定一棵以 \(1\) 为根，\(n\) 个节点的树。设 \(d(u,x)\) 为 \(u\) 子树中到 \(u\) 距离为 \(x\) 的节点数。 对于每个点，求一个最小的 \(k\)，使得 \(d(u,k)\) 最大。 ( $ 1 \le n \le 10^6 $ )
分析：第一次dfs预处理进行长链剖分求出重儿子\(son[u]\)以及\(len[u]\)表示以u为根的子树中最大深度。然后第二次dfs进行树上启发式合并，先处理重儿子并记录到数组中，再把轻儿子产生的贡献累加到数组中。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=1e6+5;
const int M=2e6+5;
const int mod=998244353;
int tot,nxt[M],head[N],to[M];
int dfn,len[N],son[N],l[N],r[N],sum[N],ans[N];
inline void add(int a,int b){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void dfs1(int u,int fa){
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==fa)continue;
dfs1(v,u);
if(len[v]>len[son[u]])son[u]=v;
}
len[u]=len[son[u]]+1;
}
inline void dfs(int u,int fa){
l[u]=++dfn;//因为每次优先处理重儿子
r[u]=l[u]+len[u]-1;//所以重儿子是一段连续的
if(son[u]){//优先处理重儿子
dfs(son[u],u);
ans[u]=ans[son[u]]+1;//答案继承
}
for(int i=head[u];i;i=nxt[i]){
int v=to[i];//处理轻儿子
if(v==son[u]||v==fa)continue;
dfs(v,u);
int k=0;//记录深度
for(int j=l[v];j<=r[v];++j){
++k;//从1开始，也就是从u的直接子节点开始
sum[l[u]+k]+=sum[j];//累加当前深度下轻儿子的贡献
if(sum[l[u]+k]>sum[l[u]+ans[u]])ans[u]=k;//更新答案
else if(sum[l[u]+k]==sum[l[u]+ans[u]]&&k<ans[u])ans[u]=k;//保证深度最小
}
}
++sum[l[u]];//u节点自己对自己产生贡献1
if(sum[l[u]+ans[u]]<=sum[l[u]])ans[u]=0;//k=0
}
int main(){
int n=read();
for(int i=1;i<n;++i){
int x=read(),y=read();
add(x,y);add(y,x);
}
dfs1(1,0);dfs(1,0);
for(int i=1;i<=n;++i)cout<<ans[i]<<endl;
return 0;
}