prufer序列

ps.之前刷题太快，现在考试碰到这种已经忘记了。

定义：一种将带编号的树用唯一的一个整数序列表示的方法，即可以把一颗带标号的 n 个节点的树序列化为一个长度为 n−2 的唯一的序列。

也就相当于完全图的生成树与数列之间的双射。

构造方法：每次选择一个编号最小的叶节点并删掉它，并把其父亲节点加入序列。

重复 n−2 次如上操作，此时树上只剩 2 个节点，算法结束。

首先找到编号最小的，度数为 1 的叶子节点，指针 p 指向它，将它删除。

如果删除了这个节点后，它的父亲节点的编号比它小并且父亲节点的度数也变成了1，那么此时这个节点一定是编号最小的叶子节点，删除它即可，同时不断往上删除，注意在这个过程中 p 并不进行移动。

否则，继续找到下一个编号最小的叶子节点即可。

每条边在删度数的时候最多被访问一次，而指针最多遍历每个结点一次，因此复杂度是 O(n) 的。

性质：1.构造完prufer序列后剩下两个节点其中一个是点n

2.每个节点出现次数是度数-1

3.没有出现在prufer里的节点就是叶子节点

Cayley公式：有n个节点的完全图有 \(n^{n-2}\) 棵生成树。

因为任意一个长度为n-2的值域[1,n]的整数序列都可以通过prufer序列双射对应一个生成树。