题目大意
给定一个 $n$ 个结点 $m$ 条边的无向图和一棵 $n$ 个结点的树。现在要把树中的每个结点不重复，不遗漏地对应到图中的每个结点上，满足对应后形成的树是图的一棵生成树。求合法方案的数量。
数据范围：$n \le 17$。
思路分析
先考虑如果没有不重复，不遗漏这个条件怎么做。相当于给树上的每个结点都染个颜色，满足相邻的两个结点的颜色之间对应有边。记 $\text{dp}(i, j)$ 表示结点 $i$ 染成颜色 $j$ 的方案数，我们只要暴力枚举儿子的颜色即可转移。时间复杂度 $O(n ^ 3)$。
但是现在有 “所有颜色都要用到” 这个条件。考虑最一般的容斥原理。对于上述的 DP，我们记对于颜色集合 $A$ 算出的答案为 $f(A)$。我们只要每次枚举一个颜色的子集 $S$ 不能使用，然后把 $(-1)^{\vert A \vert} \times f(S - A)$ 贡献到答案里就行了，其中 $S$ 是颜色的全集。时间复杂度 $O(2 ^ n \times n ^ 3)$。
代码实现
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | |
6 | typedef long long ll; |
7 | const int maxn = 18; |
8 | int n, m, cur_msk; |
9 | ll dp[maxn + 3][maxn + 3]; |
10 | bool a[maxn + 3][maxn + 3]; |
11 | vector<int> G[maxn + 3]; |
12 | |
13 | void add(int u, int v) { |
14 | G[u].push_back(v); |
15 | } |
16 | |
17 | int bit_cnt(int x) { |
18 | return __builtin_popcount(x); |
19 | } |
20 | |
21 | void dfs(int u, int pa = 0) { |
22 | for (int i = 1; i <= n; i++) { |
23 | dp[u][i] = ~cur_msk >> (n - i) & 1; |
24 | } |
25 | for (int i = 0, v; i < G[u].size(); i++) { |
26 | v = G[u][i]; |
27 | if (v == pa) continue; |
28 | dfs(v, u); |
29 | for (int i = 1; i <= n; i++) if (dp[u][i]) { |
30 | ll sum = 0; |
31 | for (int j = 1; j <= n; j++) { |
32 | if (a[i][j]) sum += dp[v][j]; |
33 | } |
34 | dp[u][i] *= sum; |
35 | } |
36 | } |
37 | } |
38 | |
39 | int main() { |
40 | scanf("%d %d", &n, &m); |
41 | for (int i = 1, u, v; i <= m; i++) { |
42 | scanf("%d %d", &u, &v); |
43 | a[u][v] = a[v][u] = true; |
44 | } |
45 | for (int i = 1, u, v; i < n; i++) { |
46 | scanf("%d %d", &u, &v); |
47 | add(u, v), add(v, u); |
48 | } |
49 | ll ans = 0, res; |
50 | for (int msk = 0; msk < (1 << n) - 1; msk++) { |
51 | cur_msk = msk; |
52 | dfs(1); |
53 | res = 0; |
54 | for (int i = 1; i <= n; i++) { |
55 | res += dp[1][i]; |
56 | } |
57 | if (~bit_cnt(msk) & 1) { |
58 | ans += res; |
59 | } else { |
60 | ans -= res; |
61 | } |
62 | } |
63 | printf("%lld\n", ans); |
64 | return 0; |
65 | } |