题目链接：https://codeforces.com/contest/1805/problem/D
赛时没过的题。
思路：首先发现一个性质：对于k来说，如果树上的一个点到树的直径的两个端点的距离都小于k的话，那么这个点一定是一个孤立点。
证明：采用反证法：假设\(x,y\)为树的直径的两个端点，\(a,b\)为另外两个点，且有\(d[a][x]<k,d[a][y]<k,d[a][b]>=k\)。
\(当a,b都在直径上时，易证不成立。\)
\(当a在直径上，b不在时，则有dist[x][a]+dist[a][y]<dist[x][a]+dist[a][b],则以x,y为端点的链就不是直径，不成立。\)
\(当a不在直径上，b在时，不可能有dist[a][b]>=k,不成立\)。
\(当a,b都不在直径上时，比较复杂，画个图来证明。\)
思路：首先求出树的直径，接着求每个点到端点的距离，最后用一个后缀和求出大于等于k的边有多少个，统计答案即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int h[N],ne[2*N],num[2*N],idx;
int d1[N],d2[N];
int d[N];
int pre[N];
void add(int x,int y){
num[idx] = y,ne[idx] = h[x],h[x] = idx++;
}
void dfs(int u,int fa){
for (int i=h[u];i!=-1;i=ne[i]){
int v = num[i];
if (v==fa) continue;
d[v] = d[u]+1;
dfs(v,u);
}
}
void dfs1(int u,int fa,int dd[]){
for (int i=h[u];i!=-1;i=ne[i]){
int v = num[i];
if (v==fa) continue;
dd[v] = dd[u]+1;
dfs1(v,u,dd);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
memset(h,-1,sizeof(h));
int n;
cin>>n;
for (int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(1,-1);
int u,mx = -1;
for (int i=1;i<=n;i++){
if (mx<d[i]) u = i,mx = d[i];
}
memset(d,0,sizeof(d));
int v;
mx = -1;
dfs(u,-1);
for (int i=1;i<=n;i++){
if (mx<d[i]) v = i,mx = d[i];
}
dfs1(v,-1,d1);
dfs1(u,-1,d2);
for (int i=1;i<=n;i++){
pre[max(d1[i],d2[i])]++;
}
for (int i=n;i>=1;i--) pre[i] += pre[i+1];
for (int i=1;i<=n;i++){
cout<<min(n,max(1,n-pre[i]+1))<<' ';
}
return 0;
}