Prufer 序列，用于把一颗树双射到一个序列上，在有度数限制的树计数上很有用。
构造过程：每次去最小的叶子，将其父亲加入序列中，再删除这个点。直到只剩两个点，其中一个点肯定是 \(n\)（如果是有根树）。
直接一个堆是 \(\mathcal{O}(n \log n)\) 的，然后考虑如果父节点编号更小直接用父节点，否则从当前节点的编号 \(+1\) 开始找下一个叶子，显然是 \(\mathcal{O}(n)\) 的。
同理可以通过 Prufer 序列还原出树。
性质：每个点的度数 \(-1\) 为其在 Prufer 序列中出现的次数。
下面是几个应用：
- \(n\) 个点带标号无根树有 \(n^{n-2}\) 个，因为 Prufer 序列上每个值的范围都是 \([1, n]\)。于是完全图 \(K_n\) 的生成树个数为 \(n^{n-2}\)。对于有根树，枚举根方案数是 \(n\)，于是个数为 \(n^{n-1}\)。
- 给定 \(n\) 个点 \(m\) 条边的带标号无向图，有 \(k\) 个连通块，求添加 \(k - 1\) 条边使得图连通的方案数。
把连通块看成点，其度数（连向其它连通块的边数）为 \(d_i\)，节点个数为 \(s_i\)，则向外连有 \(s_i ^ {d_i}\) 种方案（每条边都可以从任意一个点连出去），且边数是 \(\sum d_i = 2k - 2\)，于是 \(\sum d_i - 1 = k - 2\)，Prufer 序列的的数量是 \(\dbinom{k-2}{d_1 - 1, d_2 - 1, \dots, d_k - 1}\) 的。
于是方案数为：
\[\sum\limits_{d_i \ge 1 \sum d_i = 2k-2}\dbinom{k-2}{d_1 - 1, d_2 - 1, \dots, d_k - 1} \times \prod s_i^{d_i}
\]
\[=\sum\limits_{e_i \ge 0 \sum d_i = k-2}\dbinom{k-2}{e_1, e_2, \dots, e_k} \times \prod s_i^{e_i+1}
\]
根据多元二项式定理：
\[=(\sum s_i)^{k - 2} \times \prod s_i
\]
\[=n^{k - 2} \prod s_i
\]
- \(n\) 个点环点数为 \(x\)，且环已给定的基环树个数为 \(x\times n^{n-x-1}\)，这是因为最后一个点只能选环上的点为父节点。
例题：P6086, P2290, P3673