CF1805D A Wide, Wide Graph

题目描述

给定一棵 $n$($2\leq n\leq 10^5$)个节点的无根树,对于每个 $k$($1\leq k \leq n$),定义一个无向图 $G_k$,其中由边连接的两个节点 $u$ 和 $v$ 的距离至少为 $k$。请你计算 $G_k$ 的连通块个数。

输入格式

输出格式

说明/提示

$2\leq n\leq 10^5$ 第一个样例中,当$k=1$时,所有的点都连通;当$k=4$时,只有$(4,6)$和$(5,6)$两条边连通,所以连通块个数为4。 第二个样例中,当$k=3$时,节点1、4、5构成一个连通块,其余两个节点分别为一个连通块。