矩阵树定理
本文不作为教学向文章。
比较好的文章参考：
对于无向图
无向图中应该是矩阵树定理的常用场景。
无向图的矩阵树定理讲的是：
$$\sum_{T} \prod_{e \in T} w_e $$
求行列式的矩阵为 $D - A$，也就是度数矩阵 $D$ 减去邻接矩阵 $A$。
其中 $A_{i, j} = \sum w(i, j)$，也就是 $i \to j$ 的边的边权之和（允许重边）。
其中 $D_{i, i} = \sum_j w(i, j)$，也就是所有通向 $i$ 的边的边权之和。
这好像在无向图中也适用。
如果我们需要计数的话，就把边权设为 $1$ 即可。
在 [SDOI2014]重建 - 洛谷 中，求的是 $\sum_T \prod_{e \in T} p_e \prod_{e \not\in T} (1 - p_e)$。
我们可以轻易的把 $\prod_{e \not\in T} (1 - p_e)$ 它变为 $\cfrac {\prod_e (1 - p_e)}{\prod_{e \in T} (1 - p_e)}$。
剩下的就简单了。于是余下的是建矩阵的问题。
根据上面所说，也很简单了。
对于有向图
$A, D$ 的定义与上面类似。
只是注意两个点：
内向树和外向树
根
在求 $\det$ 的时候需要删掉一行，删掉的那一行作为的是根！
内向树和外向树？内向即是指向根的方向，外向即是根向外指。
此时 $D$ 需要有变化：$D_{i, i} = \sum_j w(i, j)$ 就是根向外指，是外向树。如果为 $\sum_j w(j, i)$ 则是内向树。
无向图中随意，因为无论外向还是内向结果都是一样的。
拓展 - 求和
生成树求和，具体来说就是求 $\sum_{T} \sum_{e \in T} w(e)$。
稍微扩展一下，求 $\sum_{T} (\sum_{e \in T} w(e))^k$。
首先观察到 $(\sum w_i)^k = \sum_{\sum a_i = k} \frac {k!}{\prod a_i !} \prod w_i^{a_i}$，整理一下得到：$= k! \sum_{\sum a_i = k} \prod \frac {w_i^{a_i}}{a_i !}$。后面这部分很像 EGF，所以对于每一个边建立其边权的 EGF，得到最终的答案为 $k! [x^k] \sum_{T} \prod_{e \in T} F^{(e)}(e)$。
后面这个部分很像矩阵树定理，于是套用高斯消元的板子，只是其元素变成了 $F^{(e)}$ 而已。
如果存在一个多项式没有逆，这是不可以的，根据矩阵树定理，如果一个图联通，那么其行列式不为 $0$，也就是这个矩阵存在逆。而对于没有逆的多项式，其满足 $[x^0]F(x) = 0$，但是对于常系数来说，其与正常的矩阵树是一样的，所以一定存在一个 $[x^0]F(x) \ne 0$ 的多项式，其一定有逆。
但是如果图不连通……其结果为 $0$ 即可。
于是对于求和的问题，就可以 $O(2^2 n^3)$ 的求解了，对于一般的问题可以 $O(n^3 k^2)$ 的完成，其中 $O(k^2)$ 是给多项式乘法和求逆的。。