Luogu6789 寒妖王

题意 ： 给定 个点 条边的无向图，边有边权。

每条边有 的概率被删除，求最后这张图的最大基环树森林（可以有普通树）的边权和的期望。

答案对 取模。

，，时限。

---

计算各个方案的权值和然后除以 即可。

注意到“生成基环树”这一限制和“生成树”这一限制都具有拟阵性质，于是用类似 Kruskal 的算法可以求解“最大生成基环森林”。

于是我们就得到了 的暴力。

不妨设边权互不相等，将边权从大到小排序，对每条边 分别考虑不被加入答案的充要条件。

考虑比这条边权值更大的边集 ：

• 这条边两侧是同一个基环树。（即联通，但不是一棵树）

• 这条边两侧是两个不同的基环树。

对于第一类情况，正难则反，枚举边 所在的点集 ，用构成极大连通图的方案数减去构成极大生成树的方案数。

记 分别表示只考虑编号 的，且与点集 有交（而非完全包含）的所有边，使得 形成极大 连通图/树 的方案数。

（换句话说，若某种方案 之间有边，不会被计入，因为不是极大的）

• 对于 的 ，有转移 ：

  分两类讨论，不加入或加入。其中连通图内部多边没关系，但是树内部不能多边。

• 若 都不在 内，由定义，不考虑这条边，无贡献。

• 若 其中之一在 内，考虑这条边，但一旦这条边出现， 必不是极大联通块，仍无贡献。

第一类方案数为

其中 为 中与 不交的边数，即考虑其余边的加入情况。

第二类方案数需要枚举 并拆成两个不交的集合，为

记两类方案总数为 ，注意前面的边方案数为 ，后面的边方案数为 ，于是 被计入的总方案数为 。

复杂度为 ，适当地使用剪枝和滚动数组可以大幅减小常数。