[NOIP2022] 建造军营 题解

· · 题解

先研究一下骗分,对于前 7 个点,可以枚举出所有 2^n -1 种建造军营的情况,然后看一下哪些边是必须选的,哪些边是可选可不选。

对于特殊性质 A ,考虑最左边的点是 l ,最右边的点是 r。 l=r 时要特殊考虑,此时所有边都可选可不选,有 n\times 2^{n-1} 种。对于其他情况,它们之间的 r-l 条边必须选,外面的 n-1-(r-l) 条边可选可不选,中间的 r-l-1 个点可选可不选。这样有 2^{n-1-(r-l)+r-l-1}=2^{n-2} 种,和 l,r 是无关的,也就是说总共有 C_{n}^2\cdot2^{n-2} 种。把这两部分加起来就是答案。

接着研究下样例 2 ,图为一个三角通过桥连着外面一个点,发现 184=8\times 23。这个 8 其实是三角形的三条边可选可不选,因为这三角在一个边双连通分量里,无论破坏哪条边依然连通,也就是说这道题最终答案会有一个 2^k 的系数,其中 k 为所有边双里的边的数量总和。

- 外面的点建了军营,此时三角上有 $7$ 种存在军营的情况桥必须选,剩下三角无军营的情况桥可选可不选,一共 $9$ 种。 - 外面的点没建军营,此时三角上 $7$ 建军营的情况,桥都可选可不选,一共 $14$ 种。 这样样例就推出来了,通过上面的启发,这题第一步是求边双连通分量,然后缩点成一棵树。缩点后的内部边就没用了(化成了一个 $2^k$ 的系数最后乘上去),只需考虑原图每个桥是否要选。 通过树形 DP 来解决问题,记 $f_u$ 表示 $u$ 子树中至少选了一个点,且能连接到 $u$ (也就是中途的树边都必须选)的方案数,$a_u$ 表示缩点后每个点包含原图的点数,$sz_u$ 为树上的子树大小(这样一个子树内的边数就是 $sz_u -1$)。 考虑求 $f_u$,结点 $u$ 中的点随便选,这样有 $2^{a_u}$ 种,对每个儿子 $v$ 分两种情况: - 该儿子的子树中一个点也没选,此时子树内的边和$<u,v>$ 这条边任意选,有 $2^{sz_v}$ 种; - 该儿子的子树至少选了一个点,此时 $<u,v>$ 这条边必须选,有 $f_v$ 种 上述情况会产生一个点都不选的可能,此时所有边都可选可不选,所以要减去 $2^{sz_u-1}$ 种。 综上所述, $f_u=2^{a_u}\prod\limits_v(2^{sz_v}+f_v)-2^{sz_u-1}$,而最终答案的方案数可以利用 $f_u$ 来计算。 为了保证每种建造军营的点集不重复不遗漏的计算,我们将在它们 LCA 处统计。也就是说在 $u$ 处统计的答案,要么是 $u$ 本身选了点,要么 $u$ 至少有两个儿子的子树选了点,这两种情况都在 $f_u$ 里出现。$u$ 作为 LCA,那么树外的边就可以随便选,这样有个 $2^{c-1-(sz_u-1)}=2^{c-sz_u}$ 的系数,其中 $c$ 为缩点后的点数。 考虑从 $f_u$ 中减去非法的方案,也就是结点 $u$ 没有选且只有一个儿子的子树里选了点。枚举儿子 $v$,有 $f_v$ 种方案,对于其他儿子的子树里的边都是可选可不选,这些边数为 $sz_u-1-sz_v$(注意 $<u,v>$ 这条边也是必须选的,否则不会在 $f_u$ 中)。 这样,$u$ 作为 LCA 对答案的贡献为 $(f_u-\sum\limits_v f_v\cdot2^{sz_u-sz_v-1})\times 2^{c-sz_u}$。 时间复杂度 $O(n+m)$,[具体细节见代码](https://www.luogu.com.cn/paste/7htallvs)。