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构成一个连通块,其余两个节点分别为一个连通块。