定理是用于解决图的生成树计数的一个定理，复杂度在级别。
内容：
构造一个仅在主对角线有值的矩阵，的值为号点的度数;
注意:这里的是出度，无向图算两次。
再构造一个邻接矩阵。
得到一个基尔霍夫矩阵。
我们取任意一个形如的该矩阵的代数余子式，其值就是以为根的生成树的数目，在有向图中表现为为根的树形图树目，无向图中就是生成树数目。
实现:
构造出基尔霍夫矩阵之后，取一个需要的代数余子式，类似高斯消元的求出它的上三角形式(左上到右下)，这条主对角线上元素的乘积就是该行列式的值。
证明：
咕着。
细节：
在辗转相除消元的时候，交换行列式的行/列时符号要取反。
最后在模意义下可能是负数，要加一个。
注意不要去消无用的点，比如对某个联通块求值的时候，那些不在该连通块里的点不要消。
行列式的运算法则和一般的矩阵消元不一样，若用行消去行,只能形如，形如是不合法的。
拓展:
求解有向图的树形图：度数矩阵定义为出度/入度，分别对应外向/内向。邻接矩阵单向，代数余子式为原矩阵消去根。
求解带权图的生成树边权乘积之和：度数矩阵为边权和，邻接矩阵为边权即可。
题目:
[SHOI2016]黑暗前的幻想乡
题意：有个点，一些边，每个边有一个颜色，共有种颜色，求每种颜色边恰好出现一次的生成树的个数
考虑容斥，设表示至多有种颜色的生成树数量，表示恰好有种颜色的数量。那么有,求解可以使用矩阵树定理做到。因为要带个求逆元的,于是总复杂度就是。
[SDOI2014]重建
巧妙而神仙。
题意：每个边有一个出现概率，求出现的边恰好构成一颗生成树的概率。
矩阵树定理其实求的是
而平时这个都是，我们没有过多的管它。
此题要求的是
上面那个式子化一下
后面那个式子就可以上矩阵树定理了。
注意：前面那个式子每条边只能被算一次。
[UOJ]智商锁
究极人类智慧题。
题意：构造点数为不超过的图，使得模意义下生成树个数为。
随机化，按照出题人的题解，随机个点数为的图，分别矩阵树定理算出生成树个数，复杂度,然后选个块粘在一起，两个连通块间只有一条边，设生成树个数为,那么这四个块粘在一起的生成树个数就是,的算出答案存起来。再的枚举另一半，每次查询另一半是否存在。
图的生成方式是保证图联通的前提下，其余每条边出现概率为(只要保证图很随机即可)。
正确性：的取值范围是,这是远大于模数的，这样从个种选个这么大的数乘起来就有约种取值，那么如果个点随机撒下来能够覆盖住就可以找到答案，算一波概率就是，约等于，这个概率几乎就是。