← 返回题目列表

Codeforces · 1805/D

D. 宽广的图表

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

给你一棵树(没有循环的连通图),其顶点为 $$$n$$$。

考虑一个固定整数$$$k$$$。那么,图 $$$G_k$$$ 是一个具有 $$$n$$$ 个顶点的无向图,其中当且仅当给定树中顶点 $$$u$$$ 和 $$$v$$$ 之间的距离至少为 $$$k$$$ 时,顶点 $$$u$$$ 和 $$$v$$$ 之间存在边。

对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,打印图中 $$$G_k$$$ 中连通分量的数量。

输入

第一行包含整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 图中的顶点数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$),表示树中顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证这些边形成一棵有效的树。

输出

输出 $$$n$$$ 整数:$$$G_k$$$ 图中每个 $$$k$$$ 从 $$$1$$$ 到 $$$n$$$ 的连通分量数。

示例

输入 #1

6
1 2
1 3
2 4
2 5
3 6

输出 #1

1 1 2 4 6 6

输入 #2

5
1 2
2 3
3 4
3 5

输出 #2

1 1 3 5 5

注意

在第一个示例中:如果 $$$k=1$$$,则该图在每对顶点之间都有一条边,因此它有一个分量。如果 $$$k=4$$$,则该图仅具有边 $$$4 \leftrightarrow 6$$$ 和 $$$5 \leftrightarrow 6$$$,因此该图具有 $$$4$$$ 个分量。

在第二个示例中:当 $$$k=1$$$ 或 $$$k=2$$$ 时,该图只有一个分量。当 $$$k=3$$$ 时,图 $$$G_k$$$ 分为 $$$3$$$ 组件:一个组件具有顶点 $$$1$$$、$$$4$$$ 和 $$$5$$$,另外两个组件各包含一个顶点。当 $$$k=4$$$ 或 $$$k=5$$$ 时,每个顶点都是一个单独的组件。