Prufer 序列学习笔记

Prufer 序列是一种常用于解决树的计数问题的序列，它是一种无根树到序列的双射。

定义

一棵无根树的 Prufer 序列是这样定义的：

• 删掉叶子节点（度为 $1$）中编号最小的节点，把与它相连的节点的编号加入序列的末尾

• 重复这个操作直到剩余节点数为 $2$

Prufer 序列的构造过程可以看作是一层一层地把树扒开（

很明显，Prufer 序列和无根树互为双射，一棵 $n$ 个节点的无根树的 Prufer 序列长度为 $n-2$。

运用

• 一棵 $n$ 个节点的无根树共有 $n^{n-2}$ 种形态，因为 Prufer 序列的每一位都可以任选；

• 一棵 $n$ 个节点的有根树共有 $n^{n-1}$ 种形态；

• 某个节点 $u$ 的度数是它在 Prufer 序列中的出现次数 $+1$；

• 一棵 $m$ 个节点，第 $i$ 个节点有 $a_i$ 种连接方式的无根树共有 $(\sum\limits_{i=1}^m a_i)^{m-2}\prod\limits_{i=1}^m a_i$ 种；

  证明如下：

  考虑生成出来的树的长度为 $m-2$ 的 Prufer 序列，显然每个位置可以任选。$i$ 的度即为它在 Prufer 序列中出现的次数 $+1$，所以 $i$ 的贡献是 $a_i^{\text{出现次数}+1}$，把 $+1$ 拉出来，变成 $(\prod a_i^{\text{出现次数}})(\prod a_i)$。

  所有情况下的 $\prod a_i^{\text{出现次数}}$ 之和显然和 $(\sum a_i)^{m-2}$ 是等价的，得证。

• 一棵 $m$ 个节点，第 $i$ 个节点有 $a_i$ 个接口（只能用一次）的无根树共有 $\dbinom{\sum\limits_{i=1}^ma_i-m}{m-2}(m-2)!\prod\limits_{i=1}^m a_i$ 种；

• $n\times m$ 的完全二分图的无根生成树共有 $n^{m-1}m^{n-1}$ 种，第 $i$ 个点有 $a_i$ 种连接方式或接口的方案数同理；

  证明如下：

  考虑每个点被删掉时会在序列中加入一个另一部的点，但是最后剩两个点时会停止。

  被删掉的点的顺序没关系，因为是按编号删去的。

例题

• 板子：CF156D Clues

• 板子：P2290 [HNOI2004]树的计数

• 板子，但是下降幂：ARC106F

  设 $cnt_i$ 为 $i$ 在 Prufer 序列中的出现次数，那么答案为：

  $\begin{aligned} &\prod d_i^{\underline{cnt_i+1}}\\ &=\left(\prod d_i\right)\prod (d_i-1)^{\underline{cnt_i}}\\ &=\left(\prod d_i\right)\left(\sum d_i-1\right)^{\underline{n-2}}\\ \end{aligned}$

• 二分图板子：【2024NOI模拟赛24】通道