rt，只是根号分治而已，不是很难的拉，帮人家看看吧，样例二过不了，dfs用的是贪心，从叶子节点往上贪心找链

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,len,book[N],ans[N],las,siz[N];
vector<int>a[N];
int f[N];
void pre(int u,int fa)
{
	siz[u]=1;
	for(auto v:a[u])
	{
		if(v==fa)
			continue;
		f[v]=u;
		pre(v,u);
		siz[u]+=siz[v];
	}
}
int solve(int k)
{
	memset(book,0,sizeof book);
	int res=0;
	for(int i=1;i<=n;i++)
	{
		if(siz[i]==1)
		{
			int now=i,cnt=1;
			book[now]=1;
			while(now)
			{
				if(cnt==k)
					cnt=0,res++;
				now=f[now];
				if(book[now])
					break;
				book[now]=1;
				cnt++;
			}
		}
	}
	return res;
}
int main()
{
	scanf("%d",&n);
	len=sqrt(n);
	for(int i=1,u,v;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		a[u].pb(v),a[v].pb(u);
	}
	pre(1,0);
	for(int i=1;i<=len;i++)
		printf("%d\n",solve(i));
	las=n;
	for(int i=0;i<=n/len;i++)
	{
		int l=len+1,r=las,id=-1;
		while(l<=r)
		{
			int mid=l+r>>1;
			int ret=solve(mid);
			if(ret==i)
				r=mid-1,id=mid;
			else if(ret>i)
				l=mid+1;
			else
				r=mid-1;
		}
		if(id==-1)
			continue;
		for(int j=id;j<=las;j++)
			ans[j]=i;
		las=id-1;
	}
	for(int i=len+1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}