简介
prufer序列 是一种无根树的编码表示方法，类似于 hash
一棵 $n$ 个节点的无根树唯一对应一串长为 $n-2$ 的 prufer编码
所以一个 $n$ 阶完全图的生成树个数为 $n^{n-2}$
无根树 转 prufer序列
定义无根树中度数为 $1$ 的节点是叶子节点
找到编号最小的叶子并删除，序列中添加与之相连的节点编号，重复执行直到只剩下 $2$ 个节点
prufer序列 转 无根树
我们设点集为 ${1,2,\cdots,n}$
然后我们每次找到点集中没有出现在 prufer序列 中的最小的点（这一定是这个时刻删除的叶子节点）
然后再取出 prufer序列 中的第一个元素，两个点建边，在将两个点在分别删除
性质
prufer序列 中某个编号出现的次数就是这个编号节点的度数减一
例题
【HNOI 2004】树的计数
一个有 $n$ 个结点的树，设它的结点分别为 $v_1, v_2, \cdots, v_n$，已知第 $i$ 个结点 $v_i$ 的度数为 $d_i$，问满足这样的条件的不同的树有多少棵
给定 $n,d_1, d_2,\cdots, d_n$，编程需要输出满足 $d(v_i)=d_i$ 的树的个数
其中 $1 \le n \le 150$，输入数据保证满足条件的树不超过 $10^{17}$ 个
由 prufer序列 的性质可以得知，度数为 $i$ 的点在序列中出现 $i-1$ 次
那么就相当于给定一些元素，元素 $i$ 有 $d_i-1$ 个，求可重集的全排列个数，也就是：
$$
\frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!}
$$
【HNOI 2008】明明的烦恼
给出标号为 $1$ 到 $n$ 的点，以及某些点最终的度数
允许在任意两点间连线，求可产生多少棵度数满足要求的树
其中 $1 \le n \le 1000$
假设有 $k$ 个点的度数被限定了，分别是 $d_1,d_2,\cdots,d_k$，记 $s=\sum_{i=1}^{k}(d_i-1)$，那么剩余的点有 $n-k$ 个，总方案数为：
$$
(n-k)^{n-2-s}{n-2 \choose s}\frac{s!}{\prod_{i=1}^{k}(d_i-1)}
$$
【bzoj 1430】小猴打架
一开始森林里面有 $n$ 只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友
每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友
经过 $n-1$ 次打架之后，整个森林的小猴都会成为好朋友
现在的问题是，总共有多少种不同的打架过程
其中 $1 \le n \le 10^6$
对于任意一棵树，对答案的贡献都是 $(n-1)!$，因为连边顺序可以任意
那么树的个数就是 $n^{n-2}$，所以答案就是 $n^{n-2}(n-1)!$
【51nod 1806】wangyurzee的树
求有多少个 $n$ 个节点的无根树，使得满足 $m$ 个给定的条件，每个条件诸如限定点 $u_i$ 的度数不能为 $d_i$
其中 $1 \le n \le 10^6, 0 \le m \le 17, 1 \le u_i \le n, 1 \le d_i \le n-1$
考虑容斥，每次枚举一个条件子集，限定强制要求这个子集不满足条件
假设限定的是 $d_1,d_2,\cdots,d_k$，记 $s=\sum_{i=1}^{k}(d_i-1)$，那么方案数为：
$$
(n-k)^{n-2-s}{n-2 \choose s}\frac{s!}{\prod_{i=1}^{k}(d_i-1)!}
$$
【GDSOI2017 第二轮模拟】树
有 $n$ 个点，它们从 $1$ 到 $n$ 进行标号，第 $i$ 个点的限制为度数不能超过 $a_i$
现在对于每个 $s (1 \le s \le n)$，问从这 $n$ 个点中选出一些点组成大小为 $s$ 的有标号无根树的方案数
其中 $1 \le n \le 100$
设 $f_{i,j,k}$ 表示考虑完了 $1 \sim i$，且选择了 $j$ 个点，且 prufer序列 填完了前 $k$ 个位置的方案数，则有：
$$
f_{i,j,k}=f_{i-1,j,k}+\sum_{t=1}^{a_i} {k \choose t-1} f_{i-1,j-1,k-(t-1)}
$$
