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.。