题目背景

原题链接

1. 做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了
• 还没有提交，或者提交了 WA 了。

题目描述

给定一棵 $n$（$2\leq n\leq 10^5$）个节点的无根树，对于每个 $k$（$1\leq k \leq n$），定义一个无向图 $G_k$，其中由边连接的两个节点 $u$ 和 $v$ 的距离至少为 $k$。请你计算 $G_k$ 的连通块个数。

输入格式

第一行包含整数 $n$。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示树上的一条无向边。

输出格式

输出共 $n$ 行，每行一个整数，表示 $G_k$ 的连通块个数。

6
1 2
1 3
2 4
2 5
3 6

1 1 2 4 6 6

5
1 2
2 3
3 4
3 5

1 1 3 5 5

数据范围

$2\leq n\leq 10^5$

提示

第一个样例中，当 $k=1$ 时，所有的点都连通；当 $k=4$ 时，只有 $(4,6)$ 和 $(5,6)$ 两条边连通，所以连通块个数为 $4$。

第二个样例中，当 $k=3$ 时，节点 $1,4,5$ 构成一个连通块，其余两个节点分别为一个连通块。