Prüfer序列学习笔记
Prüfer 序列是真好用啊。
定义
对于一棵 $n(n\ge 2)$ 个点的树，每次我们选择一个编号最小的叶子节点删掉，然后将其相邻节点的编号加入到序列中，直到剩下两个点为止，这样构成的序列，就叫这棵树的 Prüfer 序列。
性质
Prüfer 序列构建了一个有标号无根树到序列的双射，后面会讲如何通过另方求另一方。
而且任意一个值域为 $n$ 长度为 $n-2$ 的序列都对应了一棵生成树，这让 Prüfer 序列在解决无根树相关的计数问题非常好用。
从度数的角度看 Prüfer 序列，可以发现，Prüfer 序列中的点实际上表现的是度数 $-1$ 的过程。
例如 ：Prüfer 序列是 $1,2,3$ ，那么表示在删除第一个叶子时，$1$ 号点度数减 $1$ ，接下来同理。
最后，所有度数为 $1$ 的点被删除，只剩下了 $n$ 和另外一个度数为 $1$ 的点。
综上，我们可以得到下面这个结论。
结论 1 ：每个点在 Prüfer 序列中的出现次数为度数$-1$ 。
转化
无根树转 Prüfer 序列
从小到大搜索每一个点，直到 Prüfer 序列中已经有 $n-2$ 个数字，设搜索到 $p$ 号点：
- 假如 $p$ 号点不是叶子，继续搜。
- 假如 $p$ 号点是叶子，删除，如果新增了一个叶子节点且编号小于 $p$ ，显然这个叶子节点编号最小，接着删，直到删了 $n-2$ 个点或者编号 $>p$ 。
时间复杂度：$O(n)$ 。
Prüfer 序列转无根树
首先，根据 Prüfer 序列可以算出每个点的度数，然后按照 Prüfer 序列，每次取出编号最小的叶子节点和 Prüfer 序列当前位置连边，然后给 Prüfer 序列当前位置度数 $-1$ ，不断重复，直到最后，就只会剩两个度数为 $1$ 的节点，连起来即可。
时间复杂度：$O(n\log{n})$ 。
练习
- $n$ 个点的有标号无根树有多少个：$n^{n-2}$ 个。
- 假设每个点的度数已知，设为 $d_i$ ，求满足这个度数限制的有标号无根树的数量：$\binom{n-2}{d_1-1,d_2-1,…,d_n-1}$ 。
Cayley 公式：给定 $m(m\ge 2)$ 个连通块，每个连通块的大小是 $s_i$ ，且 $\sum\limits_{i=1}^m=n$ ，那么用 $m-1$ 条边把这 $m$ 个联通块联通起来的方案数为 $(\prod\limits_{i=1}^m s_i)n^{m-2}$ 。
证明
证明 1 ：考虑 $m$ 个点的树的 $Prüfer$ 序列，不妨设为 $p$ 序列，由于 $Prüfer$ 序列实际上代表了一种连边方式，所以我们只需要计算 $n-1$ 条边能够有多少种连法就行了，那么对于这个 $Prüfer$ 序列能够代表的方案数，通过计算为：$(\prod_{i=1}^m s_i)(\prod_{i=1}^{m-2} s_{p_i})$ 。又 Prüfer 序列 $m-2$ 个位置都可以填 $1-m$ ，所以显然，总方案数为 $(\prod\limits_{i=1}^m s_i)n^{m-2}$ 。
证明 2 ：代数证明（来自oiwiki）
考虑每个连通块的度数为 $d_i$ ，显然，只要 $d_i>0,\sum\limits_{i=1}^md_i=2m-2$ ，就能算是一个合法的度数序列。
所以这样子的方案数为：$\binom{m-2}{d_1-1,d_2-1,…,d_m-1}\prod{s_i^{d_i}}$ 。
由多元二项式定理：$(x_1+x_2+…+x_p)^k=\sum\limits_{a_1,a_2,…,a_p\ge 0,a_1+a_2+…+a_p=k}\binom{k}{a_1,a_2,…,a_p}\prod\limits_{i=1}^px_i^{a_i}$ 。
那么 $\sum\limits_{d_i>0,d_1+…+d_m=2m-2}\binom{m-2}{d_1-1,d_2-1,…,d_m-1}\prod\limits_{i=1}^m{s_i^{d_i}}$ ，令 $e_i=d_i-1$ 可以得到：$\sum\limits_{e_i\ge 0,e_1+…+e_m=m-2}\binom{m-2}{e_1,e_2,…,e_m}\prod\limits_{i=1}^m{s_i^{e_i+1}}=n^{m-2}\prod\limits_{i=1}^ms_i$
证毕。