CF1805D A Wide, Wide Graph

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

N/A

N/A

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.