Almost Same Distance

题意翻译

## 题目描述 给出一颗$n$个点的树($2\leq n\leq 5\times 10^5$)，对于$k\in[1,n]$，分别找出一个最大的点集，使得点集内任意两点间距离为$k$或$k+1$。 ## 输入格式 第一行输入一个整数$n$，表示树的结点数。 接下来$n-1$行，每行两个整数$u_i,v_i$，表示$u_i,v_i$间有一条边($1\leq u_i,v_i\leq n\ $)。 ## 输出格式 输出一行$n$个整数，第$i$个整数，表示当$k=i\ $时，对应的最大点集结点数。

题目描述

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.

输入输出样例

输入样例 #1

5
1 2
1 3
1 4
4 5

输出样例 #1

4 3 2 1 1

输入样例 #2

6
1 2
1 3
1 4
4 5
4 6

输出样例 #2

4 4 2 1 1 1

说明

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