树的prufer编码

2018-04-28

lolifamily

算法

树的prufer编码

注意：

高精度！

实现树的 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。

输入

输出

1
2

说明/提示

两棵树分别为 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!$ 可分解为一个数 $\times 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

注意：