fer

引入 首先这是个啥玩意呢？Prüfer 序列可以将带标号的 \(n\) 个节点的树用一个序列表示。可以理解为完全图生成树与Prüfer 序列构建了双射。 建立 每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。重复 \(n-2\) 次后就只剩下两个结点，算法结束。 ......

用于解决**带标号**的生成树计数问题，一般用于计数问题。 ### 建立 Prüfer 序列 重复下列操作 $n-2$ 次，得到长度为 $n-2$ 的 Prüfer 序列。 1. 取出编号最小的叶子节点 $x$，将与 $x$ 相连的节点加入 Prüfer 序列中。 2. 将 $x$ 和与 $x$ 相 ......

由于本人过菜，故写文备忘。 参考资料： # $\color{Violet}\mathsf{Prüfer}\ 序列$ Prüfer 序列常用于组合计数问题上。 Prüfer 序列可以将一个带标号 $n$ 个结点的树用 $[1,n]$ 中的 $n-2$ 个整数表示。你也可以把它理解为完全图的生成树与数列 ......

## 入门 长度为 $n - 2$ 的双射，可以构建起数列和无根树的关系。 构建方法 ： - 取 $\text index$ 最小的叶子，向 Prüfer 加入其父亲，并删除其本身。 大概是非常容易写 $n \log n$ 的小根堆即可。 摘自 OI-wiki : ```cpp vector> ad ......

## 简介 Prüfer 序列（以下为方便写作 “prufer 序列”）可以将一个带标号的 $n$ 个结点的树用 $[1,n]$ 中的 $n-2$ 个整数表示，也可以理解为完全图的生成树与数列之间的双射。 ## 定义 prufer 序列的简历过程为：选取树中所有叶子节点中编号最小的，将其的父节点加入 ......

[toc] ## Prüfer 序列 Prüfer 序列是将一颗 $n$ 个有标号的点用一个长度为 $n-2$ 的序列的表示的方法。 对于一颗有标号的树，会存在唯一一个 Prüfer 序列与之对应。一个 Prüfer 序列也只会对应一颗树。 ### 将一颗树转化为 Prüfer 序列 首先对于所有的 ......