终于下定决心搞一下高斯消元了，打完模板就尝试来做一下这道题，发现一下子就秒掉了？
题解
直接考虑容斥加矩阵树定理，令 (U) 为工程队的全集，考虑强制令集合 (S) 中的建筑队不修路，(f(S)) 表示此方案下的生成树个数，则答案为
[ans=sum_{Ssubseteq U} (-1)^{|S|}cdot f(S)
]
(f(S)) 就直接通过矩阵树定理求。时间复杂度是 (O(n^32^n)) ，好像可以通过？
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=20;
const int MOD=1e9+7;
int n,a[N][N],b[N][N],res=0;
vector<pair<int,int> > bag[N];
int ksm(int x,int k){
int res=1;
for(;k;k>>=1,x=x*x%MOD)
if(k&1) res=res*x%MOD;
return res;
}
void dfs(int now,int cnt){
if(now>=n){
for(int i=1;i<n;++i){
for(int j=1;j<n;++j)
b[i][j]=a[i][j];
}
for(int i=1;i<n;++i){
for(int j=1;j<n;++j){
if(i==j) continue;
int del=b[j][i]*ksm(b[i][i],MOD-2)%MOD;
for(int k=1;k<n;++k) b[j][k]+=MOD-del*b[i][k]%MOD,b[j][k]%=MOD;
}
}
int sum=pow(MOD-1,cnt%2);
for(int i=1;i<n;++i) sum*=b[i][i],sum%=MOD;
res+=sum,res%=MOD;
return ;
}
dfs(now+1,cnt+1);
for(int i=0;i<(int)bag[now].size();++i){
a[bag[now][i].first][bag[now][i].second]+=MOD-1;
a[bag[now][i].first][bag[now][i].second]%=MOD;
a[bag[now][i].second][bag[now][i].first]+=MOD-1;
a[bag[now][i].second][bag[now][i].first]%=MOD;
a[bag[now][i].first][bag[now][i].first]++;
a[bag[now][i].first][bag[now][i].first]%=MOD;
a[bag[now][i].second][bag[now][i].second]++;
a[bag[now][i].second][bag[now][i].second]%=MOD;
}
dfs(now+1,cnt);
for(int i=0;i<(int)bag[now].size();++i){
a[bag[now][i].first][bag[now][i].second]++;
a[bag[now][i].first][bag[now][i].second]%=MOD;
a[bag[now][i].second][bag[now][i].first]++;
a[bag[now][i].second][bag[now][i].first]%=MOD;
a[bag[now][i].first][bag[now][i].first]+=MOD-1;
a[bag[now][i].first][bag[now][i].first]%=MOD;
a[bag[now][i].second][bag[now][i].second]+=MOD-1;
a[bag[now][i].second][bag[now][i].second]%=MOD;
}
}
signed main(){
cin>>n;
for(int i=1;i<n;++i){
int m,u,v;scanf("%lld",&m);
for(int j=1;j<=m;++j){
scanf("%lld %lld",&u,&v);
bag[i].push_back(make_pair(u,v));
}
}
dfs(1,0),printf("%lld
",res);
return 0;
}