矩阵树定理
本文不作为教学向文章。
比较好的文章参考：
对于无向图
无向图中应该是矩阵树定理的常用场景。
无向图的矩阵树定理讲的是：
\[\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)\) 则是内向树。
无向图中随意，因为无论外向还是内向结果都是一样的。