一个用来求一张图的生成树个数的方法。
基础结论
在无向图中，定义一个点的度数为 \(d_i\)，边 \((u,v)\) 的数量为 \(c_{u,v}\)。
在有向图中，定义一个点的入度为 \(ind_i\)，出度为 \(outd_i\)，边 \(u\to v\) 的数量为 \(t_{u,v}\)。
先把结论扔出来：
求无向图生成树：
记矩阵 \(M=(m_{ij})_{n\times n}\)，其中 \(m_{ij}=\begin{cases}d_i&,i=j\\-c_{i,j}&,i\neq j\end{cases}\)。
则删去这个矩阵第 \(i\) 行和第 \(i\) 列，得到的矩阵 \(M'\) 的行列式即为原图的生成树数。
求有向图外向树：
记矩阵 \(M_{out}=(m_{ij}){n\times n}\)，其中 \(m_{ij}=\begin{cases}ind_i&,i=j\\-t_{i,j}&,i\neq j\end{cases}\)。
则删去这个矩阵第 \(i\) 行和第 \(i\) 列，得到的矩阵 \(M'\) 的行列式即为原图以 \(i\) 为根的外向生成树数。
求有向图内向树：
记矩阵 \(M_{out}=(m_{ij}){n\times n}\)，其中 \(m_{ij}=\begin{cases}outd_i&,i=j\\-t_{i,j}&,i\neq j\end{cases}\)。
则删去这个矩阵第 \(i\) 行和第 \(i\) 列，得到的矩阵 \(M'\) 的行列式即为原图以 \(i\) 为根的内向生成树数。
证明就不在这里给出。
有了这个结论，我们就可以解决很多问题了：
Luogu P6178 【模板】Matrix-Tree 定理
[HEOI2015] 小 Z 的房间
[CQOI2018] 社交网络
[SHOI2016] 黑暗前的幻想乡
拓展延伸
其实对于对于树计数可以不是单纯的单个树求乘积，所有树求加和，也就是我们求的是 \(\sum\limits_{T}\prod\limits_{e\in T}w(e)\)。
然而内部不一定得是数乘，只要满足 \(<W,+,\times>\) 构成环即可，比如可以是FWT等卷积。
[THUPC2019] 找树
考虑统计每一种可能结果的数量，找到其中值非零且最大的即可。
每一位按照它的运算方式使用对应的 FWT 方式即可，复杂度 \(O(n^32^w)\)。