题意简述：
求在 $n$ 条有色（$n-1$ 种颜色）边中选 $n-1$ 条 颜色各异 的边使它们构成一颗树的方案数。
题目解法：
前置知识：矩阵树定理
不会不行，有关系。
看到数据范围 $(n\le17)$，果断想到时间复杂度为 $O(F2^ n)$，其中 $F$ 为一个关于 $n$ 的小（请感性理解）多项式。
我们看到，求生成树的个数，根据以往知识，肯定要用 $\rm Matrix-Tree$ 定理了。
然后就是这个颜色各异条件特别烦，我们考虑枚举用的边从何处选出。
如果枚举用啥边，时间复杂度是 $\mathcal{O}(\prod m_ i n^ 3)$ 的，还不如暴力。
仔细想想，是因为 重复计数 了，每种情况都枚举了。
根据以往的经验，这道题数据规模又很小，所以用 容斥原理 就行了。
具体而言，就是 $\mathcal{O}(2^ n)$ 枚举只取其中几种颜色的边，然后瞎算一下就行了。
记 $f$ 为只考虑某几种颜色时生成树的个数，则可以在 $\mathcal{O}(n^ 3)$ 的时间复杂度算出一种选择方案所对应的 $f$ 值。
更具体点，就是 $\sum\limits_ {\text{取 1 个}}f-\sum\limits_ {\text{取 2 个}}f+\sum\limits_ {\text{取 3 个}}f-\sum\limits_ {\text{取 4 个}}f\cdots\pm\sum\limits_ {\text{取 (n-1) 个}}f$。
很显然，这个正负号取决于选的个数的奇偶性。
所以状压一下从 $1$ 枚举到 $2^ {n-1}-1$（$\rm dfs$ 也行）顺便统计一下选的个数 $\text{(cnt)}$ 然后容斥就行了。
具体详见代码。
正确代码：
#include<bits/stdc++.h>
#define mp(x,y) make_pair(x,y)
#define mod 1000000007
using namespace std;
int TMP3301;
inline int read(){
int res=0;
char c;
bool zf=0;
while(((c=getchar())<'0'||c>'9')&&c!= '-');
if(c=='-')zf=1;
else res=c-'0';
while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
if(zf)return -res;
return res;
}
int n;
int dta[21][21];
typedef pair<int,int>P;
vector<P>q[21];
inline void _swap(int x,int y){
for(register int i=1;i<=n;++i){
#define swap(x,y) TMP3301=x,x=y,y=TMP3301;
swap(dta[i][x],dta[i][y]);
#undef swap
}
return;
}
inline int det(){
int ans=1;
for(register int i=1;i<=n;++i){
int p=-1;
for(register int j=i;j<=n;++j)
if(dta[i][j]){
p=j;
break;
}
if(!~p){
return 0;
}
if(p!=i){
_swap(i,p);
ans*=-1;
}
for(register int j=i+1;j<=n;++j){
while(dta[j][i]){
int tmp=dta[j][i]/dta[i][i];
for(register int k=i;k<=n;++k){
dta[j][k]-=1ll*tmp*dta[i][k]%mod;
dta[j][k]=(dta[j][k]%mod+mod)%mod;
}
if(!dta[j][i]){
break;
}
swap(dta[i],dta[j]);
ans*=-1;
}
}
ans=1ll*ans*dta[i][i]%mod;
}
return ans;
}
signed main(){
n=read()-1;
for(register int i=1;i<=n;++i){
int cnt=read();
while(cnt--){
int x=read(),y=read();
q[i].push_back(mp(x,y));
}
}
int ans=0;
for(register int i=1;i<(1<<n);++i){
memset(dta,0,sizeof(dta));
int cnt=0;
for(register int j=1;j<=n;++j){
if(!(i&(1<<(j-1)))){
continue;
}
++cnt;
for(register int k=0;k<q[j].size();++k){
int x=q[j][k].first,y=q[j][k].second;
++dta[x][y],++dta[y][x],--dta[x][x],--dta[y][y];
}
}
ans=(ans+((cnt&1)?-1:1)*det())%mod;
}
printf("%d\n",(ans%mod+mod)%mod);
return 0;
}
如果您没有看懂这篇题解，可以在评论区问我，我将会回答您的问题并且修改这篇题解，使它变得更加通俗易懂，服务更多的 $\text{OIer}$。
如果您看懂了这篇题解，可以点个赞，使这篇题解的排名上升，服务更多的 $\text{OIer}$。
