洛谷 P6789 - 寒妖王（子集卷积+矩阵树定理）

洛谷题面传送门

像极了我验的那道牛客多校（第六场 C Forest）……

考虑对于每条边，计算其在最大生成基环森林中的概率，乘以边权求和就是答案。现在问题在于如何计算每条边在最大生成基环森林中的概率，显然比它权值小（如果权值相同则比较编号）的那些边存不存在不影响这条边是否在最大生成基环森林中，因此我们只用考虑那些活着的权值比它大的边组成的子图即可，记 \(G\) 为权值比它大且活着的边组成的图，稍加分析可以得到这条边在当且仅当：

• 这条边两个端点在 \(G\) 中连通，且该连通块是一棵树
• 这条边两个端点在 \(G\) 中不连通，且两个端点所在连通块中至少有一个是树

这样一来考虑设 \(f_S\) 表示 \(S\) 所在连通块是连通图的概率，\(g_S\) 表示 \(S\) 所在连通块是树的概率，\(f_S\) 是经典子集 \(\ln\) 问题。\(g_S\) 可以矩阵树定理求出，前者复杂度显然 \(2^nn^2\)，后者复杂度 \(2^nn^3\)。然后第一种情况直接枚举这两个端点所在连通块，第二种情况直接枚举两个连通块复杂度是 \(3^n\) 的，太劣了，不过发现可以子集卷积优化到 \(2^nn^2\)，具体方法是假设两个连通块分别为 \(S_1,S_2\)，那么发现概率可以写成 \((f_{S_1}f_{S_2}-(f_{S_1}-g_{S_1})(f_{S_2}-g_{S_2}))·c(S_1,S_2)·c(S_1\cup S_2,U-S_1\cup S_2)\)，其中 \(c(S,T)\) 表示 \(S,T\) 之间无边的概率，而如果设 \(E_S\) 表示 \(S\) 内部的边数，那么 \(c(S,T)=0.5^{E_{S\cup T}-E_S-E_T}\)，这是可以写成只与 \(S_1,S_2\) 和 \(S_1\cup S_2\) 有关的式子的，于是子集卷积即可。

总复杂度 \(m2^nn^3\)。