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