Prufer序列
Prufer序列是有标号无根树的一种映射。
$n$个节点的有标号无根树可以与一个长度为$n-2$的Prufer序列唯一对应。
从树到Prufer序列的转换：
- 设$f$为空序列
- 如果当前树上多于两个节点，假设当前标号最小的叶子节点为$x$，与$x$相连的节点标号为$y$，将$x$从树上删掉，将$y$加入$f$末端
- 重复2.直到树上只有两个节点
从Prufer序列到树的转换：
- 找到当前不在$f$中且还没使用过的最小的元素$x$
- $x$与当前$f$的第一个元素连边，把$x$标记为已使用过
- 删除$f$的第一个元素，如果$f$非空，重复1.
- 最终有两个元素没有使用过，将他们连边
Prufer序列长度为$n-2$，每个元素的取值范围是$[1,n]$。
这种唯一对应的关系说明$n$个点的有标号无根树一共有$n^{n-2}$种。