数据范围看错了,事实上数据范围允许一个很简单的容斥。
推广辗转相除版高斯消元,废除取模!!!!1
#include<bits/stdc++.h>
using namespace std;
const int N=20,M=250;
const int mod=1e9+7;
int n;
int e[N][N],d[N][N];
bool vis[N];
int lastans;
vector<pair<int,int> > v[N];
int delt(int a[N][N],int sz) {
int ans=1;
for(int i=1;i<=sz;++i) {
for(int j=i+1;j<=sz;++j) {
while(a[i][i]) {
int div=a[j][i]/a[i][i];
for(int l=i;l<n;++l) a[j][l]=(a[j][l]-1ll*a[i][l]*div%mod+mod)%mod;
swap(a[i],a[j]);
ans=-ans;
}
swap(a[i],a[j]);
ans=-ans;
}
}
for(int i=1;i<=sz;++i) ans=(1ll*ans*a[i][i])%mod;
return (ans+mod)%mod;
}
void dfs(int t,int num) {
if(t>=n) {
memset(e,0,sizeof(e));
memset(d,0,sizeof(d));
for(int i=1;i<n;++i) {
if(vis[i]) {
int tmpm=v[i].size();
for(int j=0;j<v[i].size();++j) {
int tmpu=v[i][j].first,tmpv=v[i][j].second;
d[tmpu][tmpu]++;
d[tmpv][tmpv]++;
e[tmpu][tmpv]++;
e[tmpv][tmpu]++;
}
}
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) e[i][j]=(d[i][j]-e[i][j]+mod)%mod;
lastans=(1ll*lastans+delt(e,n-1)*(1-((((n-1)&1)^(num&1))<<1))%mod+mod)%mod;
return;
}
dfs(t+1,num);
vis[t]=1;
dfs(t+1,num+1);
vis[t]=0;
}
int main() {
scanf("%d",&n);
for(int i=1;i<n;++i){
int m;
scanf("%d",&m);
for(int j=1;j<=m;++j) {
int tmpu,tmpv;
scanf("%d%d",&tmpu,&tmpv);
v[i].push_back(make_pair(tmpu,tmpv));
}
}
dfs(1,0);
printf("%d\n",lastans);
return 0;
}