Prufer序
一个Prufer数列和一个带编号的无根树是一一对应的
树->Prufer序
每次找这棵树中编号最小的叶子节点，将与这个点相连的点加入Prufer序，去掉这个点以及相连的边。重复这个操作直到剩下两个点。
Prufer序->树
设点集$ V={1,2,…,n} $，每次在$V$中找出最小的未在Prufer序中出现过的数，然后在$V$中删除，与Prufer序中的第一个数相连，Prufer序中的第一个数删除。重复这个操作直到$|V|=2$（Prufer序为空），最后将$V$中的两个点相连。
证明
这个感性理解一下感觉很有道理的
注意到，如果一个节点A不是叶子节点，那么它至少有两条边；但在上述过程结束后，整个图只剩下一条边，因此节点A的至少一个相邻节点被去掉过，节点A的编号将会在这棵树对应的Prüfer编码中出现。反过来，在Prüfer编码中出现过的数字显然不可能是这棵树（初始时）的叶子。于是我们看到，没有在Prüfer编码中出现过的数字恰好就是这棵树（初始时）的叶子节点。找出没有出现过的数字中最小的那一个（比如④），它就是与Prüfer编码中第一个数所标识的节点（比如③）相邻的叶子。接下来，我们递归地考虑后面n-3位编码（别忘了编码总长是n-2）：找出除④以外不在后n-3位编码中的最小的数（左图的例子中是⑦），将它连接到整个编码的第2个数所对应的节点上（例子中还是③）。再接下来，找出除④和⑦以外后n-4位编码中最小的不被包含的数，做同样的处理……依次把③⑧②⑤⑥与编码中第3、4、5、6、7位所表示的节点相连。最后，我们还有①和⑨没处理过，直接把它们俩连接起来就行了。由于没处理过的节点数总比剩下的编码长度大2，因此我们总能找到一个最小的没在剩余编码中出现的数，算法总能进行下去。这样，任何一个Prüfer编码都唯一地对应了一棵无根树，有多少个n-2位的Prüfer编码就有多少个带标号的无根树。
——摘自Matrix67
性质
- 一棵n个节点的无根树唯一地对应了一个长度为n-2的数列，数列中的每个数都在1到n的范围内。
- Prufer序列中某个编号出现的次数就等于这个编号的节点在无根树中的度数-1。
- 设无根树每个点的度数为$D_i$，则$\sum_{i=1}^n(D_i-1)=n-2$（这好像是废话，，，因为$\sum_{i=1}^nD_i=2(n-1)$。。。
Cayley公式
Cayley公式
一个完全图$K_n$有$n^{n-2}$棵生成树
证明
由Prufer可知，一个Prufer数列和一个带编号的无根树是一一对应的，那么这个公式也很显然了。因为$n$个节点的无根树的Prufer序长度为$n-2$，序列中每个值取值为${1,2,3,…,n}$，因此不同的Prufer序有$n^{n-2}$个，因此生成树也有这么多个。
推广
n个节点的度依次为$D_1,D_2,…,D_n$的无根树共有$\frac{(n-2)!}{(D_1-1)!(D_2-1)!\cdots(D_n-1)!}$个。
例题
BZOJ1005
LOJ6395