首页 > 代码库 > JZOJ5153:树形图求和

JZOJ5153:树形图求和

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:树形图求和