CF1266F.Almost Same Distance

Let $G$ be a simple graph. Let $W$ be a non-empty subset of vertices. Then $W$ is almost-$k$-uniform if for each pair of distinct vertices $u,v \in W$ the distance between $u$ and $v$ is either $k$ or $k+1$.

You are given a tree on $n$ vertices. For each $i$ between $1$ and $n$, find the maximum size of an almost-$i$-uniform set.

设 $G$ 是一个简单图，$W$ 是顶点集的一个非空子集。若对任意两个不同的顶点 $u,v \in W$，$u$ 与 $v$ 之间的距离均为 $k$ 或 $k+1$，则称 $W$ 是几乎-$k$-均匀集（almost-$k$-uniform set）。

给定一棵含 $n$ 个顶点的树。对每个 $i$（$1 \le i \le n$），求几乎-$i$-均匀集的最大大小。

The first line contains a single integer $n$ ($2 \leq n \leq 5 \cdot 10^5$) – the number of vertices of the tree.

Then $n-1$ lines follows, the $i$-th of which consisting of two space separated integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$) meaning that there is an edge between vertices $u_i$ and $v_i$.

It is guaranteed that the given graph is tree.

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

接下来是 $n-1$ 行，其中第 $i$ 行包含两个用空格分隔的整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示顶点 $u_i$ 与 $v_i$ 之间存在一条边。

保证所给图是一棵树。

Output a single line containing $n$ space separated integers $a_i$, where $a_i$ is the maximum size of an almost-$i$-uniform set.

输出一行，包含 $n$ 个以空格分隔的整数 $a_i$，其中 $a_i$ 表示一个几乎-$i$-一致集合的最大大小。

Consider the first example.

• The only maximum almost-$1$-uniform set is ${1, 2, 3, 4}$.
• One of the maximum almost-$2$-uniform sets is or ${2, 3, 5}$, another one is ${2, 3, 4}$.
• A maximum almost-$3$-uniform set is any pair of vertices on distance $3$.
• Any single vertex is an almost-$k$-uniform set for $k \geq 1$.

In the second sample there is an almost-$2$-uniform set of size $4$, and that is ${2, 3, 5, 6}$.

考虑第一个样例。

• 唯一的极大几乎-$1$-均匀集是 $\{1, 2, 3, 4\}$。
• 一个极大几乎-$2$-均匀集是 $\{2, 3, 5\}$，另一个是 $\{2, 3, 4\}$。
• 任意两个距离为 $3$ 的顶点构成一个极大几乎-$3$-均匀集。
• 任意单个顶点对于所有 $k \geq 1$ 均构成一个几乎-$k$-均匀集。

在第二个样例中，存在一个大小为 $4$ 的几乎-$2$-均匀集，即 $\{2, 3, 5, 6\}$。