Prufer编码
Prufer编码
prufer编码与树一一对应，可以用于计数树的种类。
先说明如何将一颗树转换为prufer编码。如果树中还剩余多于两个顶点，那么就选择度为1的编号最小的顶点，并将其从树中移除，同时将树中原本唯一与它相连的顶点加入到编码序列尾部。重复该操作直到跳出条件满足。
下面说明将prufer编码转换为树的步骤。维护一个顶点集合X，初始的时候其中包含了所有不出现在prufer编码序列中的顶点。首先从X中移除编号最小的顶点v，并从prufer编码序列中移除最前面的顶点u，在u、v之间连接一条边，如果u不再出现在prufer编码序列中，就将u加入到X中。重复上面的操作直到prufer序列为空。
这里说明一下树转prufer和prufer转树是互逆操作。初始时X集合中仅包含叶子结点，而叶子结点中编号最小的那个结点v一定是在树转prufer时第一个被选择的顶点，之后该顶点的相邻顶点u作为prufer序列的第一个元素。因此我们在prufer转树的第一步就将这两个结点连边。之后的prufer序列对应删除了v后的新树，这里可以用归纳原理证明还原的正确性。
由于树和prufer编码一一对应，我们可以容易发现n个顶点可以组成的树的数目等于$n^{n-2}$。
现在说明prufer编码的性质。
- 如果一个顶点在原树中的度数为d，那么在prufer编码中包含d-1个该顶点。
提供两道用到prufer编码技术的题目：LUOGU2624，Codeforces1109D。