发现标题字打错了,然后改不了标题就重新发了一遍。
简介
prufer 序列可以把一个结点带标号的树用 个值域为 的整数表示。
一棵树对应唯一的 prufer 序列,一个 prufer 序列对应唯一的树,二者为双射关系。
对树建立 prufer 序列
每次找到编号最小的 叶子结点,把这个结点的父亲放入 prufer 序列的末尾,然后删掉这个叶子。重复 次。
算法实现
显然可以用堆实现,也可以线性构造。
维护一个 表示最小的叶子结点,重复以下操作
- 删除 。
- 如果父亲成为了叶子,且父亲的编号 ,删除父亲。不断重复 2 操作。
- 自增直到找到新的叶子结点。
分析正确性,删除一个点新成为叶子的只会是父亲,如果父亲的编号 ,那么父亲是现在最小的叶子;如果父亲的编号 ,那么父亲会在之后被找到。
只会遍历 到 ,而删除的时候每条边只会遍历一次,所以复杂度为 。
代码
1 | for(int k=1;k<n;k++) |
对 prufer 序列建立树
prufer 序列里的点的出现次数 就是结点在树上的度数。
每次找到编号最小的 度数为 的结点,与当前枚举的 prufer 序列的结点连边,然后这两个点度数 。
最后剩下两个度数为 的点,其中一个是 ,将这两个点连边。
算法实现
同理可以用堆实现,当然也可以线性构造。
现在 prufer 序列末尾添加结点 ,维护一个 表示最小的 度数为 的结点,重复以下操作
- 删除 。
- 如果父亲度数变为 ,且父亲的编号 ,删除父亲。不断重复 2 操作。
- 自增直到找到新的度数为 的点。
代码
1 | for(int k=1;k<=n;k++) |
Cayley 公式
完全图 有 棵生成树
证明可以使用 prufer 序列,purfer 序列有 种(长度为 每个位置可以是 中的一个数),purfer 序列和生成树
一一对应,所以有 棵生成树。
类似的:
- 个点的无根树有 种
- 个点的有根树有 种
- 个点的无根树,每个点的度数为 ,有 种,也为 (sum 为还剩下的位置)
图连通方案数
一个 个点 条边的带标号无向图有 个连通块。我们希望添加 条边使得整个图连通。求方案数。
感性理解一下,如果把每个连通块看成点,总方案数为 。因为每个位置上填 都有意义。
然后每个连通块还要和上一个连边,联通块内的每一个点都可能拿出来连,所以总方案数是 。
详细证明之后再说吧。
相关题目
建 prufer 和建树:【模板】Prüfer 序列
Cayley 公式相关:[HNOI2004] 树的计数
图连通方案数:CF156D Clues