由于本人过菜，故写文备忘。
参考资料：
https://www.luogu.com.cn/blog/TheLostWeak/solution-p2290
https://oi-wiki.org/graph/prufer
https://github.com/cp-algorithms/cp-algorithms/blob/master/src/graph/pruefer_code.md
\(\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} 四\) 例题
给定了每个节点的度数，那么该节点在 Prüfer 序列中出现次数也确定了。那么就是一个可重集合排列。
\(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 序列的方案数是
对于第 \(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\) ，于是原式变成
化简得到
\[(s_1+s_2+\cdots+s_k)^{k-2}\cdot \prod_{i=1}^ks_i \]即
\[n^{k-2}\cdot\prod_{i=1}^ks_i \]这就是答案啦
标签：Pr,度数,sum,fer,序列,节点 From： https://www.cnblogs.com/xcrr/p/17638357.html