P8867 [NOIP2022] 建造军营 题解

complete_binary_tree · 2024-12-25 19:54:23 · 个人记录

原题

发现只有割边被切断才会有影响。于是缩边双。

设 f_u 为 u 子树中选至少一点的方案数。

显然 f_u 初始为 2^{E_u+V_u}，E_u 为边的个数，V_u 为点的个数。

那么 v \in \text{son}_u 的贡献就是：

• 选至少一点：f_v。

• 啥也不选：2^{sum_v+1}，其中 sum_v 表示 v 子树中边的数量，+1 是因为 <u,v> 可选。

由于最少选一点，所以最后要减去 2^{sum_u}。

对答案的贡献：此时不能选到父亲的边（会算重），其他边随便选，即 \sum_{u=1}^n f(u) \cdot 2^{m-sum_u-[fa_u]}。