「北京省选集训2019」生成树计数「Matrix-Tree」
前置知识Matrix-Tree定理对于无向图 $G$，定义其度数矩阵 $D$$$\left[\begin{matrix}deg_1 & 0 & 0 & \cdots & 0 \\0 & deg_2 & 0 & \cdots & 0 \\0 & 0 & deg_3 & \cdots & 0 \\\vdots & \vdots & \vdots & \ddots & \vdots \\0 & 0 & 0 & 0 & deg_n\end{matrix}\right]$$定义其邻接矩阵 $C$$$\left[\begin{matrix}0 & a_{1,2} & a_{1,3} & \cdots & a_{1,n} \\a_{2,1} & 0 & a_{2,3} & \cdots & a_{2,n} \\\vdots & \vdots & \vdots &a ...