Prufer 序列

算法简介

一种带编号生成树与数列之间的双射，主要用于解决组合计数问题。

Prufer 序列的性质

对一棵 $n$ 个结点的带标号树，考虑每次取编号最小的叶子结点，将其删除。

然后将与其相邻的结点加入 $\text{Prufer}$ 序列，直到只剩下两个结点。

显然这样操作得到的序列具有唯一性，删除到最后余下的节点中一定包含编号为 $n$ 的结点。

接下来考虑得到的 $\text{Prufer}$ 序列的性质。显然有 $\text{Prufer}$ 序列长度为 $n-2$，任意一个结点出现次数为其度数减一。

对一个长度为 $n-2$ 且只含 $1\sim n$ 的数列，每次找到标号最小的且不在序列中出现的点。

将它与当前序列的第一个点连一条边，然后删去序列的第一个点。易知这样得到的图唯一且最终图为树。

发现该操作对应之前寻找叶子节点删去并将其相邻节点加入序列的操作。

于是可以证明一棵 $n$ 个结点的带标号树与一个任意长度为 $n-2$ 且只含 $1\sim n$ 的数列构成双射。

根据上述结论，不难得到 $\text{Cayley}$ 公式：完全图 $K_n$ 有 $n^{n-2}$ 棵生成树。

Prufer 的编码与解码

洛谷p6086

考虑如何根据树建立 $\text{Prufer}$ 序列，同时如何根据 $\text{Prufer}$ 序列还原树。

首先不难利用优先队列可以 $O(n\log n)$ 实现，接下来考虑线性算法。

先考虑建立 $\text{Prufer}$ 序列的过程，不妨先将无根树设置为以 $n$ 为根的有根树，因为 $n$ 一定不会被删除。

用指针维护当前编号最小的叶子节点。每次将其删除，然后如果与其相邻变为叶子节点，则考虑该结点的编号。

则如果其标号小于删除节点，则立刻将该结点删除，因为删除节点是最小叶子节点，所以该结点一定是新的最小叶子节点。

否则继续寻找下一个编号最小的叶子节点，于是可以 $O(n)$ 建立 $\text{Prufer}$ 序列。

根据 $\text{Prufer}$ 序列建树过程也类似，具体细节参考代码。

int f[MAXN],prufer[MAXN];
void prufer_encode(int n){
	static int deg[MAXN];
	_rep(i,1,n)deg[i]=0;
	_for(i,1,n)deg[f[i]]++;
	int pos=1;
	_rep(i,1,n-2){
		while(deg[pos])pos++;
		prufer[i]=f[pos];
		while(i<n-2&&!--deg[prufer[i]]&&prufer[i]<pos)
		prufer[i+1]=f[prufer[i]],i++;
		pos++;
	}
}
void prufer_decode(int n){
	static int deg[MAXN];
	_rep(i,1,n)deg[i]=0;
	_rep(i,1,n-2)deg[prufer[i]]++;
	prufer[n-1]=n;
	int pos=1;
	_for(i,1,n){
		while(deg[pos])pos++;
		f[pos]=prufer[i];
		while(i<n&&!--deg[prufer[i]]&&prufer[i]<pos)
		f[prufer[i]]=prufer[i+1],i++;
		pos++;
	}
}

算法练习

习题一

CF156D

题意

给定一个 $n$ 个点 $m$ 条边的带标号无向图，求添加最少的边使图连通的方案数。

题解

假设图中有 $k$ 个连通块，每个连通块中的点的个数为 $s_i$。先进行将每个连通块缩点，于是最终方案肯定为一个生成树。

然后设每个点度数为 $d_i$，根据 $\text{Prufer}$ 序列性质，满足条件的生成树有 $\cfrac{(k-2)!}{\prod_{i=1}^k(d_i-1)!}$ 棵。

而每棵生成树对应的方案数为 $\prod_{i=1}^k s_i^{d_i}$。设 $c_i=d_i-1$，答案为

$$\sum_{\sum d_i=2k-2}\cfrac{(k-2)!\prod_{i=1}^k s_i^{d_i}}{\prod_{i=1}^k(d_i-1)!}=\prod_{i=1}^k s_i\sum_{\sum c_i=k-2}\cfrac{(k-2)!\prod_{i=1}^k s_i^{c_i}}{\prod_{i=1}^kc_i!}=\left(\sum_{i=1}^k s_i\right)^{k-2}\prod_{i=1}^k s_i=n^{k-2}\prod_{i=1}^k s_i$$

查看代码

const int MAXN=1e5+5;
int p[MAXN],sz[MAXN],mod;
int quick_pow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return ans;
}
int Find(int x){return x==p[x]?x:p[x]=Find(p[x]);}
int link(int a,int b){
	int x=Find(a),y=Find(b);
	if(x!=y){
		if(sz[x]>sz[y])swap(x,y);
		p[x]=y,sz[y]+=sz[x];
	}
}
int main()
{
	int n=read_int(),m=read_int(),k=0,ans=1,u,v;
	mod=read_int();
	_rep(i,1,n)p[i]=i,sz[i]=1;
	while(m--){
		u=read_int(),v=read_int();
		link(u,v);
	}
	_rep(i,1,n){
		if(i==Find(i)){
			k++;
			ans=1LL*ans*sz[i]%mod;
		}
	}
	enter(k==1?1%mod:1LL*ans*quick_pow(n,k-2)%mod);
	return 0;
}

习题二

牛客暑期多校(第七场) I 题

题意

定义森林的权值为每个点度数的平方和，问所有 $n$ 个点构成的带标号森林的权值和。

题解

设 $n$ 个点构成的带标号树的个数为 $t_{1,n}$，所有 $n$ 个点构成的带标号树的权值和为 $t_{2,n}$。

$n$ 个点构成的带标号森林的个数为 $f_{1,n}$，所有 $n$ 个点构成的带标号森林的权值和为 $f_{2,n}$。

考虑如何递推 $f_{2,n}$。$f_{2,n}$ 可以理解为从其他 $n-1$ 个点中选 $i$ 个与 $n$ 构成一棵树，其余点任意。

$$f_{2,n}=\sum_{i=0}^{n-1} {n-1\choose i}\left(t_{2,i+1}f_{1,n-1-i}+f_{2,n-1-i}t_{1,i+1}\right)$$

于是问题转化为求 $t_{1,n},t_{2,n},f_{1,n}$。

首先根据 $\text{Cayley}$ 公式易知 $t_{1,n}=n^{n-2}$。

$f_{1,n}$ 可以理解为从其他 $n-1$ 个点中选 $i$ 个与 $n$ 构成一棵树，其余点任意。

$$f_{1,n}={n-1\choose i}t_{1,i+1}f_{1,n-1-i}$$

接下来考虑递推 $t_{2,n}$。由于每个点地位等价，可以先计算出每个点在所有方案中的贡献和，最后乘以 $n$。

于是考虑枚举每个点的度数 $i$，根据 $\text{Prufer}$ 序列性质，有该结点恰好出现 $i-1$ 次，其他节点任意。

$$t_{2,n}=n\sum_{i=1}^ni^2 {n-2\choose i-1}n^{n-2-i+1}$$

于是可以 $O(n^2)$ 解决上述问题。