prufer序列
这是一种将带标号的树用一个唯一的整数序列表示的方法.
很多与度数有关的树上计数问题,都可以用它以及它的性质来解决
从树到prufer序列
假设有一棵n
个节点的树
每次选择一个编号最小的叶结点并删掉它,
然后在序列中记录下它连接到的那个结点.
重复n-2
次后就只剩下两个结点
使用堆构造显然可以,复杂度\mathcal O(n \log n)
线性构造
性质
prufer
序列与无根树一一对应
- 在构造完
prufer
序列后原树中会剩下两个结点,其中一个一定是编号最大的点n
.
- 每个结点在序列中出现的次数是其度数减
1
(没有出现的就是叶结点)
Cayley公式(凯莱公式)
n
个点的完全图有2^{n-2}
棵生成树。
一棵n
个点的树的prufer
序列长度为n-2
,
即总共有n^{n-2}
种prufer
序列
由于prufer
序列与无根树一一对应,所以共有2^{n-2}
种生成树
对于给定度数为d_{1\sim n}
的一棵无根树共有\dfrac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}
种情况
全部全排列方案数除以每个点i
的排列方案数(除去重复的)
第i
个点度数为d_i
,会在prufer
序列中出现d_i-1
次,全排列方案数为(d_i-1)!
图连通方案数
一个n
个点m
条边的带标号无向图有k
个连通块。
求添加k
条边使得整个图连通的方案数。
设s_i
为每个连通块点数
对每个连通块构建prufer
序列
由于度数为边数两倍,\displaystyle \sum_{i=1}^k d_i=2k-2
对于给定d
序列构造prufer
序列的方案数为:
\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1} = \frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdot(d_k-1)!}
对于第i
个连通块,它的连接方式有s_i^{d_i}
种,对于给定d
序列使图连通的方案数为:
\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}
枚举d
序列:
\displaystyle \sum_{d_i\ge 1,\sum d_i=2k-2} {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}
换元,设e_i=d_i-1
:
\displaystyle \sum_{e_i\ge 0,\sum e_i=k-2} {k-2\choose e_1,e_2,\dots,e_k}\cdot \prod_{i=1}^k s_i^{e_i+1}
根据多元二项式定理:
\displaystyle (x_1+x_2+\dots+x_m)^p=\sum_{c_i\ge 0,\sum c_i=p} {p\choose c_1,c_2,\dots,c_m}\cdot \prod_{i=1}^m x_i^{c_i}
原式化简得:
\displaystyle (s_1+s_2+\dots+s_k)^{k-2}\cdot \prod_{i=1}^k s_i
即
\displaystyle n^{k-2} \cdot \prod_{i=1}^k s_i
从prufer序列到树
例题
[HNOI2004]树的计数
CF156D Clues