对于 $n$ 个点组成的环大小为 $m$ 的基环树个数的问题，目前已知三种解法

解法一「动态规划」

在环上每个点下面搭树的方案数，相当于是在完全图中制造生成树，然后提一个点（即环上那个点）为根，故可用 $n^{n - 2}$ 来计算

然后就可以很容易想到一种背包解法，把环随便找个地方断一下，把它看成序列，即可令 $f_{i, j}$ 表示环序列前 $i$ 个点，已经使用了 $j$ 个点做环下的树的方案数，显然
$$
f_{i, j} = \sum\limits_{k = 0}^j f_{i - 1, j - k} \times \dbinom{n - m - (j - k)}{k} \cdot (k + 1)^{k - 1}
$$
然后答案要对环进行圆排列，即 $ans = f_{m, n - m} \times \frac{A_n^m}{2m}$

复杂度 $O (n^3)$

当然这样复杂度比较高，可以考虑将已经拼好的连通块和已经拼好的一棵树连接起来，令 $f_n$ 表示 $n$ 个点的答案

当然，为了保证不会算重，需要有一个特征点，即保证点 $1$ 不会在环上，即
$$
f_n = \frac{n}{n - m}\sum\limits_{i = m}^{n - 1} f_i \times i \cdot (n - i)^{n - i - 2} \cdot \dbinom{n - 1}{i}
$$
注意，前面的 $\frac{n}{n - m}$ 是因为在你令每个点作为那个不在环上的那个点的时候，实际上对于每个点它会被其它点作为不在环上的点时算重 $n - m$ 次，故需要除以 $n - m$

复杂度 $O (n^2)$

解法二「prufer序列」

考虑在做prufer序列的时候，对于序列长度来讲，将其缩成一个点，即有 $n - m + 1$ 个位置，但是在实际放点的时候，却应当是有 $n$ 种选择，因为环上不同点作为父亲的情况是不一样的，即有 $n^{n - m - 1}$ 个位置，然后再做一次圆排列，即乘上 $\frac{A_n^m}{2m}$，但是可以发现环所称的点作为非根节点（相对意义上）的时候，需要选定一个环上的点作为与父节点连接的点，即还需要乘上 $m$

故最后答案为，$ans = \frac{A_n^m}{2m} \cdot n^{n - m - 1} \cdot m$

复杂度 $O (n)$

解法三「生成函数」

考虑将基环树拆分为若干棵树的拼凑

注意此时需考虑的是有根树，即先将节点看作组合对象，根据 $Cayley$ 定理，$n$ 个节点的完全图有 $n^{n - 1}$ 棵有根树，则有根树的 EGF $T(x)$ 为
$$
T(x) = \sum\limits_{n = 1}^{\infty} n^{n - 1}\frac{x^n}{n!}
$$
那么此时将有根树看作组合对象，则将它们组成环，即基环树的 EGF $G(x)$ 为
$$
\begin{aligned}
G(x) &= \frac{1}{2}\sum\limits_{k = 3}^{\infty} \frac{T(x)^k}{k} \\
&= - \frac{1}{2}\ln (1 - T(x)) - \sum\limits_{k = 1}^2 \frac{T(x)^k}{k}
\end{aligned}
$$