lp4430 猴子打架/Prufer 序列

额…看起来是一道找规律题,实际上还是挺有门道的。

题目的题意就是,求 n 个点的点、边均有标号的生成树个数。

n 个点的无根有标号生成树个数,根据某个叫做 Cayley 的古老定理, 值是:

当然,由于边有标号,所以这里的值还要乘上一个​。

问题是 Cayley 定理要如何证明。

一种比较简易的方法是一种被称为 Prufer 序列的构造。通过这种构造,我们发现,有且仅有 ​ 种不同的方法来构造一棵有标号无根树。

这个序列是如何构造的呢?

我们考虑递归地构造这个序列。对于当前的树,我们选其中的编号最小的叶子节点,将它的相邻点——显然是唯一的——加入序列,然后删掉这个叶子节点。

这样,我们就得到了一个序列。这个序列中每一个点的出现次数是它的入度 -1 。

由此我们可以构造出这个序列。

通过 Prufer 序列,我们无损地将一棵有标号无根树的信息压缩成了一个序列。

那么要怎么把 Prufer 序列还原为一棵有标号无根树呢?我们有一种系统的方法。

首先选择一个数,这个数既不在已有的树中,也不在当前的序列中,并且它最小。那么,我们就可以确定,这个数便是我们当前要处理的叶子节点。

然后,我们把这个节点与当前枚举到的序列中的点连边。这等于是逆向还原 Prufer 序列的生成过程。

是不是对于任何一个值域在 n 范围内的长度为 n-2 的序列都可以还原成一棵树呢?

假设我们当前正在处理第 i 个节点,序列中剩下 k 种数,那么已经被作为叶子节点,已经连接或即将被连接的节点数则是 n-k 个。每处理一个节点,至多会消耗掉一个叶子节点的配额。因此已经连接的节点至多为 i-1 个。又因为 n-2-i+1 必须大于等于 k ,所以叶子节点必然不会不够。

那么完成最后一步以后叶子节点会不会有剩呢?每个节点会被连接的次数正好是它在序列中出现的次数 +1 ,这也就意味着,总度数恰好是 2n-2 ,由于每一条边都无向,所以构成的正好是一张 n-1 条边的图。

最后的疑问就是构成的图是不是连通的。考虑到 n-1 条边的连通图与 n-1 条边的无环图是等价的,我们不妨尝试证明它无环。

我们称,一个点被作为「要处理的叶子节点」来连接的过程为「向上连边」,那么每个点的向上连边操作会且仅会发生一次。在这种情况下,环会出现,只有可能是「向上连边」的时候连向的是自己所在的连通块内的点。

然而,向上连边的目标,一定还在 Prufer 序列中,而可以向上连边的点,一定不在 Prufer 序列中。我们于是证明了这张图无环。

既然这张 n-1 条边的图无环,那么它一定连通。

由此,我们发现,每一棵树都能唯一对应地生成一个 Prufer 序列,并且每一个 Prufer 序列都能生成一棵树。

这样我们就证明了 Prufer 序列和有标号无根树的一一对应性。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=9999991;

inline ll pw(ll A,ll X){
	ll RT=1;
	while(X){
		if(X&1){
			RT*=A;
			RT%=MOD;
		}
		A*=A;A%=MOD;X>>=1;
	}
	return RT;
}
int n;
void init(){
	scanf("%d",&n);
	ll fac=1;
	for(int i=1;i<n;++i){
		fac=fac*i%MOD;
	}
	printf("%lld\n",pw(n,n-2)*fac%MOD);
}
int main(){
	init();
	return 0;
}

发表评论

电子邮件地址不会被公开。