简介

prufer序列 是一种无根树的编码表示方法,类似于 hash

一棵 $n$ 个节点的无根树唯一对应一串长为 $n-2$ 的 prufer编码

所以一个 $n$ 阶完全图的生成树个数为 $n^{n-2}$

无根树prufer序列

定义无根树中度数为 $1$ 的节点是叶子节点

找到编号最小的叶子并删除,序列中添加与之相连的节点编号,重复执行直到只剩下 $2$ 个节点

prufer序列无根树

我们设点集为 ${1,2,\cdots,n}$

然后我们每次找到点集中没有出现在 prufer序列 中的最小的点(这一定是这个时刻删除的叶子节点)

然后再取出 prufer序列 中的第一个元素,两个点建边,在将两个点在分别删除

性质

prufer序列 中某个编号出现的次数就是这个编号节点的度数减一

例题

【HNOI 2004】树的计数

一个有 $n$ 个结点的树,设它的结点分别为 $v_1, v_2, \cdots, v_n$,已知第 $i$ 个结点 $v_i$ 的度数为 $d_i$,问满足这样的条件的不同的树有多少棵

给定 $n,d_1, d_2,\cdots, d_n$,编程需要输出满足 $d(v_i)=d_i$ 的树的个数

其中 $1 \le n \le 150$,输入数据保证满足条件的树不超过 $10^{17}$ 个

prufer序列 的性质可以得知,度数为 $i$ 的点在序列中出现 $i-1$ 次

那么就相当于给定一些元素,元素 $i$ 有 $d_i-1$ 个,求可重集的全排列个数,也就是:

$$
\frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!}
$$

【HNOI 2008】明明的烦恼

给出标号为 $1$ 到 $n$ 的点,以及某些点最终的度数

允许在任意两点间连线,求可产生多少棵度数满足要求的树

其中 $1 \le n \le 1000$

假设有 $k$ 个点的度数被限定了,分别是 $d_1,d_2,\cdots,d_k$,记 $s=\sum_{i=1}^{k}(d_i-1)$,那么剩余的点有 $n-k$ 个,总方案数为:
$$
(n-k)^{n-2-s}{n-2 \choose s}\frac{s!}{\prod_{i=1}^{k}(d_i-1)}
$$

【bzoj 1430】小猴打架

一开始森林里面有 $n$ 只互不相识的小猴子,它们经常打架,但打架的双方都必须不是好朋友

每次打完架后,打架的双方以及它们的好朋友就会互相认识,成为好朋友

经过 $n-1$ 次打架之后,整个森林的小猴都会成为好朋友

现在的问题是,总共有多少种不同的打架过程

其中 $1 \le n \le 10^6$

对于任意一棵树,对答案的贡献都是 $(n-1)!$,因为连边顺序可以任意

那么树的个数就是 $n^{n-2}$,所以答案就是 $n^{n-2}(n-1)!$

【51nod 1806】wangyurzee的树

求有多少个 $n$ 个节点的无根树,使得满足 $m$ 个给定的条件,每个条件诸如限定点 $u_i$ 的度数不能为 $d_i$

其中 $1 \le n \le 10^6, 0 \le m \le 17, 1 \le u_i \le n, 1 \le d_i \le n-1$

考虑容斥,每次枚举一个条件子集,限定强制要求这个子集不满足条件

假设限定的是 $d_1,d_2,\cdots,d_k$,记 $s=\sum_{i=1}^{k}(d_i-1)$,那么方案数为:

$$
(n-k)^{n-2-s}{n-2 \choose s}\frac{s!}{\prod_{i=1}^{k}(d_i-1)!}
$$

【GDSOI2017 第二轮模拟】树

有 $n$ 个点,它们从 $1$ 到 $n$ 进行标号,第 $i$ 个点的限制为度数不能超过 $a_i$

现在对于每个 $s (1 \le s \le n)$,问从这 $n$ 个点中选出一些点组成大小为 $s$ 的有标号无根树的方案数

其中 $1 \le n \le 100$

设 $f_{i,j,k}$ 表示考虑完了 $1 \sim i$,且选择了 $j$ 个点,且 prufer序列 填完了前 $k$ 个位置的方案数,则有:

$$
f_{i,j,k}=f_{i-1,j,k}+\sum_{t=1}^{a_i} {k \choose t-1} f_{i-1,j-1,k-(t-1)}
$$

参考资料

【无根树的计数——prufer序列】hec0411