Prufer 序列

定义 对于 \(n\ge 2\)，Prufer 序列是一个长为 \(n-2\)，值域为 \([1,n]\) 的序列。

定理 Prufer 序列和 \(n\)（\(n\ge 2\)）个节点的有标号无根树（两棵树不同当且仅当存在 \((u,v)\) 在 \(T_1\) 上有边而在 \(T_2\) 上没边）存在一一映射关系。也就是说，\(n\)（\(n\ge 1\)）个节点的有标号无根树数量等于 \(n^{n-2}\)。

首先考虑如何从树构造序列。我们每次取出编号最小的叶子节点，将它父亲的编号加入到序列的末尾，然后删去这个叶子，直到树上只剩两个点。这显然是一个长为 \(n-2\)，值域为 \(n\) 的序列。

然后考虑如何从序列构造树。不难发现树上每个节点的度数等于它在 Prufer 序列中的出现次数 +1。于是我们可以知道初始时哪些节点是叶子，从而知道第一个被删除的叶子，于是我们得到了一条边。剩下的部分显然是一个子问题。

推论 如果一条连接 \((u,v)\) 的边有 \(sz[u]sz[v]\) 种方案，那么把 \(k\) 个点连成树的方案数等于

\[ \bigg(\prod_{i=1}^{k}sz[i]\bigg)\bigg(\sum_{i=1}^{k}sz[i]\bigg)^{k-2} \]

发现其实就是给方案数乘以了 \(\prod sz[i]^{deg(i)}\)，而 \(deg(i)\) 就是序列中出现次数加一，因此不难写出上式。