生成树计数问题

咕咕咕...

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 新年的拯救计划 题解