prüfer 序列学习笔记

GI录像机 · 2024-01-08 16:12:05 · 算法·理论

算法部分

prüfer 序列可以将一个有标号的由 n 个结点组成的树唯一对应成一个由 n-2 个数组成的序列。prüfer 序列也会唯一对应一个树。

prüfer 序列的构建

钦定 n 为树的根结点。因为这是无根树，所以没有影响。

每次选择编号最小的叶子结点并删掉它，再把它的父亲的编号加入序列中。重复此操作，直到树上只有两个点为止。显然，这两个点中必有一个是编号最大的点 n。

为什么是两个点呢？假设我们再进行一次操作，那么进入序列的必然是 n。这是没有意义的操作。而如果我们进行了这次操作，末尾不为 n 的 prüfer 序列将失去对应一个树的优秀性质。

prüfer 序列的还原

可以看得出来，经过此操作，每个树都对应了一个 prüfer 序列。如果我们能从 prüfer 序列还原出树，那么也就证明了树和 prüfer 序列是一一对应的。

prüfer 序列有一个性质：树上每个点的度数等于在 prüfer 序列上出现的次数加 1。

这个很好想，因为一个点的度数只来源于连向父亲的边和连向儿子的边。每删掉一个儿子，这个点就会出现在 prüfer 序列上一次。众所周知，除了根结点外树上每个点都有且只有一个父亲，所以其出现次数加 1 等于度数。

那么作为根结点的 n 呢？它可没有父亲。但是别忘了，我们并没有删去所有 n 之外的点，还保留了一个 n 的儿子。因此，在 prüfer 序列中出现的 n 的个数仅为它的儿子数减 1，即它的度数减 1。

有了这个性质，我们就可以得知没有出现在 prüfer 序列上的点，一定是叶子结点。

这样我们轻易就能得到树上最小的叶子结点的编号，就是没有在 prüfer 序列上出现的点。我们将这个叶子结点与 prüfer 序列上的第一个数连边，然后删除这个点和 prüfer 序列上的第一个数。如果将编号大于该叶子结点的编号减一，我们就得到了一个长度为 n-3 的 prüfer 序列，对应一个大小为 n-1 的树。因此可以使用同样的方法重复操作，再把最后剩下的点连向 n，就可以得到原树。

线性构造 prüfer 序列

对一个树构造 prüfer 序列，很显然可以使用堆做到 O(n\log n) 的复杂度，但其实有更优的做法。

维护一个下标 p，初始值为最小的叶结点编号。重复以下操作：

删除编号为 p 的结点，并检查是否使其父亲成为叶结点。
设其父亲的编号为 x。先将 x 加入序列。若 x 成为了新的叶子结点，判断其与 p 的大小关系。若 x<p，则立即删除 x，然后重复判断 x 的父亲；否则不管。
使 p 自增，直到 p 指向一个叶子结点为止。

因为每条边最多被访问一次（在删点的时候访问父亲），指针最多遍历每个点一次，所以复杂度是 O(n) 的。

这有点像可删堆的操作，可以结合理解。

线性还原树

和线性构造 prüfer 序列的方法类似，用同样的方法寻找编号最小的叶结点删除即可。

Cayley 公式

完全图 K_n 有 n^{n-2} 个生成树。

用 prüfer 序列证明很简单。因为每个长度为 n-2，值域在 [1,n] 的序列都可以对应一个大小为 n 的树，所以一共有 n^{n-2} 个生成树。

例题：

CF156D

简要题意

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

思路：

把每个连通块缩成一个点，显然缩点之后使图连通等价于建立一个大小为 k 的生成树。

这就解决了？不，远远没有。对于大小为 s_i 的连通块 i 连出的每一条边，都可以在这 s_i 个点内任选一个作为该边连接的点。设缩点后连通块 i 的度数为 d_i，则确定连边方式的之后的答案为 \prod^k_{i=1} s_i^{d_i}。

如果给定 d_i，不同的连边方式有多少种呢？回忆起我们前面提到的性质：树上每个点的度数等于在 prüfer 序列上出现的次数加 1。

既然给定了每个点的度数，那么每个点在序列上出现的次数也就定了，即 d_i-1。更进一步，整个 prüfer 序列中每个数的出现次数也就定了。也就是说整个 prüfer 序列仅仅在做位置上的变换。

一个长度为 k-2，数两两不同的数列变换位置能生成多少个不同的数列？显然是 (k-2)!。但 prüfer 序列的数字是有相同的。显然这种数内部的排列是没有意义的，因为无论如何排列在这个位置上的数依然是这个数，没有本质区别。因此我们只需将答案分别除去所有的 (d_i-1)!。

所以不同的 prüfer 序列数量就是 \frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdots(d_k-1)!}。

现在我们得出了一个结论：对于确定的 d_i，方案数为 \frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdots(d_k-1)!}\cdot\prod^k_{i=1} s_i^{d_i}。

边数之和的两倍为所有点度数之和（因为每个边会连向两个点），所以 \sum^k_{i=1}d_i=2(k-1)，整理得 \sum^k_{i=1}(d_i-1)=k-2。

由于要枚举 d_i，所以答案为 \sum_{d_i-1\geq0,\sum^k_{i=1}(d_i-1)=k-2}\frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdots(d_k-1)!}\cdot\prod^k_{i=1} s_i^{d_i}

看起来很不友好，对吧？但我们有多元二项式定理：

这两个柿子是不是很像？可以换元一下，令 $c_i=d_i-1$，$x_i=s_i$，$m=k$，$p=k-2$，发现只有最后的 $\prod^m_{i=1}x_i^{c_i}$ 不一样，应该是 $\prod^m_{i=1}x_i^{c_i+1}$，即 $\prod^m_{i=1}x_i^{c_i}\cdot \prod^m_{i=1}x_i$。因此套用此定理，可得原柿子等于 $(s_1+s_2+\cdots+s_k)^{k-2}\cdot\prod^m_{i=1}x_i$。因为所有连通块大小之和为 $n$，所以原柿子就是 $n^{k-2}\cdot\prod^m_{i=1}x_i$。 ## P2624 ### 简要题意：现有 $n$ 个点，求把这 $n$ 个点连成一个树的方案数。但第 $i$ 个点限制度数为 $d_i$，若 $d_i=-1$ 则该点无限制。 #### 思路：设有限制的点有 $k$ 个。对于有限制的点，设 $s=\sum (d_i-1)$。那么在 prüfer 序列中，就要拿出 $s$ 个位置去填放这些数。从长为 $n-2$ 的序列中取出 $s$ 个位置的方案数为 $C^s_{n-2}$。还是那个问题。一个长度为 $s$，数可能的数列变换位置能生成多少个不同的数列？同上一道题，是 $\frac{s!}{\prod(d_i-1)!}$。 prüfer 序列上剩下 $n-2-s$ 个位置没有填，可以填剩下的 $n-k$ 个点。因此剩下的选择就是 $(n-2-s)^{n-k}$。故答案为 $C^s_{n-2}\cdot\frac{s!}{\prod(d_i-1)!}\cdot(n-2-s)^{n-k}$。 ## bzoj4766 ### 简要题意：有一个完全二分图 $(X,Y,E)$。两部分 $X$ 和 $Y$ 分别有 $n1$ 和 $n2$ 个顶点。求生成树个数。 ### 思路：可以对应到 prüfer 序列上。如果我们删去一个 $X$ 中的点，那么进入 prüfer 序列的一定是 $Y$ 中的点，因为只有不在同一部分的点有连边。最后剩下的两个点也一定是一个 $X$ 中的点，一个 $Y$ 中的点。所以我们一共会删除 $X$ 中的点 $n1-1$ 个，$Y$ 中的点 $n2-1$ 个。而每个删除的 $X$ 点都可以选择一个 $Y$ 中点作为父亲，进入 prüfer 序列的点就有 $n2$ 种选择；同理，删除的 $Y$ 点可以选择 $n1$ 个 $X$ 点进入 prüfer 序列中。故而答案为 $n1^{n2-1}\cdot n2^{n1-1}$。