矩阵树定理

矩阵树定理

对于无向图

记度数矩阵 $D$，$D_{i,i}=de{g}_i$。邻接矩阵 $A$，$A_{i,j}=A_{j,i}$ 等于 $(i,j)$ 的数量。定义 基尔霍夫矩阵 $K=D-A$，则 $K$ 去掉 $k$ 行 $k$ 列 得到 $K^{\prime }$，$k^{\prime }$ 的行列式 $det(K^{\prime })$ 为图的生成树数量。

模板：P4111。

对于有向图

分 叶向树和根向树，将度数分别换为入度和出度，删去 $rt$ 行 $rt$ 列的行列式为以 $rt$ 为根的方案数。

模板：P4455。

生成树带权值

如果求图的 生成树每条边的权值之积 的和，将 $D$ 和 $A$ 的值改为对应的权值和。

P3317

对于一颗生成树 $T$，权值为 ${\prod }_{e\in T}{p}_e{\prod }_{e\notin T}(1-p_e)$。把 ${\prod }_e(1-p_e)$ 提出来，生成树每条边的权值为 $\frac{p_e}{1-p_e}$。

BEST 定理

对于欧拉图（有向图，存在欧拉回路，入度等于出度，除了孤立点强连通），从 $x$ 出发的欧拉回路等于以 $x$ 为根的根向树的方案数乘以 $de{g}_x\times \prod (de{g}_u-1)!$。

P7531

建源汇点，再从 $T$ 向 $S$ 连 $de{g}_S$ 条边，此时是欧拉图。随便选一个根求内向树，还要除去 $S,T$ 并不能随便定向。

相关技巧

P6624

莫比乌斯反演除去 $gcd$ 的贡献。此时生成树的权值为每条边之和，但矩阵树做的是每条边之积。权值 $(wx+1)$ 之积模 $x^2$ 的一次项权值，维护一个结构体的行列式。

P4208

最小生成树每种边权选的边数量相等。求出一个 MST 之后，把同个边权的边拉出来，先连上其他边权的边，把每层内的生成树数量乘起来。

Q9278

对初始为 $0$ 的 $n\times n$ 矩阵操作 $m$ 次，对 $l\le i\le r,l\le j\le r$ 的 $a_{i,j}$ 加 $1$。求矩阵的行列式。

$n\le 5\times 10^5,m\le n+300$。

二维差分后行列式值不变，等价于连边 $(l,r+1)$ 后图的基尔霍夫矩阵的行列式，即生成树方案数。注意到 $m-n\le 300$，广义串并联方法，点数 $600$，求出缩完之后每条边在/不在生成树的方案数 $f_e$ 和 $g_e$。提出 $\prod g_e$，边权为 $\frac{f_e}{g_e}$ 再矩阵树定理求生成树权值。