树的prufer编码 | loli's oi blog

注意：

高精度！

实现树的Prufer编码

Prufer编码是用另外一种形式来描述一棵树，这棵树是无根树，它可以和无根树之间形成一一对应关系。已知树，如何求Prufer编码？
首先选这棵树叶子中编号最小的点，将这个点删除，并且把它的邻接点加入一个数组中，例如第一个删除的节点为 $1$ ，并且把 $5$ 加入数组中。删除节点后形成一棵新的树，再在新树中删除最小的节点，并且把邻接点加入数组中，这样重复以上步骤，直到树中最后剩余两个点的时候终止操作。这时候数组中的便是Prufer编码。

例如上图是一棵无根树，这棵树的Prufer编码为 $(5, 5, 4, 4, 4, 6)$ 。

将Prufer编码还原为一棵树

假如Prufer编码为 $(a_{1}, a_{2}, a_{3}, \dots a_{n - 2})$ 在上述数组中，在数组最后加入 $n$ 这个值，这样便形成了数组中包含 $n - 1$ 个节点，例如上述为 $(5, 5, 4, 4, 4, 6, 8)$ 。
然后取不在数组中的最小值为 $b_{1}$ ，则 $b_{1}$ 与 $a_{1}$ 是邻接点，在数组中删除 $a_{1}$ ，再在剩下的数中选取不为 $b_{1}$ ，且不在数组中的最小值为 $b_{2}$ ，则 $b_{2}$ 与 $a_{2}$ 是邻接点，这样依次循环下去直到结束，这样便形成了一棵树。

Prufer编码的性质

Cayley 定理：不同的 $n$ 节点标号树的数量为 $n^{n - 2}$ 。
任意一棵 $n$ 节点的树都可唯一的用长度为 $n - 2$ 的Prufer编码表示；度数为 $m$ 的节点的序号在Prufer编码中出现的次数为 $m - 1$ ；

例题：[HNOI2008]明明的烦恼

题目描述

自从明明学了树的结构，就对奇怪的树产生了兴趣……给出标号为 $1$ 到 $N$ 的点，以及某些点最终的度数，允许在任意两点间连线，可产生多少棵度数满足要求的树？

输入格式

第一行为 $N (0 < N \leq 1000)$ ，接下来 $N$ 行，第 $i + 1$ 行给出第 $i$ 个节点的度数 $D_{i}$ ，如果对度数不要求，则输入-1

输出格式

一个整数,表示不同的满足要求的树的个数，无解输出0

输入

3
1
-1
-1

输出

说明/提示

两棵树分别为1-2-3;1-3-2

题目分析

该题需要将树转化为prufer编码：
$n$ 为树的节点数， $d_{i}$ 为各节点的度数， $m$ 为无限制度数的节点数。
则有度数的点出现次数为： $\begin{array}{r} t o t = \sum_{i = 1}^{n} (d_{i} - 1) \end{array}$ ，因为度数为 $d_{i}$ 的点出现了 $d_{i} - 1$ 次
所以要求在 $n - 2$ 大小的数组中插入 $t o t$ 个序号，共有 $\begin{array}{r} C_{n - 2}^{t o t} \end{array}$ 种插法；
在 $t o t$ 个序号排列中，插第一个节点的方法有 $\begin{array}{r} C_{t o t}^{d_{1} - 1} \end{array}$ 种插法；
插第二个节点的方法有 $\begin{array}{r} C_{t o t}^{d_{2} - 1} \end{array}$ 种插法；
…………
另外还有 $m$ 个节点无度数限制，所以它们可任意排列在剩余的 $n - 2 - t o t$ 的空间中，排列方法总数为 $\begin{array}{r} m^{n - 2 - t o t} \end{array}$
根据乘法原理：

\begin{aligned} a n s & = C_{n - 2}^{t o t} \cdot C_{t o t}^{d_{1} - 1} \cdot C_{t o t - (d_{1} - 1)}^{d_{2} - 1} \dots C_{d_{n} - 1}^{d_{n} - 1} \cdot m^{n - 2 - t o t} \\ = \frac{(n - 2)!}{(n - 2 - t o t)! \cdot t o t!} \cdot \frac{t o t!}{(d_{1} - 1)! \cdot (t o t - d_{1} + 1)!} \dots \frac{(d_{n} - 1)!}{(d_{n} - 1)! \cdot 0!} \cdot m^{n - 2 - t o t} \\ = \frac{(n - 2)! \cdot m^{n - 2 - t o t}}{(n - 2 - t o t)! \cdot (d_{1} - 1)! \cdot (d_{2} - 1)! \dots (d_{n} - 1)!} \end{aligned}

然后就要高精度了……但高精度除法太麻烦了，显而易见的排列组合一定是整数，所以可以进行质因数分解，再做一下相加减。
关于 $n!$ 质因数分解有两种方法，第一种暴力分解，这里着重讲第二种。
若 $p$ 为素数，则 $n!$ 可分解为一个数 $\cdot p^{x}$ ，其中 $\begin{array}{r} x = ⌊ \frac{n}{p} ⌋ + ⌊ \frac{n}{p^{2}} ⌋ + \dots + ⌊ \frac{n}{p^{t}} ⌋ \end{array}$ 且 $\begin{array}{r} p^{t} < n \end{array}$
所以 $\begin{array}{r} n! = p_{1}^{x_{1}} \cdot p_{2}^{x_{2}} \cdot p_{3}^{x_{3}} \dots p_{m}^{x_{m}} (p_{m} < n) \end{array}$
代码详见Code

模板题

讲义下载

树的prufer编码.pdf