学一发matrix-tree
原来bzoj1016这题是暴搜+玄学并查集过的…数据弱怪我咯
首先matrix-tree需要度数矩阵D，就是说当i=j时D[i][j]为i的度数，否则为0。
还有邻接矩阵A，如果i、j两点直接相连的话A[i][j]=1，否则为0。
基尔霍夫矩阵C=D-A，只要把C中的任意一行一列去掉求剩下的行列式的绝对值就是生成树个数了。
额行列式怎么求？
只要通过高斯消元法将矩阵化成上三角矩阵，然后求对角线的乘积。
怎么高斯消元？这就是另一个问题了，因为你硬刚的话你会发现你并不知道行列式的符号…
辗转相除！复杂度就多了一个log
裸题 bzoj4031
bzoj1016如果我们用matrix-tree做的话，首先边权一样的边要排完序合成一坨。
一坨边的话我们都加入并查集，并且更新度数矩阵和访问标记。（注意如果一条边的两端点原来就是连通的就忽略）
这一坨边如果我们在这一次加的边访问到了，我们就枚举和这坨加边有关的每一个连通分量，跑一下matrix-tree大法求一下这个联通块的生成树个数。
bzoj1016这道题这样乱搞复杂度大概是O(n^4)的，反正能过