P9167 [省选联考 2023] 城市建造

Alex_Wei · 2023-04-12 20:37:38 · 题解

P9167 [省选联考 2023] 城市建造

因为选择的城市数等于连通块数，所以每个连通块恰选择一个城市，否则无法连通。

先在不考虑连通块大小的限制下，探究合法的充要条件。

性质和结论

对于选择的两个城市，如果存在一条不经过重复点的简单路径连接它们，则路径上的每个点都要选择。否则，必然存在某两个选择的城市连通。

相反，如果满足条件，将选择的城市之间的边删去后，这些城市两两不连通。可以反证。

因此，根据点双的性质，如果一个点双里面选了两个点，则整个点双都要被选择。

建出圆方树，称选择一个方点表示选择其周围的所有圆点，要求：

• 为保证选择的城市不连通，选择的方点是一个连通块。即若两个方点被选择，则它们简单路径上的所有方点均被选择。
• 删去选择的方点（相当于删去选择城市之间的边）后，每个连通块大小（圆点数量）相差不超过 k。

\boldsymbol{k = 0}

考虑 k = 0，则连通块大小 d 为 n 的因数。

考虑以重心 R 为根，则若一个方点被选择，其祖先方点一定被选择，且若 R 为方点，则 R 一定被选择。可以反证。

树形 DP，能剥子树就剥子树。设 f_i 表示：若 i 是圆点，能否删去其父亲方点（若 i 为根，则答案可以视为添加并强制删去 i 的父亲方点时整棵子树的答案）；若 i 是方点，能否删去其本身。f_R 即为所求。

• 对于圆点 i，枚举所有子结点 j（方点）。当 sz_j \geq d 时，要求 f_j = 1。否则 j 不能被删去，因此要求 sz_j < d 的 sz_j 之和恰等于 d。
• 对于方点 i，f_i = 1 当且仅当其所有子结点 j 的 f_j = 1。

\boldsymbol{k = 1}

考虑 k = 1，枚举连通块大小 d = 1\sim \lfloor \frac n 2\rfloor，则 k = 0 的 2\sim \lfloor \frac n 2\rfloor 多算了，要减掉（因为 n\geq 3，所以 k = 0 的 \lfloor \frac n 2\rfloor + 1 一定不合法）。

类似地，设 f_i 表示对应方案数，f_R 即为所求。

• 对于圆点 i：

  • 若 sz_j < d，则 j 不能被删去。
  • 若 sz_j > d，则 j 必须被删去。
  • 否则 sz_j = d。当 f_j = 0 时，j 不能被删去。否则 j 可以被删去，也可以不删去，但后者要求不存在不能被删去的 j 且其它 j 均被删去。

  设 ss 为不能被删去的 \sum sz_j 加上 i 本身贡献的 1 表示 i 的连通块大小最小值，设 pd 为可以被删去的 \prod f_j：

  • 若 ss > d + 1，f_i = 0。
  • 若 d\leq ss\leq d + 1，则 f_i 加上 pd。
  • 若 ss = 1，则 f_i 加上对每个可以被删去的 sz_j = d，\frac {pd} {f_j} 之和。因为 sz_j = d 且 f_j > 0 时 f_j = 1，故 \sum \frac {pd} {f_j} 等于 pd 乘以 sz_j = d 且 f_j > 0 的 j 的数量 cnt。

  注意第二、三个条件可以同时满足。

• 对于方点 i，f_i 等于 \prod f_j。