prufer序列是一个定义在无根树上的东西。
构造方法是:每次选一个编号最小的叶子结点,把他的父亲的编号加入到序列的最后。然后删掉这个叶节点。直到最后只剩下两个节点,此时得到的序列就是prufer序列。
这个构造可以用优先队列做到 $O(n\log n)$。
至于如何用prufer序列反推出树,我还有点没看懂怎么 $O(n\log n)$,以后看懂了再来填坑吧。
prufer序列的一些性质:
- 一棵 $n$ 个点的无根树prufer序列长度为 $n-2$。
- 无根树和prufer序列一一对应,一个无根树唯一对应一个prufer序列,一个prufer序列唯一对应一个无根树。
- 一个在树中度数为 $d$ 的点在prufer序列中出现了恰好 $d-1$ 次。
那么就能推出一些常用结论:
- $n$ 个点的无根树(带标号)有 $n^{n-2}$ 棵。(prufer序列长度为 $n-2$,每个位置都可以随便选 $1$ 到 $n$ 的数)
- $n$ 个点的度数为 $d_1,d_2\cdots,d_n$ 的无根树个数为 $\dfrac{(n-2)!}{\prod(d_i-1)!}$。因为 $i$ 在prufer序列中会出现 $d_i-1$ 次,最后计算出来就是这个式子。
一些例题:
洛谷2290 [HNOI2004]树的计数(题解待填充)
洛谷2624 [HNOI2008]明明的烦恼(题解待填充)
洛谷5219 无聊的难水题 I(题解待填充)