考虑判定一个图是否合法。让我们对每一个点双连通分量考虑。
对于一个点双中的一个点 u,设它的悬挂集 S_u 包含所有 v,其中 v 满足存在一个点 k,k 与 u 同点双,且 u 在 k 与 v 的必经路径上。具体一点 S_u 就是 u 和 u 周围不在该点双的那部分。很容易发现如果 |S_u| \bmod 2=1,那么 u 的悬挂集除 u 外内部已经匹配完了,u 只能和该点双内部匹配。如果 |S_u| \bmod 2=0,那么 u 一定会和它的悬挂集中某个点匹配。
我们给出如下性质:
否则,我们一定可以找到点双中相邻两点 x,y,其中 |S_x| \bmod 2=0,|S_y| \bmod 2=1,由于 x 不能和该点双内部匹配,y 必须和点双内部匹配,所以我们保留的生成树中只要把 y 设为叶子,并且连向 x,此时一定没有包含 y 的匹配。于是图一定不合法。
当所有 |S_u| \bmod 2=0 时,该点双内不会产生匹配,忽略。
当所有 |S_u| \bmod 2=1 时,点双内所有点都在这里面发生匹配。我们考虑此时一个点双的合法性。
首先点数肯定要是偶数。下面我们证明,如果这个点双内有点的度数大于等于 3 就无解。考虑反证,设 v1 连向了 v2,v3,v4。考虑以下生成树:让 v1,v2 连通,v2 和 v3 分别与 v4 用一条不经过 v1 的路径连接,其余随便连。再考虑断开 v1,v2 的边,连接 v1,v3 的边。以 v4 为根,如果这两个生成树都有完美匹配,那么意味着 v2 和 v3 子树都匹配上了。此时,如果我们连接 v1,v2,v1,v3,v1,v4,断开 v2,v3 与父亲的边。你会发现 v1,v2,v3 完全无法匹配,所以就寄了。所以此时点双只能是一个偶环或者两点一边。
于是我们可以通过以下方式构造所有好的图:
如果把初始连通块看成一个点的话,最终就是一个若干个点双的连通图。
然后我们考虑如何计数。
首先我们肯定要算 n 个点连通图数量和点双数量。
设 g_n 表示 n 个点的连通图数量,容易得到:g_n=2^{\frac{n(n-1)}{2}}-\sum\limits_{i=1}^{n-1}\binom{n-1}{i-1}2^{\frac{(n-i)(n-i-1)}{2}}g_i。
设 f_{n,m} 表示有 n 个点 m 个点双的连通图数量。有 f_{n,1}=g_n-\sum\limits_{i=2}^{n-1}f_{n,i}。
关键问题是怎么算 f_{n,m},考虑钦定一个点为根建出点双的圆方树,那么显然有 m 个方点。设第 i 个方点的儿子数为 a_i,那么内部一个点双的方案就是 f_{a_i+1,1}。外层还要将方点圆点连起来。此时相当于有 m+1 个连通块,大小分别为 1,a_1,a_2,...,a_m,我要把它们连成树。此时方案数为 n^{m-1}\prod\limits_{i=1}^{m}a_i。但是因为是圆方树,所以一个块中是哪个儿子连向父亲的并不重要,于是答案除以 \prod\limits_{i=1}^{m}a_i,最终就是 n^{m-1}。再处理一下编号就可以得到转移式 f_{n,m}=\frac{n^{m-1}(n-1)!}{m!}\sum\limits_{a_1+...+a_m=n-1}\prod\limits_{i=1}^{m}\frac{f_{a_i+1,1}}{a_i!}。
最后一步是算答案。枚举我们初始放入了 x 个连通块,第 i 个有 b_i 个点,进行了 y 次操作得到了 y 个点双。计算答案方法和算点双类似,不同的就是连通块大小和为 n。以及对于形成树后的一个方点,它的父亲是哪个点是确定的,但是你还需要对每个儿子确定它的连通块内用哪个点在这里形成点双。于是总共还要多乘上 \prod\limits_{i=1}^{x}b_i。(其中根的 b 为在算树形态时乘的)
于是此时答案为 \frac{n^{y-1}(x-1)!}{y!}\prod\limits_{i=1}^{x}b_i\sum\limits_{a_1+...+a_y=x-1}\prod\limits_{i=1}^{y}\frac{f_{a_i+1,1}}{a_i!}。
点双的式子以及 n 个点 \prod\limits_{i=1}^{x}b_i 和的东西都可以在 O(n^3) 内算出。总复杂度 O(n^3)。