CF1805D.A Wide, Wide Graph

You are given a tree (a connected graph without cycles) with $n$ vertices.

Consider a fixed integer $k$. Then, the graph $G_k$ is an undirected graph with $n$ vertices, where an edge between vertices $u$ and $v$ exists if and only if the distance between vertices $u$ and $v$ in the given tree is at least $k$.

For each $k$ from $1$ to $n$, print the number of connected components in the graph $G_k$.

给你一棵树（一个无环的连通图），该树包含 $n$ 个顶点。

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

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

The first line contains the integer $n$ ($2 \le n \le 10^5$) — the number of vertices in the graph.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$), denoting an edge between vertices $u$ and $v$ in the tree. It is guaranteed that these edges form a valid tree.

第一行包含一个整数 $n$（$2 \le n \le 10^5$）—— 图中顶点的数量。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示树中顶点 $u$ 与顶点 $v$ 之间的一条边。保证这些边构成一棵合法的树。

Output $n$ integers: the number of connected components in the graph $G_k$ for each $k$ from $1$ to $n$.

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

In the first example: If $k=1$, the graph has an edge between each pair of vertices, so it has one component. If $k=4$, the graph has only edges $4 \leftrightarrow 6$ and $5 \leftrightarrow 6$, so the graph has $4$ components.

In the second example: when $k=1$ or $k=2$ the graph has one component. When $k=3$ the graph $G_k$ splits into $3$ components: one component has vertices $1$, $4$ and $5$, and two more components contain one vertex each. When $k=4$ or $k=5$ each vertex is a separate component.

在第一个例子中：若 $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$ 时，每个顶点各自构成一个连通分量。