codeforces#P1266F. Almost Same Distance
Almost Same Distance
Description
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.
Input
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
Output a single line containing $n$ space separated integers $a_i$, where $a_i$ is the maximum size of an almost-$i$-uniform set.
Samples
5
1 2
1 3
1 4
4 5
4 3 2 1 1
6
1 2
1 3
1 4
4 5
4 6
4 4 2 1 1 1
Note
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\}$.