Prufer 序列的定义
\(\rm Prufer\) 序列可以将一颗结点数为 \(n\) 的有标号无根树用一个长度为 \(n-2\)，值域为 \([1,n]\) 的数列唯一表示，即有标号无根树和 \(\rm Prufer\) 序列呈双射关系。
具体来说，有标号无根树的构建方式如下：
- 选择一个编号最小的叶子节点，并将其删除。
- 将这个叶子节点所连接的点的编号加入 \(\rm Prufer\) 序列中。
- 重复以上步骤 \(n-2\) 次，直到树上只剩下 \(2\) 个点。
这是某一颗点数为 \(n\) 的有标号无根树的 \(\rm Prufer\) 序列的构造过程：
快速求解 Prufer 序列
由其过程，显然有一个使用堆优化的 \(\Theta(n\log n)\) 做法，但 \(\rm Prufer\) 序列其实可以线性构造。
记录所有点的度数和一个指针 \(p\) 指向编号最小的叶子节点，进行以下操作：
- 将 \(p\) 指向的结点删除，检查是否出现了新的叶结点。
- 如果产生了新的叶结点，记其编号为 \(x\)。 若 \(x\gt p\)，则不做任何操作，否则将其删除，并检查删除 \(x\) 以后是否出现了新的叶结点，重复这一步操作直到没有产生新的叶结点或新产生的结点编号大于 \(p\)。
- 让 \(p\) 自增直到遇见下一个叶结点为止。
- 重复以上操作直到结点数为 \(2\) 可以得到这棵树的 \(\rm Prufer\) 序列。
可以发现，在算法流程中，每条边只在其连接的外层结点被删除时被遍历过一次，并且 \(p\) 单调递增，树中的节点数单调递减，所以每个点也只被遍历过一次。
总时间复杂度 \(\Theta(n)\)。
快速还原 Prufer 序列
显然还是有一个堆优化的 \(\Theta(n\log n)\) 做法。
从前到后枚举 \(\rm Prufer\) 序列中的每一个数，维护不在序列中的结点编号的最小值。显然不在序列中的是叶子节点，并且其最小值为最后一个加入的，于是将其与当前枚举的序列中的数连边。连边后若序列中已没有枚举的这个数，那么将其踢出序列作为新的叶子结点。
考虑以与之前构造 \(\rm Prufer\) 序列相同的方法构造线性做法。
记一个指针 \(p\) 指向不在序列中的最小结点，如果将其连向序列中枚举的位置，并将枚举的位置删除。序列中没有这个结点了，那么如果被删除的结点比 \(p\) 小，直接将其与现在序列中枚举的数连边后将其删除，重复操作。如果这个结点的值大于 \(p\)，那么不用管它，在后面它一定会被枚举到。
显然，这种算法的时间复杂度为 \(\Theta(n)\)。
Prufer 序列的应用
Cayley 公式
完全图 \(K_{n}\) 有 \(n^{n-2}\) 颗生成树。
证明方法很多，其中最简单的应该是利用 \(\rm Prufer\) 序列。
考虑到任何一个长度为 \(n-2\) 的 \(\rm Prufer\) 序列唯一对应一颗大小为 \(n\) 的有标号无根树，于是考虑计算长度为 \(n-2\) 的 \(\rm Prufer\) 序列的数量，又因为其值域为 \([1,n]\)，故总方案数为 \(n^{n-2}\)。
限定度数的有标号无根树计数
求有 \(n\) 个结点，且第 \(i\) 个结点的度数为 \(d_{i}\) 的有标号无根树的数量。
考虑到一个点的度数为其在 \(\rm Prufer\) 序列中出现次数 \(+1\)，于是对于一个度数为 \(d_{i}\) 的点，其在 \(\rm Prufer\) 序列中的出现次数应为 \(d_{i}-1\)，故存在这样的有标号无根树当且仅当 \(\sum_{i=1}^{n} d_{i}-1=n-2\)，并且这样的树的数量为：
\[ \dbinom{n-2}{d_1-1,d_2-1,\cdots ,d_n-1}=\frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots (d_n-1)!} \]