简介

$prufer$序列，是讲一棵树唯一转化为一个序列，在解决无根树的计数问题时十分有用。

无根树转$prufer$序列

我们定义一棵树的叶子为这棵树上度数为$1$的点。
每次找到编号最小的叶子节点，讲目前唯一与它相连的点的编号加入$prufer$序列，并删除这个叶子节点。
当最后还剩两个点的时候停止。
比如下图的$prufer$序列为$\{3,2,2,1,1\}$。

实现的话拿个$set$维护一下叶子结点就好了。

$prufer$序列转无根树

先有一个点集V，表示目前可能为叶子的集合，初始时等于{1..n}。
从前往后扫$prufer$序列，设$prufer$序列上这一位为$u$，找到$V$中没在之后的$prufer$序列中出现过，编号最小的节点$v$，将$u,v$连上一条边，并把$v$从$V$中删除。
直至最后$V$中剩下两个节点，将这两个节点间连边后停止。
实现的话同样是一个set可以搞定。

性质

通过上面这两种转化方式，显然一棵无根树只会与恰好一个$prufer$序列对应.
最重要的性质就是每个点在$prufer$序列中恰好出现度数-1次。

带标号无根树计数

给你$n$个点，让你求出$n$个点的无根树的数量为多少。
BZOJ 1430
根据上面的两条性质，题目转化为在一个长度为$n-2$的序列中填上$[1..n]$的方案数，显然为$n^{n-2}$
例题中再乘以一个$(n-1)!$阶乘就好了。

带标号无根树计数推广

推广1

给你$n$个点，并给定每个点的度数$d_i$，求出这$n$个点可以构成无根树的数量。
题意可以转化为，在长度为$n-2$的数列中，填上$[1..n]$，且$i$出现$d_i-1$次。
那么答案应该为

$\frac{(n-2)!}{\prod\limits_{i=1}^{n}(d_i-1)!}$

推广2

给你$n$个点，$k$个点的度数确定，剩下点的度数随意，求出这$n$个点可以构成的无根树的数量。
BZOJ 1005
假设prufer序列还有$res$个位置未确定
$res=(n-2)-\sum\limits_{i=1}^{k}(d_i-1)$
总方案为

$\frac{(n-2)!}{res!*\prod\limits_{i=1}^{k}(d_i-1)!}*(n-k)^{res}$

例题只需要在这个基础上加一个高精度即可。

带标号有根树计数

只需要给无根树选一个根就好了

$n^{n-2}*n$

结语

博主水平有限，目前只会不带标号的计数，带标号的有机会再更。