生成树计数问题用矩阵树定理来考虑。

矩阵树定理求得的为\(\sum\limits_T\prod\limits_{e\in T}v_e\),也就是所有生成树的边权积的和。

这题边是不带权的,应用矩阵树定理前,我们必须考虑给每条边赋上一个权值。

可以从多项式的角度来考虑解决生成树和给定树有\(k\)条边重复这一条件,将给定树的边边权赋为\(x\),其余边赋为\(1\),那么应用矩阵树定理后得到的多项式中第\(k\)次项\(x^k\)的系数即为恰好有\(k\)条边重复的方案数。

发现直接代入多项式来求行列式不太现实,那么可以先求得\(x\)在取\(1\)到\(n\)时行列式的值,然后就得到了\(n\)个方程,把原多项式的系数看作未知数,代入\(x\)得到的值来作为现在的系数,那么就可以通过高斯消元来求解了。

具体实现看代码吧。

\(code:\)

#include<bits/stdc++.h>
#define maxn 210
#define mod 1000000007
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
ll n;
ll a[maxn][maxn],b[maxn][maxn],e[maxn][maxn];
ll inv(ll x)
{
ll y=mod-2,ans=1;
while(y)
{
if(y&1) ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
ll det()
{
ll ans=1;
for(int i=1;i<n;++i)
{
ll p=inv(b[i][i]);
for(int j=i+1;j<n;++j)
{
ll d=b[j][i]*p%mod;
for(int k=i;k<n;++k)
b[j][k]=(b[j][k]-b[i][k]*d%mod+mod)%mod;
}
ans=ans*b[i][i]%mod;
if(!b[i][i]) return 0;
}
return ans;
}
void gauss()
{
for(int i=1;i<=n;++i)
{
ll d=inv(a[i][i]);
for(int j=i;j<=n+1;++j) a[i][j]=a[i][j]*d%mod;
for(int j=i+1;j<=n;++j)
{
d=a[j][i];
for(int k=i;k<=n+1;++k)
a[j][k]=(a[j][k]-a[i][k]*d%mod+mod)%mod;
}
}
for(int i=n;i;--i)
for(int j=i-1;j;--j)
a[j][n+1]=(a[j][n+1]-a[j][i]*a[i][n+1]%mod+mod)%mod;
}
int main()
{
read(n);
for(int i=1;i<n;++i)
{
int x,y;
read(x),read(y);
e[x][y]=e[y][x]=1;
}
for(int i=1;i<=n;++i)
{
a[i][1]=1;
for(int j=2;j<=n;++j)
a[i][j]=a[i][j-1]*i%mod;
}
for(int k=1;k<=n;++k)
{
for(int i=1;i<=n;++i)
{
b[i][i]=0;
for(int j=1;j<=n;++j)
{
if(i==j) continue;
if(e[i][j]) b[i][j]=mod-k,b[i][i]+=k;
else b[i][j]=mod-1,b[i][i]++;
}
}
a[k][n+1]=det();
}
gauss();
for(int i=1;i<=n;++i) printf("%lld ",a[i][n+1]);
return 0;
}
05-11 09:04