模板及讲解

定义

$Prufer$数列是无根树的一种数列。在组合数学中，$Prufer$数列由有一个对于顶点标过号的树转化来的数列，点数为n的树转化来的$Prufer$数列长度为$n-2$。它可以通过简单的迭代方法计算出来。

将树转换为$prufer$序列

总体的思路是迭代删点，直到原图中只剩下两个点。对于一棵树$T$,我们已经将每次找到树中标号最小的叶子结点，将这个叶子结点以及与它相邻的边删去，将与叶子结点相连的点加入数列中。重复上一步，直到原图中只剩下两个点。

将$prufer$序列转换为树

将结点列一个集合$A=(1，2，\dots ,n)$在集合$A$中找出一个没有在$prufer$数列中出现的最小的值，将这个值在集合$A$中删去，并且将这个值和$prufer$数列中的第一个数连起一条边，并划去$prufer$数列中的第一个值，重复此步，直到集合$A$中只剩下两个数字，将以这两个数字为编号的结点连起一条边。

应用

1、无根树和$prufer$数列是唯一对应的
2、一个点的度数为$d$，那么这个点在$prufer$序列中的出现次数为$d−1$, bzoj 1211
3、一个完全图$K_n$有$n^{n-2}$棵生成树，换句话说$n$个节点的带标号的无根树有$n^{n-2}$个。(Cayley公式, bzoj 1430)

对3的证明，显然一个$n-2$长的$prufer$序列对应唯一一棵无根树，那么所有$prufer$序列的个数是$n^{n-2}$