看到这题面,应该是生成树计数了。

再容斥一下就好了。

可是我不会生成树计数啊!

回顾了一下矩阵树定理,发现有点不一样(可能以前学错了。

矩阵树定理只能背啊。。。

和普通的高斯消元有点不同,这是行列式。

所以互换时要反号(答案要取反)。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int M=570707,N=(1<<18)-1,mod=1e9+7;
const double pi=acos(-1);
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int u[20][400],v[20][400],siz[N],G[20][20],m[N];
inline int add(int x,int y){x+=y;if(x>=mod)x-=mod;return x;}
inline int del(int x,int y){x-=y;if(x<0)x+=mod;return x;}
inline int mul(int x,int y){x=1ll*x*y%mod;return x;}
inline int fpow(int a,int b){int ans=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;}
inline int gauss(int n)
{
    int f=1,ans=1;
    for(int i=1;i<=n;i++)    
    {
        int x=i;for(int j=i+1;j<=n;j++)if(G[j][i]>G[x][i])x=j;
        if(x!=i){f=-f;for(int j=i;j<=n;j++)swap(G[x][j],G[i][j]);}
        if(!G[i][i])return 0;
        for(int k=1;k<=n;k++)
            if(k!=i)
            {
                int sum=mul(G[k][i],fpow(G[i][i],mod-2));
                for(int j=i;j<=n;j++)G[k][j]=del(G[k][j],mul(G[i][j],sum));
            }
    }
    ans=mul(ans,f+mod);
    for(int i=1;i<=n;i++)ans=mul(ans,G[i][i]);
    return ans;
}
int main()
{
    int n;qr(n);int s=(1<<(n-1))-1;
    for(int i=1;i<n;i++){qr(m[i]);for(int j=1;j<=m[i];j++)qr(u[i][j]),qr(v[i][j]);}
    siz[1]=1;for(int i=2;i<=s;i++)siz[i]=siz[i>>1]+(i&1);int ans=0;
    for(int i=s;i>=1;i--)
    {
        memset(G,0,sizeof(G));
        for(int p=i,j=1;p;p>>=1,++j)
            if(p&1)for(int k=1;k<=m[j];k++)
            {
                int x=u[j][k],y=v[j][k];
                ++G[x][x];++G[y][y];
                --G[x][y];--G[y][x]; 
            }
        if((n-siz[i])&1)ans=add(ans,gauss(n-1));
        else ans=del(ans,gauss(n-1));
    }
    qw(ans);puts("");
    return 0;
}