D. A Wide, Wide Graph
dfs and similar; dp; graphs; greedy; trees
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\).
The first line contains the integer \(n\) (\(2 \le n \le 10^5\)) — the number of vertices in the graph.Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) (\(1 \le u, v \le 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 \(G_k\) for each \(k\) from \(1\) to \(n\).
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 \leftrightarrow 6\) and \(5 \leftrightarrow 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 \(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.