prufer序列

这是一种将带标号的树用一个唯一的整数序列表示的方法.

很多与度数有关的树上计数问题,都可以用它以及它的性质来解决

从树到prufer序列

假设有一棵n个节点的树

每次选择一个编号最小的叶结点并删掉它,

然后在序列中记录下它连接到的那个结点.

重复n-2次后就只剩下两个结点

使用堆构造显然可以,复杂度\mathcal O(n \log n)

线性构造

性质

1. prufer序列与无根树一一对应
2. 在构造完prufer序列后原树中会剩下两个结点,其中一个一定是编号最大的点n.
3. 每个结点在序列中出现的次数是其度数减1(没有出现的就是叶结点)

4. Cayley公式(凯莱公式)

   n个点的完全图有2^{n-2}棵生成树。

   一棵n个点的树的prufer序列长度为n-2,

   即总共有n^{n-2}种prufer序列

   由于prufer序列与无根树一一对应,所以共有2^{n-2}种生成树

5. 对于给定度数为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