关于 Purfer 序列

随便抄点什么玩意当笔记用

purfer 序列是啥就不说了

构造方法

不断选取树上编号最小的叶子删除,并加入序列的末尾。

还原方法

\mathbb{A} = \{ 1, 2, 3, \cdots , n \} 以及 purfer 序列 \{ a_i \}

\mathbb{A} 是所谓的度数序列,初始值全是 1 ,然后 Purfer 序列里每个数字都对 \mathbb{A} 1 的贡献。

顺次取出 Purfer  的首个元素,并在 \mathbb{A} 中选择最小的度数为 1 的元素与之连边。

之后这两个元素的度数均 -1

最后 \mathbb{A} 中应该还剩两个元素,将它们连边。

一个性质

因为要进入 purfer 序列就必须要成为一个叶子,那么也就是说 (对于原数的非叶节点) 每个节点在 purfer 序列中出现了它的度数 -1 这么多次 (有一个临点要当父亲) 

(HNOI2008)