题目链接

LOJ：

洛谷：

Solution

这题很像[，注意到如果没有每个边集选一条边的限制的话，直接就是一个果的\(\rm matrix \ tree\)定理。

那么有这个限制我们算出来的生成树个数就会有不合法的情况，即一个边集里选多条边，或者说没有用到\(n-1\)个边集。

那么我们可以算出\(f[s]\)表示至考虑\(s\)状态的这些边集，随便选的生成树个数，那么这些方案最多也就选到\(s\)这些边集。

我们可以参照上题进行容斥，对每个\(f\)乘个\((-1)^{n-1-cnt(s)}\)的系数加起来就好了。

#include
    
     using namespace std;void read(int &x) {    x=0;int f=1;char ch=getchar();    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;}void print(int x) {    if(x<0) putchar('-'),x=-x;    if(!x) return ;print(x/10),putchar(x%10+48);}void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}#define lf double#define ll long long #define pii pair
     
      #define vec vector
      
       #define pb push_back#define mp make_pair#define fr first#define sc second#define FOR(i,l,r) for(int i=l, i##_r=r;i<=i##_r;i++) const int maxn = 18;const int inf = 1e9;const lf eps = 1e-8;const int mod = 1e9+7;int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}int del(int x,int y) {return x-y<0?x-y+mod:x-y;}int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;}int qpow(int a,int x) {    int res=1;    for(;x;x>>=1,a=mul(a,a)) if(x&1) res=mul(res,a);    return res;}int inv(int x) {return qpow(x,mod-2);}int n,r[maxn][maxn],a[18][400],b[18][400],ans;void ins(int u,int v) {r[u][u]++,r[v][v]++,r[u][v]--,r[v][u]--;}int calc() {    int tmp=1;    FOR(i,1,n-1) {        if(!r[i][i])            FOR(j,i+1,n-1) if(r[j][i]) {                FOR(k,1,n-1) swap(r[i][k],r[j][k]);tmp=-tmp;break;            }        FOR(j,1,i-1) {            int res=mul(r[i][j],inv(r[j][j]));            FOR(k,1,n-1) r[i][k]=del(r[i][k],mul(res,r[j][k]));        }    }if(tmp==-1) tmp=mod-1;    FOR(i,1,n-1) tmp=mul(tmp,r[i][i]);    return tmp;}void solve(int s) {    memset(r,0,sizeof r);    FOR(i,1,n-1) if(s&(1<<(i-1)))        FOR(j,1,a[i][0]) ins(a[i][j],b[i][j]);    ans=((n-1-__builtin_popcount(s))&1?del:add)(ans,calc());}int main() {    read(n);    FOR(i,1,n-1) {        read(a[i][0]);        FOR(j,1,a[i][0]) read(a[i][j]),read(b[i][j]);    }FOR(s,1,(1<<(n-1))-1) solve(s);    write(ans);    return 0;}