Description

Input

Output

HINT

题解：

一种很直观的想法是通过矩阵生成树求树形图方法数ans以及不包含某一条边i的树形图方法数ans[i]，则答案为Σ(ans-ans[i])*w[i]。

对于树形图，矩阵生成树的建立方法是：将有向边(u,v)加入，即inc(A[u,u])（如果是要求n能够走到所有点则inc(A[v,v])），dec(A[u,v])。

删去第n行与第n列后，求行列式（即m[n,n]，m为余子式矩阵）。

对于要删去某条边情况下的m[n,n]，只要修改矩阵的两项，再求m[n,n]。因为总要删去第n行与第n列，所以只要保留(n-1)*(n-1)的矩阵，每次求整个矩阵的行列式即可。

但是这样做肯定会TLE，考虑使用伴随矩阵去优化。

有公式：

其中，A为原矩阵，A*为A的伴随矩阵，即A的代数余子式矩阵cof A的转置。（cof A[i,j]=(-1)^(i+j)*m[i,j]）

我们通过高斯消元求行列式以及矩阵求逆，计算出A*，转置得到cof A。

                                                            n

对矩阵行展开求行列式的公式是：det(A)   =    ∑    A[i,j]   *   cof A[i,j]  （按第i行展开）

                                                           j=1 

当删去一条边时，只修改了A[u,u]与A[u,v]，它们都在第u行，所以cof A的第u行不变。

我们可以按第u行展开，O(n)求解。多预处理一些东西，甚至可以O(1)求解。

JZOJ5153:树形图求和