markdown

D. 给你一棵树

时间限制：每个测试点 $7$ 秒
内存限制：每个测试点 $512$ MB
输入：标准输入
输出：标准输出

题目描述

一棵树是一个无向图，其中任意两个顶点之间有且仅有一条简单路径。
我们称一组简单路径是 $k$-合法的，如果树中的每个顶点最多属于这些路径中的一条（包括路径的端点），并且每条路径恰好包含 $k$ 个顶点。

现在给你一棵有 $n$ 个顶点的树。对于每个 $k$ 从 $1$ 到 $n$（包含两端），请找出最大的可能的 $k$-合法简单路径集合的大小（即路径的数量）。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 100000$）—— 树中顶点的数量。
接下来的 $n-1$ 行描述这棵树，每行包含两个整数 $v$ 和 $u$（$1 \le v, u \le n$）—— 对应一条边的两个端点。
输入保证给定的图是一棵树。

输出格式

输出 $n$ 个数，其中第 $k$ 个数是 $k$-合法路径集合中路径数量的最大值。

样例

样例输入 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

注释

对于第二个样例，达到最优路径数量的一种方式如下图所示：