传送门

题意：

幽香要修建幻想乡的公路。幻想乡有 N 个城市，之间原来没有任何路。幽香向选民承诺要减税，所以她打算只修 N- 1 条路将这些城市连接起来。但是幻想乡有正好 N- 1 个建筑公司，她打算让每个建筑公司都负责一条路来修。
每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间的。所以幽香打算选择 N-1 条能够连接幻想乡所有城市的边，然后每条边都交给一个能够负责该边的建筑公司修建，并且每个建筑公司都恰好修一条边。幽香现在想要知道一共有多少种可能的方案呢？两个方案不同当且仅当它们要么修的边的集合不同，要么边的分配方式不同。

Solution：

给出一个图，求这个图的生成树个数显然是可以用矩阵树定理，由于这道题正着去实现不好考虑，我们考虑这道题的反面：生成树中至少x个公司不选的方案数，这样一来我们用矩阵树定理可以很快的求出，而最终的答案我们就可以用容斥了，答案即为：选到所有公司-至少一个公司没选+2个公司没选…

最终复杂度 O(2n∗n3) ,行列式可以通过高斯消元 n3 求出，不懂的同学们请看这里

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int mod=1e9+7;
int n,m[20];
int a[20][20];
int sum=0;
struct edg{
    int x,y;
}e[20][400];
double abss(double x)
{
    return x<0?-x:x;
}
int fast_pow(int x,int a)
{
    int ans=1;
    for (;a;a>>=1,x=1ll*x*x%mod)
        if (a&1) ans=1ll*ans*x%mod;
    return ans;
} 
int mt(int n)
{
    bool flag=1; 
    for (int i=1;i<=n;i++)
    {
        int now=i;
        for (int j=i+1;j<=n;j++)
            if (abss(a[j][i])>abss(a[now][i])) now=j;
        if (now!=i)
        {
            flag^=1;
            for (int j=1;j<=n;j++)
                swap(a[now][j],a[i][j]);
        }
        for (int j=i+1;j<=n;j++)
        {
            int chu=1ll*a[j][i]*fast_pow(a[i][i],mod-2)%mod;
            for (int k=1;k<=n;k++)
                a[j][k]-=(1ll*a[i][k]*chu)%mod,a[j][k]=(a[j][k]+mod)%mod;
        }
    }
    int ans=1;
    for (int i=1;i<=n;i++)
        ans=1ll*ans*a[i][i]%mod;
    if (flag) return ans;
    else return (mod-ans)%mod;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        scanf("%d",&m[i]);
        for (int j=1;j<=m[i];j++)
            scanf("%d%d",&e[i][j].x,&e[i][j].y);
    }
    for (int S=0;S<(1<<(n-1));S++)
    {
        int num=0;
        memset(a,0,sizeof(a));
        for (int i=0;i<n;i++)
        {
            if ((S>>i)&1)
            {
                num++;
                for (int j=1;j<=m[i+1];j++)
                {
                    a[e[i+1][j].x][e[i+1][j].y]--;
                    a[e[i+1][j].y][e[i+1][j].x]--;
                    a[e[i+1][j].x][e[i+1][j].x]++;
                    a[e[i+1][j].y][e[i+1][j].y]++;
                }
            }
        }
        num=n-1-num;
        int g=mt(n-1);
        if (num&1) sum-=g;
        else sum+=g;
        sum=(1ll*sum+mod)%mod;
    }
    printf("%d",sum);
}