关于生成树计数的一些小技巧

· · 个人记录

众所周知，无向图 G 的生成树个数等于其 \mathrm{Laplacian} 矩阵的任何一个代数余子式（即任何一个 n-1 阶主子式）。

通俗地讲，一张图的 \mathrm{Laplacian} 矩阵即为其度数矩阵减去其邻接矩阵。

还有一些关于内、外向树的计数，可以参考 OI Wiki。

技巧1：生成树权值和的计算

把边加上边权，一棵生成树的权值定义为边权之积，求所有生成树的权值和。

把邻接矩阵的 1 换成边权，再将一点周围的边权和作为其度数。

可以用重边来解释。

技巧2：权值定义为边权加和

将边权 v 替换成一次多项式 x+v，最终结果即为行列式的一次项系数。

消元的时候只需要保留零次项和一次项，故可以通过一些构造得到逆元，然后就可以正常消元了。

技巧3：对边有额外要求

例：树有红蓝两种边，求有 s 条红边的生成树数量。

解：把蓝边的权值设为 1，红边的权值设为 x，答案即为行列式的 s 次项系数。

带着 x 很不好操作，我们选一些值带入，最后把答案插出来就可以了。