prufer 序列

定义：prufer序列是树和序列的双向映射，prufer 序列描述了节点的度数以及父节点的信息。

使用场景：将构造树的问题转化为构造序列，将统计树的问题转化为统计序列，将树的 dp 转化为序列的 dp。

如何得到 prufer 序列：

1. 统计树上所有结点的 degree.
2. 找到度数为 1 的最小的点把他的父亲加到 prufer 序列并删掉他。
3. 重复 2 直到只剩两个点。

性质：

1. 剩余两个点中一定有 n。
2. 节点编号在 prufer 序列中的出现次数为 degree-1

prufer 序列的常用结论：

1. 对于 n 个点的完全图，他的生成树的个数为 $n^{n-2}$
2. 对于 n 个点的无根树，他的方案数为 $n^{n-2}$，有根树的方案数是 $n^{n-1}$
3. 对于 n 个点的无根树，每个点的度数确定，他的方案数为 $(n-2)!/(deg_1!deg_2!...deg_n!)$