← 返回题目列表

Codeforces · 1039/D

D. 给你一棵树

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

树是一种无向图,每对顶点之间只有一条简单路径。如果树的每个顶点属于这些路径(包括端点)中的一个以上,并且每个路径恰好由 $$$k$$$ 个顶点组成,则我们称一组简单路径 $$$k$$$ 有效。

给你一棵有 $$$n$$$ 个顶点的树。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,找出 $$$k$$$ 有效简单路径集的最大可能大小。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100\,000$$$) — 树中的顶点数。

接下来的 $$$n - 1$$$ 行描述了树,每行包含两个整数 $$$v$$$, $$$u$$$ ($$$1 \le v, u \le n$$$) — 相应边的端点。

保证给定的图是一棵树。

输出

输出 $$$n$$$ 数字,其中第 $$$i$$$ 是 $$$i$$$ 有效路径集中的最大可能路径数。

示例

输入 #1

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

输出 #1

7
3
2
1
1
1
1

输入 #2

6
1 2
2 3
2 4
1 5
5 6

输出 #2

6
2
2
1
1
0

注意

下图说明了实现第二个样本的最佳路径数的一种方法: