P4426 [HNOI/AHOI2018]毒瘤

· · 题解

题传

纪念一手 800 AC。

DP 牛牛题，虚树 板板题。

若 m=n-1，则这是一棵树，那么显然有个很 easy 的动态规划，设 f_{x, 0/1} 为当前子树中 不选/选 根的方案数：

f_{x,0}=\prod_{(x, y) \in T} (f_{y, 0}+f_{y, 1}) f_{x,1}=\prod_{(x, y) \in T} f_{y, 0}

发现 m-(n-1) \le 11，什么意思呢？我们在原图中构造一颗生成树，则非树边不超过 11 条，我们弄出来这 11 条边对应的点集 D。

考虑暴力枚举集合 D 中的所有点的状态（是否在最终备选集合中），那么就珂以无视这 11 条额外边了，此时仍然还是树形 DP，复杂度 O(2^{22}n)，显然过不去。

考虑到每次只有一堆关键点（D 中的点）的限制条件被改变，这让我们联想到了虚树，那么建出虚树，考虑如何算虚树上相邻两点之间的贡献，不难发现中间这个部分还是一棵小树，且这棵树内显然是没有其他关键点的（不然就不满足虚树定义），那么我们提前将这个部分的答案预处理好，然后枚举 D 状态的时候在虚树上跑一遍计数 DP 就行了。

设 g(x, y, 0/1, 0/1) 为 原树上 x-y 路径所在连通块中，满足 x 选/不选，y 选/不选 的方案数，则：

f_{x,ty1}=k_x\prod_y (\sum_{ty2} f_{y,ty2} \times g(x, y, ty1, ty2))

注意虚树上的点在原树中除了连向儿子的边外可能还有一些单链，这些构成了上式的系数 k_x。

Code