图论Prüfer 序列目录0%参考资料简介例题Prüfer 序列概述概述Prüfer 序列建立 n 个点的带标号无根树与长度 n-2 的序列之间的双射：反复删去编号最小的叶子并记录它唯一的邻居，就得到序列；反过来也能由序列唯一还原出树。由这个双射可以直接推出凯莱公式——n 个点的带标号树共有 n 的 n-2 次方棵，还能对每个点度数受限的树进行计数，因为一个点在序列里出现的次数恰等于它的度数减一。文末附一道模板例题。参考资料 Prüfer 序列 - OI Wiki 简介 Prüfer 序列 是 nnn 个点的带标号无根树与长度 n−2n-2n−2 的序列之间的双射：每次删去编号最小的叶子并记录其唯一邻居，得到序列；反之可唯一还原。由它立得凯莱公式——带标号树共 nn−2n^{n-2}nn−2 棵，并能对度数受限的树计数。 例题 题面code洛谷 P6086 【模板】Prüfer(Prufer) 序列在带标号无根树与其 Prüfer 序列之间相互转换，并输出结果序列的加权异或和。