https://www.luogu.com.cn/problem/P6178

矩阵树定理

记住结论\(QAQ\)

\(D\)为度数矩阵

\(A\)为邻接矩阵

外向树：边的方向为根指向子节点

内向树：边的方向为子节点指向根

若边权为\(cost\)

那么所有生成树的乘积和如下：

无向图：

\(D\)：存在边\(i-j\)，则\(D_{i,i}+=cost,D_{j,j}+=cost\),对于\(D_{i,j}(i \ne j)\),\(D_{i,j}=0\)

\(A\)：存在边\(i-j\)则\(a_{i,j}=a_{j,i}=1\),否则\(a_{i,j}=a_{j,i}=0\)

有向图：

\(D\)：存在边\(i \rightarrow j\)，则：

外向树：\(D_{j,j}+=cost\)

内向树：\(D_{i,i}+=cost\)

\(A\)：存在边\(i \rightarrow j\)则\(a_{i,j}=1\),否则\(a_{i,j}=0\)

设\(C=D-A\)

无向图中：

答案为\(C\)对于任意的\(r\)，划去第\(r\)行，第\(r\)列得到的\(n-1\)阶余子式的行列式值

有向图中：

答案为\(C\)对于根节点\(r\)，划去第\(r\)行，第\(r\)列得到的\(n-1\)阶余子式的行列式值

若要计算生成树个数，设边权为\(1\)即可

Luogu6178 【模板】Matrix-Tree 定理

原文：https://www.cnblogs.com/GK0328/p/13435383.html