显然地，这 \(t\) 座城市一定由每个连通块出一座得来，换言之，新修建道路的两城市原来一定不连通。
进一步可以想到，若选择了 \(u, v\) 两座城市且它们连通，则 \(u \rightsquigarrow v\) 上的所有城市都应被选择。
更进一步地可以推出，若选择的城市同属一个点双，则该点双内的所有城市都应被选择。
对给定的图建出圆方树，定义一次 选择 操作为：选择该城市（对圆点）或选择该点双内的所有城市（对方点），那么有：
- 选择的方点构成一个连通块。
- 删去选择的方点后，剩余的所有连通块大小（圆点数量）的极差不超过 \(k\)。
接下来分类考虑解法。
当 \(k = 0\) 时：
枚举每个连通块的大小 \(s(s | n)\)。
首先，必定有树的重心 \(o \in V'\)，于是考虑以 \(o\) 为根 树型 DP。
证明：
若 \(o \notin V'\)，则 \(g\) 所在的连通块的大小一定 \(> \dfrac n2\)，无论 \(k\) 怎么取都不符合题意。
设 \(f(u)\) 表示 \(u\) 所对应的方点能否被删除，每个连通块的大小为 \(s\) 成立，则一定有 \(f(o) = 1\)。
- 对圆点，若 \(\exist v \in son_o, sz_v \ge k\)，则 \(f(u) = 1\)，否则 \(f(u) = 0\)。额外地，若 \(f(u) = 0\)，则要求 \(\sum\limits_{v \in son_u} sz_v = k\)。
- 对方点，\(f(u) = \prod\limits_{v \in son_o} f(v)\)。
时间复杂度 \(\mathcal O(n \sqrt n)\)。
当 \(k = 1\) 时：
枚举 \(s \in [1, \lfloor \dfrac n2 \rfloor]\)，则每个连通块的大小 \(\in [s, s + 1]\)。
设 \(f(u)\) 表示以 \(u\) 为根的子树中的方案数，\(v \in son_u\)。
-
对圆点，
- 若 \(sz_v < s\)，则 \(v\) 一定不能删去。
- 若 \(sz_v > s\)，则 \(v\) 一定要删去。
- 否则有 \(sz_v = s\)，那么当 \(f(v) = 0\) 时，\(v\) 一定不能删去，否则 \(v\) 可删可不删，额外地，若不删 \(v\)，则需要满足不存在未被删去的 \(v'\)。
设 \(c\) 为所有可删可不删的 \(\prod f(v)\)：
- 若 \(\sum\limits_{f(v) < s} sz_v + 1 \in [k, k + 1]\)，则 \(f(u) \gets c\)。
- 若 \(\sum\limits_{f(v) < s} sz_v = 0\)，则 \(f(u) \gets \sum\limits_{sz_v = s \and f(v) > 0} \dfrac c{f(v)}\)，又因为满足条件的 \(f(v)\) 势必为 \(1\)，所以令 \(T = \sum[sz_v = s \and f(v) > 0]\)，则有 \(f(u) \gets Tc\)。
-
对方点，\(f(u) = \prod f(v)\)。
最后注意到有算重的情况，需要容斥减掉 \(k = 0\) 的 \(s \in [2, \lfloor \dfrac n2 \rfloor]\)。
时间复杂度 \(\mathcal O(n^2 + n \sqrt n)\)。
考虑优化，瓶颈在 \(k = 1\) 的情况。
发现对答案有贡献的 \(s\) 必然满足 \(n \bmod s \le \lfloor \dfrac ns \rfloor\)，将 \(n \bmod s\) 替换为 \(n - s\lfloor \dfrac ns \rfloor\) 后可以得到 \(n \le (s + 1)\lfloor \dfrac ns \rfloor\)，解得 \(s | d\) 或 \((s - 1) | d\)，枚举这些 \(s\) 即可。
时间复杂度 \(\mathcal O(n \sqrt n)\)。
代码（待补）：
标签：lfloor,sz,连通,limits,省选,dfrac,sum,2023,D1T2 From： https://www.cnblogs.com/chy12321/p/17678082.html