让 $$$G$$$ 成为一个简单的图表。令 $$$W$$$ 为顶点的非空子集。那么 $$$W$$$ 几乎是-$$$k$$$-均匀的,如果对于每对不同的顶点 $$$u,v \in W$$$,$$$u$$$ 和 $$$v$$$ 之间的距离是 $$$k$$$ 或 $$$k+1$$$。
给你一棵有 $$$n$$$ 个顶点的树。对于 $$$1$$$ 和 $$$n$$$ 之间的每个 $$$i$$$,找到几乎 $$$i$$$ 均匀集合的最大大小。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) – 树的顶点数。
然后是 $$$n-1$$$ 行,其中第 $$$i$$$ 行由两个空格分隔的整数 $$$u_i$$$、$$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) 组成,这意味着顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条边。
保证给定的图是树。
输出
输出包含 $$$n$$$ 空格分隔的整数 $$$a_i$$$ 的单行,其中 $$$a_i$$$ 是几乎 $$$i$$$ 均匀集合的最大大小。
示例
输入 #1
5 1 2 1 3 1 4 4 5
输出 #1
4 3 2 1 1
输入 #2
6 1 2 1 3 1 4 4 5 4 6
输出 #2
4 4 2 1 1 1
注意
考虑第一个例子。
- 唯一最大的几乎-$$$1$$$-均匀集合是$$$\{1, 2, 3, 4\}$$$。
- 最大的几乎$$$2$$$均匀集合之一是或$$$\{2, 3, 5\}$$$,另一个是$$$\{2, 3, 4\}$$$。
- 最大近似$$$3$$$均匀集是距离$$$3$$$上的任何一对顶点。
- 任何单个顶点都是 $$$k $$$ 的几乎 $$$k $$$ 一致的集合,$$$k \geq 1$$$。
在第二个样本中,有一个几乎 $$$2$$$ 大小一致的集合 $$$4$$$,即 $$$\{2, 3, 5, 6\}$$$。