Skip to main content

Prüfer 序列

Summary

Prüfer 序列建立 n 个点的带标号无根树与长度 n-2 的序列之间的双射：反复删去编号最小的叶子并记录它唯一的邻居，就得到序列；反过来也能由序列唯一还原出树。由这个双射可以直接推出凯莱公式——n 个点的带标号树共有 n 的 n-2 次方棵，还能对每个点度数受限的树进行计数，因为一个点在序列里出现的次数恰等于它的度数减一。文末附一道模板例题。

参考资料​

简介​

Prüfer 序列 是 nn 个点的带标号无根树与长度 n−2n-2 的序列之间的双射：每次删去编号最小的叶子并记录其唯一邻居，得到序列；反之可唯一还原。由它立得凯莱公式——带标号树共 nn−2n^{n-2} 棵，并能对度数受限的树计数。

例题​

洛谷 P6086 【模板】Prüfer(Prufer) 序列

在带标号无根树与其 Prüfer 序列之间相互转换，并输出结果序列的加权异或和。