题解：P6789 寒妖王

· · 题解

寒妖王

图计数题。

首先考虑确定没有消失的边集后如何找到权值最大的符合条件的边集。将边权从大到小排序，对于每条边讨论其连接的两个点的情况。如果这两个点没有联通或者其所在连通块内没有环就连上即可（类似于 Kruskal）。

不难发现如果对一个树求那么保留的边集合是一颗树，对联通图做保留的边集一定是基环树。

考虑对消失之后的权值求期望。把贡献拆到每条边上，期望最后处理，那么问题转化为有多少种方案使得这条边会被选中。

首先发现权值比这条边小的边都是不必要的，因此从大到小排序依次处理。那么一条边能被选上一共有三种情况。

下文记 f_S,g_S 分别表示点集为 S 的树和联通图的数量，cnt_S 表示点集 S 的导出子图的边的数量，U 为 \{1,2,3\cdots, n\}，这些东西都可以在 \operatorname{O}(3^n) 内求出。

  1. 原先的两个点已经联通。

此时如果能够选这条边那么原来的这个联通块一定是一个树。因此此时方案为：

\sum_{\{u,v\}\subseteq S} f_S\times 2^{cnt_{U-S}}
  1. 原先的两个点不连通且加入这条边后在前面的类 Kruskal 操作中形成的联通块为树。

那么两边的联通块都是树，方案数量为：

\sum_{u\in S,v\in T,S\cap T=\emptyset} f_S\times f_T\times 2^{cnt_{U-S-T}}
  1. 原先的两个点不连通且加入这条边后在前面的类 Kruskal 操作中形成的联通块为基环树。

那么原来有一个联通块是树，另一个联通块是图，讨论那一边是图即可。方案数为：

\sum_{u\in S,v\in T,S\cap T=\emptyset} (f_S\times g_T+g_S\times f_T)\times 2^{cnt_{U-S-T}}

对每条边都算一遍即可，时间复杂度 \operatorname{O}(m\times 3^n)，轻微卡常，有一些不必要的状态可以跳过。

可以用集合幂级数 ln 求 g，用矩阵树求 f 再高维前缀和计算答案做到 \operatorname{O}(n^2m\times 2^n)，快不了多少也没有必要。