306887: CF1266F. Almost Same Distance
Memory Limit:256 MB
Time Limit:5 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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