题目链接
题意：略（原题的描述已经很简练了）。
分析：首先需要知道的是一个prufer序列和一棵标号树是一一对应的，所以不会有S=0的情况。一个标号在prufer序列中没出现，当且仅当该标号对应的点在prufer序列对应的树中为叶结点。对图G，设其不同的生成树有cnt棵，令ans=cnt*n*(n+1)/2。考虑点u对ans的负贡献，即计算以u为叶结点的生成树的个数，设为cntu，则ans=ans-cntu*u。计算生成树个数用矩阵树定理，计算以u为叶结点的生成树个数可以先计算图G-u的生成树个数cnt0，则cntu=cnt0*du。
代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn=100+5,mo=1e9+7; void gcd(LL a,LL b,LL &d,LL &x,LL &y) { if (!b) {d=a;x=1;y=0;} else {gcd(b,a%b,d,y,x);y-=x*(a/b);} } LL inv(LL a,LL n) { LL d,x,y; gcd(a,n,d,x,y); return d==1?(x+n)%n:-1; } struct mat { int n; LL e[maxn][maxn]; void clear() { n=0;memset(e,0,sizeof(e)); } LL det() { /*for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) cout<<e[i][j]<<" "; cout<<endl; } cout<<endl;*/ for (int i=1;i<=n;i++) { int r=0; for (int k=i;k<=n;k++) if (e[k][i]) {r=k;break;} if (!r) return 0; if (r!=i) for (int j=1;j<=n;j++) swap(e[r][j],e[i][j]); LL iv=inv(e[i][i],mo); for (int k=i+1;k<=n;k++) if (e[k][i]) { LL o=e[k][i]*iv%mo; for (int j=1;j<=n;j++) e[k][j]=(e[k][j]-o*e[i][j]%mo+mo)%mo; } } LL ret=1; for (int i=1;i<=n;i++) ret=ret*e[i][i]%mo; //cout<<ret<<endl; return ret; } }; int n,m,a[maxn][maxn],d[maxn]; mat A; void init() { memset(a,0,sizeof(a)); memset(d,0,sizeof(d)); } int main() { int T;cin>>T; while (T--) { scanf("%d%d",&n,&m); init(); while (m--) { int u,v; scanf("%d%d",&u,&v); a[u][v]=a[v][u]=1; d[u]++;d[v]++; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) A.e[i][j]=(mo-a[i][j])%mo; for (int i=1;i<=n;i++) A.e[i][i]=d[i]; A.n=n-1; LL ans=A.det()*(LL)(n*(n+1)/2)%mo; for (int u=1;u<=n;u++) { A.clear(); for (int i=1;i<u;i++) { for (int j=1;j<u;j++) A.e[i][j]=(mo-a[i][j])%mo; for (int j=u+1;j<=n;j++) A.e[i][j-1]=(mo-a[i][j])%mo; } for (int i=1;i<u;i++) A.e[i][i]=d[i]-a[i][u]; for (int i=u+1;i<=n;i++) { for (int j=1;j<u;j++) A.e[i-1][j]=(mo-a[i][j])%mo; for (int j=u+1;j<=n;j++) A.e[i-1][j-1]=(mo-a[i][j])%mo; } for (int i=u+1;i<=n;i++) A.e[i-1][i-1]=d[i]-a[i][u]; A.n=n-2; ans=(ans-A.det()*d[u]*u%mo+mo)%mo; } printf("%d\n",(ans+mo)%mo); } return 0; }