prufer序列

本文主要是介绍prufer序列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

prufer序列，一种把有标号树用唯一的整数序列表示。它可以将一个带标号\(n\)个结点的树用\(n-2\)个整数表示。

建立方法非常简单：每次找到无根树上编号最小的一个叶子，删掉它并记录它的父亲编号，重复\(n-2\)次，直到只剩下两个节点结束。

我们可以以线性的复杂度使一棵树在树和prufer序列之间相互转换。（以下树的形态为其父亲序列，即序列中\(f_i\)为节点\(i\)在\(n\)为根时的父亲）

1. 从树到prufer序列

当然我们可以\(O(n^2)\)暴力找每个最小的叶子删掉然后记录父亲。当然仅限于可以，能不能过两码事。

当然我们还可以开个堆保存每个节点的度数，复杂度\(O(n\log n)\)。

但是更优秀的方法是拿指针扫一遍。指针从小到大扫，找到第一个指针扫到的叶子并记录它的父亲，父亲度数\(-1\)。如果这一操作产生了新的比当前节点小的叶子，则继续加入序列中。

void father_to_prufer(){
	for(int i=1;i<n;i++){
		scanf("%lld",&f[i]);
		d[f[i]]++;//记录每个父亲的权值 
	}
	for(int i=1,j=1;i<=n-2;i++,j++){
		while(d[j])j++;//指针往上跳 
		p[i]=f[j];
		while(i<=n-2&&p[i]<j&&!--d[p[i]]){//顺序不要搞错 最后再自减 
			p[i+1]=f[p[i]];i++;//有减到0的进入序列 
		}
	}
}

这个做法显然正确：当产生新的叶子时：

1. 如果叶子比当前节点大，直接不管。
2. 反之它一定是最小的叶子，直接更新。

树转成prufer序列就这样。

2. 从头prufer序列到树

和上一个的逻辑差不多，就是有个要注意的点，最后多放一个根要不然根转不完。

void ptf(){
	for(int i=1;i<=n-2;i++){
		scanf("%lld",&p[i]);d[p[i]]++;
	}
	p[n-1]=n;//注意要记录一下根节点 
	for(int i=1,j=1;i<n;i++,j++){
		while(d[j])++j; 
		f[j]=p[i];
		while(i<n&&p[i]<j&&!--d[p[i]]){
			f[p[i]]=p[i+1];i++;
		}
	}
}

好了上面的东西都是纯扯淡，应该没人考你这个。引用一句话：

显然你不会想不开拿这玩意儿去维护树结构。这玩意儿常用组合计数问题上。
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $——OI WiKi

然后是这玩意真正的应用：计数。

举个例子：凯莱定理：\(n\)个点的完全图有\(n^{n-2}\)棵生成树。

证明：显然\(K_n\)的prufer序列有\(n-2\)个数，每个数都可以从\([1,n]\)中选，总共\(n^{n-2}\)种。

另一个小结论：
对于给定度数为\(d_{1\sim n}\)的一棵无根树共有$\frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!} $种情况。证明很简单，prufer序列上跑重排列就行了。

这篇关于prufer序列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！