Prufer序列

定义

用来表示一棵\(n\)个节点有标号无根树的，长度为\(n-2\)序列，其中每个数都在\([1,n]\)范围内。

可以把它理解为完全图的生成树与数列之间的双射，常用于组合计数问题。

构建方法

1、找到编号最小的度数为\(1\)的节点。

2、删去该点，并在序列中添加与该节点相连的节点编号。

3、重复上述流程，直到树剩下两个节点。

维护当前编号最小的度数为\(1\)的节点，然后检查删去该点后是否产生编号比它更小的度数为\(1\)的点，可以得到\(O(n)\)的做法。

Prufer序列还原树

初始时set中是所有没有在prufer序列中出现的元素。

for p in prufer序列：
    q：set中最小元素
    set.erase(q)
    edge:(p,q)
    if：p为最后一次出现在prufer序列
        set.insert(p)

性质

1、最后剩下的两个点中，其中一个为\(n\)。

2、每个点在序列中出现的次数\(=\)其度数\(-1\)。

应用

1、\(n\)个点完全图生成树个数（\(n\)个点有标号无根树个数）：\(n^{n-2}\)

2、\(n\)个点有标号有根树个数：\(n^{n-1}\)（相当于上面的每种方案有\(n\)种选根的方式）

3、\(n\)个点有标号，其中第\(i\)个点的度数为\(\deg_i\)，的无根树个数：\(\frac{(n-2)!}{\Pi_{(\deg_i-1)!}}\)

一道例题（CF156D）

给出一个\(n\)个点\(m\)条边的图，添加最少的边使图连通，求最后的图的方案数。（\(n,m\le 10^5\)）

在给出的\(m\)条边中，只有不会产生环的边，即非树边是有用的，设有\(k\)条。

那么当前连通块有\(n-k\)个，需要添加\(n-k-1\)条边。

对于两个连通块，他们之间连边的方案数为他们点数之积，再利用上面的性质\(3\)，可以写出答案的式子：

\[\sum_{deg_i\ge 1,\sum_{i=1}^{n-k}deg_i=2(n-k)-2}\frac{(n-k-2)!}{(deg_1-1)!(deg_2-1)!\cdots(deg_{n-k}-1)!}\Pi_{i=1}^{n-k}size_i\]

其中\(size_i\)为第\(i\)个连通块的大小。

这个式子算不了，但可以用多项式定理化简，多项式定理即

\[(x_1+\cdots+x_m)^p=\sum_{c_i\ge 0,\sum_{i=1}^m c_i=p}\frac{p!}{c_1!c_2!\cdots c_m!}\Pi_{i=1}^m{x_i}^{c_i}\]

这个很好理解，证明不再赘述。那么把上面的\(deg_i-1\)换为\(c_i\)即可。

最后推出的式子为：

\[n^{n-k-2}\Pi_{i=1}^{n-k}size_i\]