对于一个无向图，我们想知道它的生成树数量

前置知识——高斯消元解行列式

传送门 (opens new window)

矩阵树定理

这里只指无向图

生成树个数

对于一个图，我们可以按这样的规则建立一个行列式$A$
$A_{ij}\quad i\ne j$ 表示$i$点和$j$点的连边数量的相反数
$A_{ii}$ 表示$i$点的度数

例：
对于这样一个图，我们可以建出如下矩阵

$$\left\{\begin{matrix} &2 &-1 &-1 &-1 &-1\\ &-1 &2 &-1 &-1 &-1\\ &-1 &-1 &2 &-1 &-1\\ &-1 &-1 &-1 &2 &-1\\ &-1 &-1 &-1 &-1 &2 \end{matrix}\right\}$$

那么这样的一个行列式的值就是生成树的个数

生成树权值积的和

可以将$A_{ij}$换成连边的权值和

生成树权值和的和

我们求不了和，但是可以利用权值积利用有效的部分变成权值和
首先看一个多项式乘积形式：

$$(ax+b)(cx+d)=acx^2+(ad+bc)x+bd$$

在$b=d=1$时，多项式的一次项系数就是$a+c$
这里就转化成和的形式了
所以每次将$A_{ij}$换成$(连边的权值和\times x+1)$即可

在高斯消元中，我们还涉及到其他运算
所以要定义一下它们的其他操作
由于每次只看最后两项，所以在四种运算时多项式不用变得太长

$$\begin{aligned} &(ax+b)+(cx+d)=(a+c)x+(b+d)\\ &(ax+b)-(cx-d)=(a-c)x+(b-d)\\ &(ax+b)\times (cx-d) = ...+(ad + bc)x + bd\\ &(ax+b)\div (cx-d)=\frac {ad-bc}{d^2}x+\frac bd \end{aligned}$$

例题

1.洛谷P2144 轮状病毒
题目地址
题解地址

2.洛谷P4111 小Z的房间
题目地址
题解地址

3.洛谷P4336 黑暗前的幻想乡
题目地址
题解地址