真是菜到爆炸。。。。容斥写反（反正第一次写qwq）
题意：$n-1$个公司，每个公司可以连一些边，求每个边让不同公司连的生成树方案数。
矩阵树定理+容斥原理（注意到$n$不是很大）
枚举公司参与与否的状态，每次重构矩阵，把参与连边的公司可以连的边写在矩阵中，然后求出方案。
代码中的$Gauss()$是辗转相除求解，$Gauss2()$是通过求逆元求解（貌似我的辗转相除更快（雾））
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#define ll long long
#define R register ll
char B[<<],*S=B,*T=B;
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?EOF:*S++)
const int M=;
using namespace std;
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
int n,ans=,C; ll a[][]; vector<pair<int,int> > q[];
#define pb push_back
inline int Gauss() { ll ans=;
for(R i=;i<n;++i) {
for(R j=i+;j<n;++j) while(a[j][i]) {
ll t=a[i][i]/a[j][i];
for(R k=i;k<n;++k) (a[i][k]-=t*a[j][k])%=M;
swap(a[i],a[j]); ans=-ans;
} ans=(ans*a[i][i])%M; if(!ans) return ;
} return (ans+M)%M;
}
inline ll Inv(int x) {
if(x==) return ; if(x<) return ;
return (M-M/x*Inv(M%x))%M;
}
inline int Gauss2() { register ll ans=;
for(R i=;i<n;++i) for(R j=i+;j<n;++j) {
if(!a[i][i]) return ; if(!a[j][i]) continue;
register ll t=(ll)a[j][i]*Inv(a[i][i]%M)%M;
for(R k=i;k<n;++k) a[j][k]=((a[j][k]-t*a[i][k])%M+M)%M;
} for(R i=;i<n;++i) ans=ans*a[i][i]%M; return ans;
}
signed main() {
n=g(); for(R i=,x;i<n;++i) { x=g();
for(R j=,u,v;j<=x;++j) u=g(),v=g(),q[i].pb(make_pair(u,v));
} C=<<(n-);
for(R i=;i<C;++i) { R cnt=; memset(a,,sizeof(a));
for(R j=;j<n;++j) if(i&(<<j-)) {
for(R k=,u,v;k<q[j].size();++k)
u=q[j][k].first,v=q[j][k].second,
++a[u][u],++a[v][v],--a[u][v],--a[v][u];
++cnt;
} if((n-cnt)&) ans=(ans+Gauss2())%M;
else ans=(ans-Gauss2()+M)%M;
} printf("%lld\n",ans);
}
2019.06.02