\(\color{Violet}\mathsf{Prüfer}\ 序列\)

Prüfer 序列常用于组合计数问题上。

Prüfer 序列可以将一个带标号 \(n\) 个结点的树用 \([1,n]\) 中的 \(n-2\) 个整数表示。你也可以把它理解为完全图的生成树与数列之间的双射。

\(\color{red}一\) 从树到序列

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

线性构造法

用指针 \(p\) 指向编号最小的度数为 0 的节点。先删掉 \(p\)，获得 \(x\)，为度数被更新的节点。如果 \(x\) 的度数不变为 0，即没有产生新的度数为 0 的节点，那么将 \(p\) 自增，直到找到度数为 0 的节点，此时 \(p\) 指向的就是下一个要删掉的节点。如果 \(x\) 的度数变为 0，我们 check 一下 \(x\) 与 \(p\) 的大小：

若 \(x<p\)，意味着 \(p\) 在自增环节扫过 \(x\)，但当时由于 \(x\) 的度数限制，没有被删掉，如今 \(x\) 应当被删掉了，我们删掉 \(x\)，继续检索 \(x\) 是否致使产生新的 0 度节点，若产生了，并且产生的节点编号 \(<p\)，循环执行删除，如果否，退出循环。
注意在这个过程中不改动 p，因为 p 可以在上述操作后仍保持原有 1 到 p-1 间不存在 0 度节点的性质。

若 \(x>p\)，意味着虽然 \(x\) 的度数变成 0 了，但是 \(p\) 并未在自增环节扫过 \(x\)，也就是说 \(x\) 的编号顺序不一定满足条件。反正之后会扫到 \(x\)，我们当前直接跳过。

循环执行直到未被删除的节点只剩 2 个，结束。

//此代码摘取自https://github.com/cp-algorithms/cp-algorithms/blob/master/src/graph/pruefer_code.md
  vector<int> code(n - 2);
  int leaf = ptr;
  for (int i = 0; i < n - 2; i++) {
    int next = parent[leaf];
    code[i] = next;
    if (--degree[next] == 1 && next < ptr) {
      leaf = next;
    } else {
      ptr++;
      while (degree[ptr] != 1) ptr++;
      leaf = ptr;
    }
  }

复杂度分析：除了删除节点和 \(p\) 自增的均摊 \(O(n)\) 之外其余操作均 \(O(1)\)。总复杂度 \(O(n)\)。

\(\color{red}二\) 从序列到树

刚开始你有一个点集 \(V=\{v|1\le v\le n\}\)，这个点集是所有没连边的节点的集合。

循环执行以下操作：

拿出 Prüfer 序列最靠前的数，拿出点集中不在当前 Prüfer 序列中的编号最小的点。在两个点之间连一条边。

同样可以线性时间解决。

\(\color{red}三\) 性质

Prüfer 序列与无根树为双射关系。
度数为 \(d_i\) 的节点会在序列中出现 \(d_i−1\) 次。
节点 \(n\) 一定会活到最后。

\(\color{red} 四\) 例题

P2290 [HNOI2004] 树的计数

给定了每个节点的度数，那么该节点在 Prüfer 序列中出现次数也确定了。那么就是一个可重集合排列。

P4981 父子

\(n\) 个节点无根树的个数根据 Cayley 公式得到，由于节点之间互异，不同节点当根不会产生同构，所以有根树个数 \(\times n\) 即可。

\(\color{Violet}\mathsf{Cayley}\ 公式\mathsf{(Cayley's\ formula)}\)

\(n\) 个节点可以产生 \(n^{n-2}\) 种连通无根树。

用 Prüfer 序列证明：任意一个长度为 \(n-2\) 的值域 \([1,n]\) 的整数序列都可以通过 Prüfer 序列映射为一个生成树，故种类为 \(n^{n-2}\)。

\(\color{Violet} 图连通方案数\)

以下内容 copy 自 \(\mathcal{OIwiki}\)。本人还没阅读。

Prüfer 序列可能比你想得还强大。它能创造比凯莱公式更通用的公式。比如以下问题：

一个 [n] 个点 [m] 条边的带标号无向图有 [k] 个连通块。我们希望添加 [k-1] 条边使得整个图连通。求方案数。

证明

设 \(s_i\) 表示每个连通块的数量。我们对 \(k\) 个连通块构造 Prüfer 序列，然后你发现这并不是普通的 Prüfer 序列。因为每个连通块的连接方法很多。不能直接淦就设啊。于是设 \(d_i\) 为第 \(i\) 个连通块的度数。由于度数之和是边数的两倍，于是
\(\sum_{i=1}^kd_i=2k-2\) 。则对于给定的 \(d\) 序列构造 Prüfer 序列的方案数是

\[\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}=\frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdots(d_k-1)!} \]

对于第 \(i\) 个连通块，它的连接方式有 \({s_i}^{d_i}\) 种，因此对于给定 \(d\) 序列使图连通的方案数是

\[\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}\cdot \prod_{i=1}^k{s_i}^{d_i} \]

现在我们要枚举 \(d\) 序列，式子变成

\[\sum_{d_i\ge 1，\sum_{i=1}^kd_i=2k-2}\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}\cdot \prod_{i=1}^k{s_i}^{d_i} \]

好的这是一个非常不喜闻乐见的式子。但是别慌！我们有多元二项式定理：

\[(x_1 + \dots + x_m)^p = \sum_{\substack{c_i \ge 0 ,\ \sum_{i=1}^m c_i = p}} \binom{p}{c_1, c_2, \cdots ,c_m}\cdot \prod_{i=1}^m{x_i}^{c_i} \]

那么我们对原式做一下换元，设 \(e_i=d_i-1\) ，显然
\(\sum_{i=1}^ke_i=k-2\) ，于是原式变成

\[\sum_{e_i\ge 0，\sum_{i=1}^ke_i=k-2}\binom{k-2}{e_1,e_2,\cdots,e_k}\cdot \prod_{i=1}^k{s_i}^{e_i+1} \]

化简得到

\[(s_1+s_2+\cdots+s_k)^{k-2}\cdot \prod_{i=1}^ks_i \]

即