structGRAPH { vector<vector<int> > s; voidClearEdges(){ for (auto& i : s) i.resize(0); } voidInit(int n){ ClearEdges(); s.resize(n+1); } voidAddUndi(int u, int v){ s[u].push_back(v); s[v].push_back(u); } };
GRAPH g, G; bitset<MAXN> ban; int n; LL f[MAXN][MAXN]; bool vis[MAXN]; voiddfs(int u){ vis[u] = true; for (int i = 0; i < n; ++i) { f[u][i] = ban[i] ? 0 : 1; } for (int v : g.s[u]) { if (vis[v]) continue; dfs(v); for (int i = 0; i < n; ++i) { if (ban[i]) continue; LL res = 0; for (int j : G.s[i]) { if (ban[j]) continue; res += f[v][j]; } f[u][i] *= res; } } } intmain(){ int m; cin >> n >> m; g.Init(n); G.Init(n);
while (m--) { int u, v; cin >> u >> v; --u; --v; G.AddUndi(u, v); } m = n-1; while (m--) { int u, v; cin >> u >> v; --u; --v; g.AddUndi(u, v); } LL ans = 0; for (int s = 0, maxs = 1 << n; s < maxs; ++s) { memset(vis, 0, n * sizeof(bool)); ban = s; dfs(0); LL now = 0; for (int j = 0; j < n; ++j) { now += f[0][j]; } if (ban.count() & 1) ans -= now; else ans += now; #if DEBUG for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cout << f[i][j] << ' '; } cout << endl; } cout << endl; #endif } cout << ans << endl;
scanf("%d", &n); --n; ma.row = ma.col = n; for (int i = 0; i < n; ++i) { int m; scanf("%d", &m); while (m--) { int u, v; scanf("%d%d", &u, &v); --u; --v; es[i].emplace_back(u, v); } } int ans = 0; for (int s = 0, maxs = 1 << n; s < maxs; ++s) { ma.clear(); for (int i = 0; i < n; ++i) { if (0 == (s & (1 << i))) { for (auto e : es[i]) { --ma.s[e.first][e.second]; --ma.s[e.second][e.first]; ++ma.s[e.first][e.first]; ++ma.s[e.second][e.second]; } } } int t = ma.det_laplacian(); if (__builtin_popcount(s) & 1) { SubMod(ans -= t, p); } else { AddMod(ans += t, p); } } printf("%d\n", ans);