补题需要用到的学习资料……从别人的博客里搬运一下。

原文链接：https://www.cnblogs.com/HocRiser/p/10390772.html
原文作者：HocRiser
原文发布时间：2019-02-17 12:55

Prufer Codes

在一棵 $n$ 个节点带标号树中，我们认为度数为 $1$ 的点为叶子。$n$个点的树的 Prufer 序列是经过下面流程得到的一个长度为 $n-2$ 的序列。

1. 若当前树中只剩下两个点，退出，否则执行2。
2. 找到树中编号最小的节点，将与它相连的那个点的编号加入 Prufer 序列的末尾，并将这个叶子删除。返回1。

显然，每棵树都唯一对应一个 Prufer 序列，而每个 Prufer 序列也唯一对应一棵树。可以通过一下流程得到这棵树。

1. 令$A = {1,2,\ldots,n}$，不断重复 2 直到 Prufer 序列为空。
2. 找到 $A$ 中最小的不在 Prufer 序列中的点，将其与 Prufer 序列首元素连边，然后同时删除这个点与序列首元素。
3. 此时 $A$ 中还剩下两个点，将这两个点连边。

根据以上流程，不难发现：若点 $i$ 在树中的度数为 $a_i$，则它在 Prufer 序列中会出现 $a_i-1$ 次。

Cayley’s Formula

Prufer 序列中的每个元素都可以从 $1$ 取到 $n$，且每种方案会唯一对应一棵带标号无根树。 所以，由于 Prufer 序列共有$n ^ {n-2}$ 个，$n$ 个点的带标号无根树就有$n ^ {n - 2}$ 种。

拓展：

1. 显然，$n$ 个点的带标号有根树有 $n ^ {n - 2}$ 种。
2. 当树中每个点的度数 $a_i$ 都已经确定后，由 Prufer 序列得，满足条件的树共有 $\frac{(n-2)!}{\prod a_i!}$ 种。

例题：BZOJ1005, BZOJ1211, BZOJ1430

Generalized Cayley’s Formula

已知 $n,k$，求 $f(n,m)$ 表示 $n$ 个点组成的共有 $m$ 棵树的森林，且 $1,2,\ldots,m$ 分别属于不同的树，的方案数。

先给出结论：$f(n,m)=m\cdot n^{n-m-1}$ （显然可以发现$f(n,1)=n^{n-2}$）

证明

显然，$f(1,1)=0$，$f(n,0)=0(n\geq 1)$。

数学归纳，假设对于所有 $i<n$ 的 $f(i,j)$ 都已证明。

考虑 $1$ 号点属于的那棵树，枚举 $1$ 号点的度数 $i$，则删除后这张图会变成 $n-1$ 个点，$m+i-1$ 棵树。

$f(n,m)=\sum\limits_{i=0}^{n-m}\binom{n-m}{i}f(n-1,m+i-1)$

将原式代入，有 $f(n,m)=\sum\limits_{i=0}^{n-m}\binom{n-m}{i}(m+i-1)(n-1)^{n-m-i-1}=mn^{n-m-1}$

命题得证。

拓展：显然 $n$ 个点组成有根树森林的方案为$\sum\limits_{k=1}^{n}n^{n-k-1}\times k\times \binom{n}{k}$

应用：CF1109D

定理拓展

$n$ 个带权的点，定义每条边的权值为相连的两个点的权值之积，定义一棵树的权值是所有边的权值之积，求所有树的权值和。

相当于每棵树中每个点的权值的度数次方的和。考虑 Prufer 序列，每个点都恰出现 $\text{度数} - 1$ 次。于是根据乘法分配律，答案为 $(\text{所有点权值之积}) \times (\text{所有点权值之和}) ^ {n - 2}$。

这个推论包含了上面所有定理。当所有点权值取 $1$ 时，就是Cayley’s Formula。当将点 $1 \sim m$ 缩成一个权值为 $m$ 的点时，就是Generalized Cayley’s Formula。

以上所有似乎都可以用 Matrix Tree 那一套理论通过化简行列式得到。