← Home
write a go solution for Description:
You are given a tree (a connected graph without cycles) with n vertices.

Consider a fixed integer k. Then, the graph G_k 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 G_k.

Input Format:
The first line contains the integer n (2<=n<=10^5) — 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 Format:
Output n integers: the number of connected components in the graph G_k for each k from 1 to n.

Note:
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 4arrow6 and 5arrow6, 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 G_k 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.. Output only the code with no comments, explanation, or additional text.