有标号边双计数（25.11.11）
设 \(f_{n, m}\) 表示 \(n\) 个点形成含 \(m\) 个点双的连通图的方案数。
\(g_n\) 表示 \(n\) 个点的连通图数量。\(g_n\) 容易通过容斥算出：
\[g_n = 2^{\binom{n}{2}} - \sum_{i=1}^{n - 1} \binom{n - 1}{i - 1} \times g_i \times 2^{\binom{n - i}{2}}\\
\]
\(f_{n, 1}\) 可以通过容斥得到：
\[f_{n, m} = g_n - \sum_{i=2}^n f_{n, i}
\]
关键是计算 \(f_{n, m}\)，其中 \(m \gt 1\)。圆方树建出来后，设这 \(m\) 个方点的子节点个数为 \(a_i\)，那么这个点双内部的方案数就是 \(f_{a_i + 1, 1}\)。点双之间的连边，相当于有 \(m + 1\) 个连通块，大小为 \(1, a_1, a_2, \dots\)。直接连的方案数是 \(n^{m - 1} \times \prod a_i\)。由于我们不关心一个点双是哪一个节点连向父节点（即实际上是方点连出去的），所以方案数要除掉 \(\prod a_i\)，也就是 \(n^{m - 1}\)。因此最终的式子就是：
\[\begin{aligned}
f_{n, m} &= \sum_{a_1 + \dots + a_m = n - 1} \frac{1}{m!} \times \binom{n - 1}{a_1, \dots, a_m} n^{m - 1} \prod_{i=1}^m f_{a_i + 1, 1}\\
&= \frac{n^{m - 1}(n-1)!}{m!} \sum_{a_1 + \dots + a_m = n - 1} \prod_{i=1}^m \frac{f_{a_i + 1, 1}}{a_i!}
\end{aligned}
\]
可以通过辅助数组 \(h_{n, m} = \sum_{\sum a_i = n} \prod \frac{f_{a_i + 1, 1}}{a_i}\) 进行转移。最终可以在 \(O(n^3)\) 内解决。