CF1805D.A Wide, Wide Graph
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a tree (a connected graph without cycles) with n vertices.
Consider a fixed integer k . Then, the graph Gk is an undirected graph with n vertices, where an edge between vertices u and v exists if and only if the distance between vertices u and v in the given tree is at least k .
For each k from 1 to n , print the number of connected components in the graph Gk .
输入格式
The first line contains the integer n ( 2≤n≤105 ) — the number of vertices in the graph.
Each of the next n−1 lines contains two integers u and v ( 1≤u,v≤n ), denoting an edge between vertices u and v in the tree. It is guaranteed that these edges form a valid tree.
输出格式
Output n integers: the number of connected components in the graph Gk for each k from 1 to n .
输入输出样例
输入#1
6 1 2 1 3 2 4 2 5 3 6
输出#1
1 1 2 4 6 6
输入#2
5 1 2 2 3 3 4 3 5
输出#2
1 1 3 5 5
说明/提示
In the first example: If k=1 , the graph has an edge between each pair of vertices, so it has one component. If k=4 , the graph has only edges 4↔6 and 5↔6 , so the graph has 4 components.
In the second example: when k=1 or k=2 the graph has one component. When k=3 the graph Gk splits into 3 components: one component has vertices 1 , 4 and 5 , and two more components contain one vertex each. When k=4 or k=5 each vertex is a separate component.