prufer 序列是一种无根树的序列，对于一个 (n) 个点的树，其 prufer 序列的长度为 (n-2)。
prufer 序列和原树之间都可以唯一地相互转化。
构造
构造 prufer 序列分为如下的步骤：
- 找到一个编号最小的度数为 (1) 的点；
- 将与这个点相邻的点的编号加入 prufer 序列的后面；
- 删除这个点；
- 重复上述步骤，知道原树只剩下 (2) 个点，这两个点之间应该有一条边。
还原
令集合 (V = {1, 2, cdots, n})。
-
取出 prufer 序列最前面的点 (x)；
-
找到 (V) 序列中最小的没有在现在的 prufer 序列中出现过的点 (y)；
-
将 (x) 和 (y) 连边并从集合 (V) 中删除 (y)，从 (prufer) 序列中删除最前面的 (x)。
-
重复上述步骤，直到 prufer 序列被遍历完；此时 (V) 中应该还剩下两个点，给它们连边。
考虑这样还原为什么是对的。
每一次被配对的 (y)，应该是原树在删掉 prufer 序列 (x) 之前的点后的叶子。
那么根据之前的构造步骤，这个 (y) 必须满足：
- 是个叶子，这个条件等价于没有在后面的 prufer 序列中出现。
- 之前没有被选过；
- 编号最小。
于是就有了上面的选 (y) 的条件了。
性质
性质 1
一棵无根树的每个点的度数等于这个点在 prufer 序列中的出现次数 (+1)。
这个结论很显然，由构造过程就可以发现。
性质 2
一棵有标号的无根树的数量为 (n^{n-2})。
可以发现我们的还原过程中，prufer 序列本身没有任何限制。
只要是长度为 (n-2)，值域为 (n) 的序列，都可以还原成一棵树。
性质 3
如果限定了每个点的度数，编号为 (i) 的点的度数为 (a_i)，那么方案为 (frac{(n-2)!}{prodlimits_{i=1}^n a_i-1})。
显然必须有 (sumlimits_{i=1}^n a_i = 2(n-1) = 2n - 2)，于是 (sumlimits_{i=1}^n a_i - 1 = n - 2)，所以相当于是做一个可以重复元素的全排列。