Prufer序列相关

最近做到一些题，用到了Prufer序列，挺有用的，在这里学习一下。

描述

Prufer数列是无根树的一种数列，通过一个Prufer序列可以唯一表示一棵顶点带标号的无根树，点数为n的树转化来的Prufer数列长度为n-2，它有很多的性质

求法

一种生成Prufer序列的方法是迭代删点，直到原图仅剩两个点。对于一棵顶点已经经过编号的树T，顶点的编号为{1,2,…,n}，在第i步时，移去所有叶子节点（度为1的顶点）中标号最小的顶点和相连的边，并把与它相邻的点的编号加入Prufer序列中，重复以上步骤直到原图仅剩2个顶点
可以发现，对于一棵带标号的无根树的Prufer序列是唯一的

转回

现在有一个prufer序列，如何推回原本的无根树呢？
考虑对于初始的点集1~n，根据生成的方式可以得知，第一个删掉的点在之后一定不会出现，而未出现的点都是一开始度数为1的，所以说，第一个被删除的点的编号是所有开始未出现的点中编号最小的，删除一个点后就可以转化为子问题了，直到昨晚n-2次，此时对未被删除的剩下两个点连上一条边，就把原树构造出来了
容易发现，一个Prufer序列对应着唯一的一个带标号的无根树

作用

比如，现在有一棵$n$个节点的树，给定每个节点的度数，求树可能形态数，答案为：(n−2)!∏i=1n(di−1)!\frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}∏i=1n​(di​−1)!(n−2)!​
然后如果有些节点如果不确定度数也可以做
例题：[HNOI2008][bzoj1005]明明的烦恼（咕咕咕咕咕）

待upd

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！