prufer 序列

发现标题字打错了，然后改不了标题就重新发了一遍。

简介

prufer 序列可以把一个结点带标号的树用 $n-2$ 个值域为 $[1,n]$ 的整数表示。

一棵树对应唯一的 prufer 序列，一个 prufer 序列对应唯一的树，二者为双射关系。

对树建立 prufer 序列

每次找到编号最小的 叶子结点，把这个结点的父亲放入 prufer 序列的末尾，然后删掉这个叶子。重复 $n-2$ 次。

算法实现

显然可以用堆实现，也可以线性构造。

维护一个 $p$ 表示最小的叶子结点，重复以下操作

1. 删除 $p$。
2. 如果父亲成为了叶子，且父亲的编号 $<p$，删除父亲。不断重复 2 操作。
3. $p$ 自增直到找到新的叶子结点。

分析正确性，删除一个点新成为叶子的只会是父亲，如果父亲的编号 $<p$，那么父亲是现在最小的叶子；如果父亲的编号 $>p$，那么父亲会在之后被找到。

$p$ 只会遍历 $1$ 到 $n$，而删除的时候每条边只会遍历一次，所以复杂度为 $O(n)$。

代码

1
2
3
4
5
6
7
8
9
10
11

for(int k=1;k<n;k++)
    d[fa[k]]++;
for(int k=1,j=1;k<=n-2;k++,j++){
    while(d[j])
        j++;
    p[k] = fa[j];
    while(k<=n-2&&!(--d[p[k]])&&p[k]<j){
        p[k+1] = fa[p[k]];
        k++;
    }
}

对 prufer 序列建立树

prufer 序列里的点的出现次数 $+1$ 就是结点在树上的度数。

每次找到编号最小的 度数为 $1$ 的结点，与当前枚举的 prufer 序列的结点连边，然后这两个点度数 $-1$。

最后剩下两个度数为 $1$ 的点，其中一个是 $n$，将这两个点连边。

算法实现

同理可以用堆实现，当然也可以线性构造。

现在 prufer 序列末尾添加结点 $n$，维护一个 $p$ 表示最小的 度数为 $1$ 的结点，重复以下操作

1. 删除 $p$。
2. 如果父亲度数变为 $1$ ，且父亲的编号 $<p$，删除父亲。不断重复 2 操作。
3. $p$ 自增直到找到新的度数为 $1$ 的点。

代码

1
2
3
4
5
6
7
8
9
10
11
12

for(int k=1;k<=n;k++)
    d[p[k]]++;
p[n-1] = n;
for(int k=1,j=1;k<n;k++,j++){
    while(d[j])
        j++;
    fa[j] = p[k];
    while(k<n&&!(--d[p[k]])&&p[k]<j){
        fa[p[k]] = p[k+1];
        k++;
    }
}

Cayley 公式

完全图 $K_n$ 有 $n^{n-2}$ 棵生成树

证明可以使用 prufer 序列，purfer 序列有 $n^{n-2}$ 种（长度为 $n-2$ 每个位置可以是 $[1,n]$ 中的一个数），purfer 序列和生成树
一一对应，所以有 $n^{n-2}$ 棵生成树。

类似的：

• $n$ 个点的无根树有 $n^{n-2}$ 种
• $n$ 个点的有根树有 $n \times n^{n-2}$ 种
• $n$ 个点的无根树，每个点的度数为 $d_i$，有 $\frac{(n-2)!}{\prod^{n}_{i-1}(d_i-1)!}$ 种，也为 $\prod^{n}_{i-1}C_{d_i-1}^{sum}$（sum 为还剩下的位置）

图连通方案数

一个 $n$ 个点 $m$ 条边的带标号无向图有 $k$ 个连通块。我们希望添加 $k-1$ 条边使得整个图连通。求方案数。

感性理解一下，如果把每个连通块看成点，总方案数为 $n^{k-2}$。因为每个位置上填 $[1,n]$ 都有意义。

然后每个连通块还要和上一个连边，联通块内的每一个点都可能拿出来连，所以总方案数是 $n^{k-2}\times \prod^{k}_{i=1}s_i$。

详细证明之后再说吧。

相关题目

建 prufer 和建树：【模板】Prüfer 序列

Cayley 公式相关：[HNOI2004] 树的计数

图连通方案数：CF156D Clues