宽广图

• 时间限制：1 秒

• 内存限制：256 MiB

题目描述

给定一棵包含 $n$ 个顶点的树。

对于每个整数 $k=1,2,\ldots,n$，构造一张新图：顶点集合仍为原树的 $n$ 个顶点；当且仅当原树中两个不同顶点之间的距离不少于 $k$ 时，在它们之间连一条边。

请分别求出这 $n$ 张新图中的连通块数量。

树上两点之间的距离定义为连接这两点的简单路径上的边数。

输入格式

第一行包含一个整数 $n$（$2\le n\le 10^5$），表示树的顶点数。

接下来 $n-1$ 行，每行包含两个整数 $u,v$（$1\le u,v\le n$），表示树中有一条连接顶点 $u$ 与 $v$ 的边。

保证给出的图是一棵树。

输出格式

输出 $n$ 个整数。第 $k$ 个整数表示距离阈值为 $k$ 时，新图中的连通块数量。

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

数据范围

对于所有数据，$2\le n\le 10^5$，输入图是一棵树。