看一看数据范围，求生成树个数毫无疑问直接上矩阵树定理。
但是要求每条边都属于不同公司就很难直接实现。
按套路上容斥：
如果直接将几个公司的修路列表加进矩阵里的话，求出来的是“只使用”这些边的生成树个数。
很明显上容斥之后就会直接变成“只使用”且“每个都被使用”的个数。
正好符合题目要求的生成树的n-1条边分属于n-1个公司。
#include<bits/stdc++.h>
using namespace std;
template<typename TP>inline void read(TP &tar)
{
TP ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10+(ch-'0');ch=getchar();}
tar=ret*f;
}
namespace RKK
{
const int N=20,mo=1000000007;
void doadd(int &a,int b){if((a+=b)>=mo)a-=mo;}
int fpow(int a,int p){int ret=1;while(p){if(p&1)ret=1ll*ret*a%mo;a=1ll*a*a%mo,p>>=1;}return ret;}
int n,m,b;
int ma[N][N];
int calc()
{
b=m;int f=1;
for(int l=1;l<=b;l++)
{
int g=l;for(;g<=b&&!ma[g][l];g++);if(g>b) return 0;
if(g!=l){for(int j=l;j<=b;j++) swap(ma[l][j],ma[g][j]);f=-f;}
for(g=l+1;g<=b;g++)
{
int k=1ll*ma[g][l]*fpow(ma[l][l],mo-2)%mo;
for(int j=l;j<=b;j++) doadd(ma[g][j],mo-1ll*ma[l][j]*k%mo);
}
}
if(f==-1) f=mo-1;
for(int i=1;i<=b;i++) f=1ll*f*ma[i][i]%mo;
return f;
}
int elst[N][(N*N)<<1];
int main()
{
read(n),m=n-1;
for(int i=0;i<m;i++)
{
read(elst[i][0]);
for(int j=1;j<=elst[i][0];j++) read(elst[i][j*2-1]),read(elst[i][j*2]);
}
int ans=0;
for(int s=0;s<(1<<m);s++)
{
int f=1;
memset(ma,0,sizeof(ma));
for(int i=0;i<m;i++)if((s>>i)&1)
{
for(int j=1,x,y;j<=elst[i][0];j++)
{
x=elst[i][j*2-1],y=elst[i][j*2];
ma[x][x]++,ma[y][y]++;
doadd(ma[x][y],mo-1),doadd(ma[y][x],mo-1);
}
}else f=-f;
f=calc()*f;if(f<0) f=mo+f;
doadd(ans,f);
}
printf("%d\n",ans);
return 0;
}
}
int main(){return RKK::main();}bzoj4596/luoguP4336 [SHOI2016]黑暗前的幻想乡(矩阵树定理，容斥)
原文：https://www.cnblogs.com/rikurika/p/12253103.html