生成树计数问题

咕咕咕…

upd 好家伙，原来有个叫矩阵树定理的东西 QAQ 有空学吧（

随手记一下这些奇奇怪怪的东西，说不定会派上用场。

以下默认为无向图。

1. $n$ 个不同的点构成的完全图，其生成树个数为 $n^{n-2}$ 。注意生成树没有根节点。

   另一种说法为：一个带标号的 $n$ 个结点的完全图的生成树个数有 $n^{n−2}$ 个。

   证明：Cayley公式，见浅谈 Prüfer 序列

2. $n$ 个不同的点构成的完全图，其有根生成树的个数为 $n^{n-1}$ 。

   见上一条，枚举哪个点是根，即可得到。

3. $n$ 个无区别点构成的完全图，其不相交生成树的个数为 $\left\lfloor\frac{n}{2}\right\rfloor$ 。

   见 UOJ460 新年的拯救计划 题解