====== Prufer 序列 ======

Prufer 序列构造了一个 $n \geq 2$ 个结点的无根树，与一个长度为 $n - 2$、值域在 $[1, n]$ 的序列之间的双射。



===== 从无根树到 Prufer 序列 =====

每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。重复 $n - 2$ 次后就只剩下两个结点，算法结束。

显然剩下结点中一定有 $n$。



===== 从 Prufer 序列到无根树 =====

根据 Prufer 序列的性质，我们可以得到原树上每个点的度数。然后你也可以得到度数最小的叶结点编号，而这个结点一定与 Prufer 序列的第一个数连接。然后我们同时删掉这两个结点的度数。

讲到这里也许你已经知道该怎么做了。每次我们选择一个度数为 $1$ 的最小的结点编号，与当前枚举到的 Prufer 序列的点连接，然后同时减掉两个点的度。到最后我们剩下两个度数为 $1$ 的点，其中一个是结点 $n$。



===== Prufer 序列的性质 =====

  - $n$ 个节点的无根树的 Prufer 序列长度为 $n-2$。
  - 在构造完 Prufer 序列后原树中会剩下两个结点，其中一个一定是编号最大的点；
  - 度为 $d$ 的节点会出现 $d-1$ 次，没有出现的就是叶结点。

我们知道 Prufer 序列可以得到 Cayley 公式，即带标号无根树的个数是 $n^{n-2}$ 的，因为对应的 Prufer 序列就有这么多种。同时由于 Prufer 序列还体现了树中度数的关系，因此也可以用来做一些度数有限制的生成树计数。例如，设已知节点的度数组 $d_1, d_2, \ldots, d_n$，则其无根树的数量为

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

证明只要考虑“度为 $d$ 的节点会出现 $d-1$ 次”这个性质即可。另一个带度数限制的例子可以参考 [[http://wiki.buaaacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:multi2020-nowcoder-7#i_-valuable-forests | Valuable Forests]] 这道题的树形 DP 解法。



===== 参考资料 =====

  - [[https://oi-wiki.org/graph/prufer/#_4 | Prufer 序列 - OI Wiki]]