矩阵树定理

参考资料

• 矩阵树定理 - OI Wiki

简介

矩阵树定理（Kirchhoff 定理）把图的生成树个数表示为其基尔霍夫矩阵（度数矩阵减邻接矩阵）任一 $n-1$ 阶主子式的行列式。对带权图，行列式给出所有生成树「边权之积」的和；对有向图，按入度或出度构造可计数根向 / 叶向树形图。

例题

洛谷 P6178 【模板】Matrix-Tree 定理

给定一张带边权的无向图，求其所有生成树的边权乘积之和，对 $10^9+7$ 取模。