自然地想到容斥原理
然后套个矩阵树就行了
求行列式的时候只有换行要改变符号啊QAQ
复杂度为\(O(2^n * n^3)\)
#include#include #include #include using namespace std;#define ri register int#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)#define drep(io, ed, st) for(ri io = ed; io >= st; io --)const int sid = 20;const int mod = 1e9 + 7;inline void inc(int &a, int b) { a += b; if(a >= mod) a -= mod; }inline void dec(int &a, int b) { a -= b; if(a < 0) a += mod; }inline int mul(int a, int b) { return 1ll * a * b % mod; }inline int inv(int a) { int ret = 1; for(int k = mod - 2; k; k >>= 1, a = mul(a, a)) if(k & 1) ret = mul(ret, a); return ret;} int N, ans;int M[sid], G[sid][sid];struct edge { int u, v; } E[sid][400];inline int Guass(int n) { int sign = 1; rep(i, 1, n) { int pos = i; rep(j, i + 1, n) if(G[j][i]) pos = j; swap(G[i], G[pos]); if(i != pos) sign *= -1; if(!G[i][i]) return 0; int Inv = inv(G[i][i]); rep(j, i + 1, n) { int t = mul(G[j][i], Inv); rep(k, i, n) dec(G[j][k], mul(G[i][k], t)); } } int ret = 1; rep(i, 1, n) ret = mul(ret, G[i][i]); if(sign == 1) return ret; else return mod - ret;}inline int calc(int S) { memset(G, 0, sizeof(G)); rep(i, 1, N - 1) { if(!(S & (1 << i - 1))) continue; rep(j, 1, M[i]) { int u = E[i][j].u, v = E[i][j].v; inc(G[u][u], 1); inc(G[v][v], 1); dec(G[u][v], 1); dec(G[v][u], 1); } } return Guass(N - 1);}inline void dfs(int o, int S, int num) { if(o == N) { if((N - 1 - num) & 1) dec(ans, calc(S)); else inc(ans, calc(S)); return; } dfs(o + 1, S, num); dfs(o + 1, S | (1 << o - 1), num + 1);} int main() { freopen("pp.in", "r", stdin); cin >> N; rep(i, 1, N - 1) { cin >> M[i]; rep(j, 1, M[i]) cin >> E[i][j].u >> E[i][j].v; } dfs(1, 0, 0); printf("%d\n", ans); return 0;}