Description：

给出若干个完全图，然后完全图之间首尾相连并成环，要求删边使得两点之间路径数不超过 $1$ ，求方案数。

$1\leqslant n\leqslant 10^5$

Solution：

首先求出 $f[i]$ 表示 $i$ 个点的团的生成森林个数，我们可以枚举 $n$ 所在的树，然后式子就是： $$ f[n]=\sum_{i=1}^n\binom{n-1}{i-1}i^{i-2}f[n-i] $$ 这个可以分治 $FFT$ ，另一种求法是设 $f'[i]=i^{i-2}$ 为生成树的个数，那么有 $f=\exp f'$ ，于是可以多项式 $\exp$ 。

然后连起来的边可以随便选，方案数是 $\prod f[c_i]\times 2^{m}$ 。

但是这样会加多，也就是如果有一个图 $1$ 和 $n$ 被连起来了，那么最后会形成一个大环，于是我们再计算一个 $g[i]$ 表示 $1$ 和 $n$ 在一个点中的方案数，那么有： $$ g[i]=\sum_{i=2}^n\binom{n-2}{i-2}i^{i-2}f[n-i] $$ 于是再减去 $\prod g[c_i]$ 即可。

Code：

没有代码