树的prufer编码

2018-04-28

lolifamily

算法

树的prufer编码

注意：

高精度！

实现树的 Prufer 编码

Prufer 编码是用另外一种形式来描述一棵树，这棵树是无根树，它可以和无根树之间形成一一对应关系。

已知树，如何求 Prufer 编码？

首先选这棵树叶子中编号最小的点，将这个点删除，并且把它的邻接点加入一个数组中，例如第一个删除的节点为 $1$ ，并且把 $5$ 加入数组中。

删除节点后形成一棵新的树，再在新树中删除最小的节点，并且把邻接点加入数组中，这样重复以上步骤，直到树中最后剩余两个点的时候终止操作。

这时候数组中的便是 Prufer 编码。

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

将 Prufer 编码还原为一棵树

假如 Prufer 编码为 $(𝑎 1, 𝑎 2, 𝑎 3, \dots 𝑎 𝑛 - 2)$ 在上述数组中，在数组最后加入 $𝑛$ 这个值，这样便形成了数组中包含 $𝑛 - 1$ 个节点，例如上述为 $(5, 5, 4, 4, 4, 6, 8)$ 。

然后取不在数组中的最小值为 $𝑏 1$ ，则 $𝑏 1$ 与 $𝑎 1$ 是邻接点，在数组中删除 $𝑎 1$ ，再在剩下的数中选取不为 $𝑏 1$ ，且不在数组中的最小值为 $𝑏 2$ ，则 $𝑏 2$ 与 $𝑎 2$ 是邻接点，这样依次循环下去直到结束，这样便形成了一棵树。

Prufer 编码的性质

Cayley 定理：不同的 $𝑛$ 节点标号树的数量为 $𝑛 𝑛 - 2$ 。

任意一棵 $𝑛$ 节点的树都可唯一的用长度为 $𝑛 - 2$ 的 Prufer 编码表示。

度数为 $𝑚$ 的节点的序号在 Prufer 编码中出现的次数为 $𝑚 - 1$ 。

例题：[HNOI2008] 明明的烦恼

题目描述

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

输入格式

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

输出格式

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

输入

输出

1
2

说明 / 提示

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

题目分析

该题需要将树转化为 prufer 编码：

$𝑛$ 为树的节点数， $𝑑 𝑖$ 为各节点的度数， $𝑚$ 为无限制度数的节点数。

则有度数的点出现次数为：

$𝑡 𝑜 𝑡 = 𝑛 \sum 𝑖 = 1 (𝑑 𝑖 - 1)$

因为度数为 $𝑑 𝑖$ 的点出现了 $𝑑 𝑖 - 1$ 次。

所以要求在 $𝑛 - 2$ 大小的数组中插入 $𝑡 𝑜 𝑡$ 个序号，共有 $𝐶 𝑡 𝑜 𝑡 𝑛 - 2$ 种插法。

在 $𝑡 𝑜 𝑡$ 个序号排列中，插第一个节点的方法有 $𝐶 𝑑 1 - 1 𝑡 𝑜 𝑡$ 种插法。

插第二个节点的方法有 $𝐶 𝑑 2 - 1 𝑡 𝑜 𝑡$ 种插法。

……

另外还有 $𝑚$ 个节点无度数限制，所以它们可任意排列在剩余的 $𝑛 - 2 - 𝑡 𝑜 𝑡$ 的空间中，排列方法总数为 $𝑚 𝑛 - 2 - 𝑡 𝑜 𝑡$ 。

根据乘法原理：

𝑎 𝑛 𝑠 = 𝐶 𝑡 𝑜 𝑡 𝑛 - 2 \cdot 𝐶 𝑑 1 - 1 𝑡 𝑜 𝑡 \cdot 𝐶 𝑑 2 - 1 𝑡 𝑜 𝑡 - (𝑑 1 - 1) \dots 𝐶 𝑑 𝑛 - 1 𝑑 𝑛 - 1 \cdot 𝑚 𝑛 - 2 - 𝑡 𝑜 𝑡 = (𝑛 - 2)! (𝑛 - 2 - 𝑡 𝑜 𝑡)! \cdot 𝑡 𝑜 𝑡! \cdot 𝑡 𝑜 𝑡! (𝑑 1 - 1)! \cdot (𝑡 𝑜 𝑡 - 𝑑 1 + 1)! \dots (𝑑 𝑛 - 1)! (𝑑 𝑛 - 1)! \cdot 0! \cdot 𝑚 𝑛 - 2 - 𝑡 𝑜 𝑡 = (𝑛 - 2)! \cdot 𝑚 𝑛 - 2 - 𝑡 𝑜 𝑡 (𝑛 - 2 - 𝑡 𝑜 𝑡)! \cdot (𝑑 1 - 1)! \cdot (𝑑 2 - 1)! \dots (𝑑 𝑛 - 1)!

然后就要高精度了…… 但高精度除法太麻烦了，显而易见的排列组合一定是整数，所以可以进行质因数分解，再做一下相加减。

关于 $𝑛!$ 质因数分解有两种方法，第一种暴力分解，这里着重讲第二种。

若 $𝑝$ 为素数，则 $𝑛!$ 可分解为一个数 $\times 𝑝 𝑥$ ，其中

𝑥 = ⌊ 𝑛 𝑝 ⌋ + ⌊ 𝑛 𝑝 2 ⌋ + \dots + ⌊ 𝑛 𝑝 𝑡 ⌋

且 $𝑝 𝑡 < 𝑛$

∴ 𝑛! = 𝑝 𝑥 1 1 \cdot 𝑝 𝑥 2 2 \cdot 𝑝 𝑥 3 3 \dots 𝑝 𝑥 𝑚 𝑚 (𝑝 𝑚 < 𝑛)

代码详见 Code

注意：