解题思路

给一棵含 $n$ 个点的树。对每个 $k(1\le k\le n)$ 构造图 $G_k$：当且仅当树上两点距离 $d(u,v)\ge k$ 时，在 $G_k$ 中连边。要求输出 $G_k$ 的极大连通块（连通分量）个数。

关键观察（树的性质）：

• 设树的直径两端为 $s,t$，直径长度为 $D=d(s,t)$。对任意点 $v$，其离得最远的点一定是 $s$ 或 $t$，故点 $v$ 的离心率

  $$\mathrm{ecc}(v)=\max(d(v,s),\,d(v,t)).$$

题目内容

给定一颗包含 $n$ 个顶点的树，需要对每个整数 $k(1≤k≤n)$ 构造一张无向图，使得：

对于任意顶点 $u,v$ ，当且仅当它们在原树中的距离 $d(u,v)$ 不小于 $k$ 时，图中存在一条边连接 $u$ 和 $v$ 。

为了便于输出，请依次直接返回每个 $k$ 对应图中的极大连通块数目。

【名词解释】

距离：在树中，顶点 $u$ 与顶点 $v$ 之间的前单路径上的边数，即为它们间的距离，记为 $d(u,v)$ ；

极大连通块：对于图上的任意一个点集 $\mathbb S$ ，如果点集中的任意两点 $u,v$ 满足 “ $u$ 到 $v$ 的简单路径上的所有点都在点集中”，则称 $\mathbb S$ 是一个连通块。特别的，单独的点也构成一个连通块。如果一个连通块已经无法再添加点，则称其为极大连通块。

输入描述

第一行输入一个整数 $n(1≤n≤2× 10^5)$，表示树的顶点数；

此后 $n-1$ 行，第 $i$ 行输入两个整数 $u_i,v_i(1≤u_i,v_i≤n;u_i≠v_i)$，表示原树中第 $i$ 条边连接顶点 $u_i$ 与顶点 $v_i$ 。

输出描述

输出 $n$ 个整数 $p_1,p_2,…,p_n$，其中 $P_k$ 表示当 $k=1,2,...,n$ 时构造图的连通分量数目；相邻整数之间用空格分隔。

样例1

输入

5
1 2
1 3
3 4
3 5

输出

1 1 3 5 5

说明

在第一个样例中，原树包含边 {$(1,2),(1,3),(3,4),(3,5)$};

当 $k =1$ ，任意顶点对均满足 $d(u,v)≥1$，构造图完全连通，连通分量数为 $1$;

当 $k= 2$ ，点对 $(2,4),(2,5),(2,3),(1,4),(1,5),(4,5)$ 满足距离 $≥2$，构造图完全连通，连通分量数为 $1$ ;

当 $k= 3$ ，仅质点对 $(2,4),(2,5)$ 满足距离 $≥3$，它们与顶点 $2,4,5$ 形成一连通块，其他质点独立，连通分量数为 $3$;

当 $k=4$ ，没有任何边，图无边，连通分量数等于顶点数 $5$ 。

样例2

输入

7
1 2
1 3
1 4
2 5
5 6
6 7

输出

1 1 1 3 5 7 7