P9167

洛谷题面 原题等价于计算有多少个点集 $V$，满足删去 $V$ 的导出子图中的边后，原图形成了 $|V|$ 个连通块，且连通块大小的极差 $\le k$。形成 $|V|$ 个连通块又等价于 $V$ 中的每个点都分属不同的连通块，我们称这样的 $V$ 为合法的。 考虑在同一个点双连通分量中的三点 $u ......

考场降智系列。 首先手模一下，发现题意就是让我们选出一个点集，删去之间的所有边，使得这个点集中的每个点都不在同一个连通块中。首先可以发现选择的点集一定是若干个点双，如果一个点双中的点没有全部被选择，那么一定有其中至少两个点仍然在同一连通块中。其次，我们发现选取的点集一定是联通的，否则同样会有两个点在 ......