← 返回题目列表

Codeforces · 1266/F

F. 几乎相同的距离

中文机器翻译题面 查看原题

让 $$$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\}$$$。