矩阵树定理
对于无向图
记度数矩阵 D，Di,i=degi。邻接矩阵 A，Ai,j=Aj,i 等于 (i,j) 的数量。定义 基尔霍夫矩阵 K=D−A，则 K 去掉 k 行 k 列 得到 K′，k′ 的行列式 det(K′) 为图的生成树数量。
对于有向图
分 叶向树和根向树，将度数分别换为入度和出度，删去 rt 行 rt 列的行列式为以 rt 为根的方案数。
生成树带权值
如果求图的 生成树每条边的权值之积 的和，将 D 和 A 的值改为对应的权值和。
对于一颗生成树 T，权值为 ∏e∈Tpe∏e∈/T(1−pe)。把 ∏e(1−pe) 提出来，生成树每条边的权值为 1−pepe。
BEST 定理
对于欧拉图（有向图，存在欧拉回路，入度等于出度，除了孤立点强连通），从 x 出发的欧拉回路等于以 x 为根的根向树的方案数乘以 degx×∏(degu−1)!。
建源汇点，再从 T 向 S 连 degS 条边，此时是欧拉图。随便选一个根求内向树，还要除去 S,T 并不能随便定向。
相关技巧
莫比乌斯反演除去 gcd 的贡献。此时生成树的权值为每条边之和，但矩阵树做的是每条边之积。权值 (wx+1) 之积模 x2 的一次项权值，维护一个结构体的行列式。
最小生成树每种边权选的边数量相等。求出一个 MST 之后，把同个边权的边拉出来，先连上其他边权的边，把每层内的生成树数量乘起来。
对初始为 0 的 n×n 矩阵操作 m 次，对 l≤i≤r,l≤j≤r 的 ai,j 加 1。求矩阵的行列式。
n≤5×105,m≤n+300。
二维差分后行列式值不变，等价于连边 (l,r+1) 后图的基尔霍夫矩阵的行列式，即生成树方案数。注意到 m−n≤300，广义串并联方法，点数 600，求出缩完之后每条边在/不在生成树的方案数 fe 和 ge。提出 ∏ge，边权为 gefe 再矩阵树定理求生成树权值。
