P6086 【模板】Prüfer 序列
Prüfer 序列可以将树的计数问题转化为序列，而且可以和树实现 \(O(n)\) 互相转换。
Prüfer 序列定义：对于一颗无根树，每次选择一个编号最小的叶子节点（定义为度为 \(1\) 的点），记录它的父节点，直到最后只剩下两个点（因为节点 \(n\) 一定不会被删，是个常量，没有必要记录）。
二者是唯一对应的。
转换方法
Prüfer 转树
显然可以带 \(\log\) 转换，但是有 \(O(n)\) 的方法。
考虑维护一个变量 \(j\) 表示现在已知的最小的编号的叶子节点，逐步增加，遇到第一个叶子节点时：
- 加入序列。
- 查看其父亲的编号是否小于它且成为叶子节点，如果小于加入其父亲，不断往上迭代。
由于每次循环 Prüfer 序列长度都会增加 \(1\)，所以复杂度显然。
树转 Prüfer
类似做法。
除 \(n\) 外，每个节点的度为它在 Prüfer序列中出现的次数。
同上，遇到情况时的区别：
- 更新父亲。
- 同上2.。