一种神奇套路：对答案根分，根分的依据是链的长度和答案大致是一个成反比的关系。
考虑确定了 $k$ 怎么做。因为一个点只能在一条链里，所以 dfs 的时候如果能拼成一条链就一定会拼成一条链，不然就把贡献传给父亲继续尝试。
对于 $k$ 比较小的时候可以暴力计算。对于 $k$ 较大的情况，发现答案一定非严格单减，并且递减的幅度越来越小。所以对于 $k$ 比较大的情况，可以通过枚举答案，二分找出答案对应的区间。
设块长为 $B$，对于 $k\leq B$ 暴力计算，$k>B$ 枚举答案不会超过 $\dfrac{n}{B}$，复杂度 $\mathcal O(Bn+\dfrac{n^2}{B}\log n)$，块长取 $1000$ 可以通过此题。
一点卡常技巧：dfs 的次数非常多，所以可以先 dfs 一遍，之后按照 dfn 序扫一遍即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int n,cnt,ans,bl,len,tot,maxn[100010],maxm[100010],up[100010],a[100010],fin[100010],head[100010],to[200010],nex[200010];
inline void add(int x,int y){to[++cnt]=y,nex[cnt]=head[x],head[x]=cnt;}
void dfs0(int k,int fa)
{
a[++tot]=k,up[k]=fa;
for(int i=head[k];i;i=nex[i])if(to[i]!=fa)dfs0(to[i],k);
}
void dfs()
{
for(int i=n;i>=1;--i)
{
int now=a[i];maxn[now]=maxm[now]=0;
for(int j=head[now];j;j=nex[j])
{
if(to[j]==up[now])continue;
int t=maxn[to[j]];
if(t>=maxn[now])maxm[now]=maxn[now],maxn[now]=t;
else Mmax(maxm[now],t);
}
if(maxn[now]+maxm[now]+1>=len)++ans,maxn[now]=0;
else ++maxn[now];
}
}
inline void mian()
{
read(n),bl=1000;int x,y;
for(int i=1;i<n;++i)read(x,y),add(x,y),add(y,x);
dfs0(1,0);
for(int i=1;i<=bl;++i)len=i,ans=0,dfs(),fin[i]=ans;
int tt=ans;
for(int i=0,last=n+1;i<=tt;++i)
{
int l=bl+1,r=last,mid;
while(l<r)
{
len=mid=l+((r-l)>>1),ans=0,dfs();
if(ans>i)l=mid+1;
else r=mid;
}
for(int j=l;j<last;++j)fin[j]=i;
last=l;
}
for(int i=1;i<=n;++i)write(fin[i],'\n');
}