123
P
令 \(p(i)\) 为选 \(i\) 个点的所有方案的积的和， \(q(i)\) 为将原图划分为 \(i\) 个连通块，且每个连通块中有且仅有1个选中点的方案数，那么题目所求可以表示为：
\[ \sum_{i=1}^N p(i) \times q(i) \]
考虑分别计算 \(p(i)\) 和 \(q(i)\) 。
\(p(i)\) 的计算是简单的，有 \(p(i)=[x^i]\prod(1+A_ix)\) ，暴力 \(O(n^2)\) 算即可。
考虑如何计算 \(q(i)\) ，最后形成的图边双缩点后一定是一棵树，于是考虑如下问题：
假设当前有 \(M\) 个连通块，每个连通块有 \(B_i\) 个点，满足 \(N=\sum B_i\) ，那么加 \(M-1\) 条边使之联通的方案数是 \((\prod B_i)N^{M-2}\) 。
再令 \(r(i)\) 表示 \(i\) 个点的边双个数，令 \(dp_{i,j}\) 表示把 \(i\) 个点分为 \(j\) 个边双，且所选择的 \(j\) 个点在不同边双内的所有方案的 \(\prod B_kr(B_k)\) 的和，那么有 \(q(i) = dp_{N,i} \times N^{i-2}\) 。该dp的转移为：
\[ dp_{i,j}=\sum_{k=1}^{i-j+1} \binom{i-j}{k-1} \times dp_{i-k,j-1} \times k \times r(k) \]
考虑如何计算 \(r(i)\) ，考虑容斥，令 \(dp2_{i,j}\) 表示把 \(i\) 个点分为 \(j\) 个边双的所有方案的 \(\prod B_kr(B_k)\) 的和，那么有转移：
\[ dp2_{i,j}=\sum_{k=1}^{i} \binom{i-1}{k-1} \times dp2_{i-k,j-1} \times k \times r(k) \]
令 \(s(i)\) 为 \(i\) 个点的连通块个数那么有：
\[ r(i)=s(i)-\sum_{j=2}^i dp2_{i,j} \times i^{j-2} \]
\(s(n)\) 满足 \(\sum_k\binom{n}{k}ks_k2^{\binom{n-k}{2}}=n2^{\binom{n}{2}}\)