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.

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.

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

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\}$ .