矩阵树定理：
生成树的个数=$|G|$。
其中$G$为$D-A$，即度数矩阵-邻接矩阵。
具体而言，$D$的增加只在主对角线上，即每有一条$(u,v)$,$a[u][u]++,a[v][v]++$。
$A$的增加就是$a[u][v]++,a[v][u]++$。
然后求出其行列式即可。
升级版：
求所有的生成树的所有边权积之和。
就是把++换成+=边权即可。
证明就是把一条边权为$k$的边拆成$k$个边权为$1$的边，然后再做矩阵树定理，可以发现是等价的。
------------
拓展:
$root$为$i$的内向生成树计数：把$A$换成出度矩阵，求点$A[i][i]$的代数余子式。
$root$为$i$的外向生成树计数：把$A$换成入度矩阵，求点$A[i][i]$的代数余子式。
感性证明（以内向为例）:
舍弃当前行列求出的是有一条未定向，其他全部定向的边的生成树。
我们只需要把那条未定向的指向赋值为$root$即可。