LibreOJ 2091 「ZJOI2016」小星星

发表于 | 分类于

Description

给定一棵\(n\)个点的树\(T\)，以及一个\(n\)个点\(m\)条边的简单无向图\(G\)，要求你将\(T\)“镶嵌”在\(G\)中（即求一个两者点集的双射，使得\(T\)中的边能对应成\(G\)中的边），求方案数。

\(n\leq 17\)。

Solution

先考虑一个树形DP……\(f_{i, j}\)表示树中的\(i\)对应图中的\(j\)时，\(i\)所在子树的对应方案数，转移的话就枚举每个儿子对应哪个点就行了。很显然这是一个时间复杂度\(O(n^3)\)的DP，但是很不幸这个算法是可能搞出来多个点对应到一个点的情况……

那么我们考虑容斥，注意到发生重复等价于有图内的点没法被对应，因此问题就转化为图内的任何点都要被对应。我们考虑当对应到的图的点集事全集的时候，至少有零个图内的点无法被对应；如果说对应的图的点集大小为\(n - 1\)时，至少有一个图内的点无法被对应；大小为\(n - 2\)时，至少有两个无法被对应……以此类推。我们最后想要求的是恰好零个点没被对应，这就是一个经典容斥了……

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <forward_list>
const int maxn = 20;
bool G[maxn][maxn];
std::vector<int> T[maxn];
void ins_edge(int u, int v) {
  T[u].push_back(v); T[v].push_back(u);
}

using ll = long long;
ll f[maxn][maxn]; int n;
bool rec[maxn];
void dp(int u, int fa) {
  for(const int &v : T[u]) {
    if(v != fa) dp(v, u);
  }
  for(int i = 1; i <= n; i ++) {
    if(rec[i]) {
      f[u][i] = 1;
    } else {
      f[u][i] = 0;
    }
  }
  for(int i = 1; i <= n; i ++) {
    if(!rec[i]) continue;
    for(const int &v : T[u]) {
      if(v != fa) {
        ll s = 0;
        for(int j = 1; j <= n; j ++) {
          if(G[i][j]) s += f[v][j];
        }
        f[u][i] *= s;
      }
    }
  }
}
ll calc() {
  ll ans = 0;
  for(int s = 2; s < (1 << n); s ++) {
    if((s & (s - 1)) == 0) continue;
    memset(rec, 0, sizeof(rec));
    int sz = 0;
    for(int i = 1; i <= n; i ++) {
      if((1 << (i - 1)) & s) {
        sz ++; rec[i] = true;
      }
    }
    dp(1, -1);
    ll th = 0;
    for(int i = 1; i <= n; i ++) {
      th += f[1][i];
    }
    if(1 & (n - sz)) th = -th;
    ans += th;
  }
  return ans;
}

int main() {
  int m; scanf("%d%d", &n, &m);
  if(n == 1) {
    puts("1"); return 0;
  }
  for(int i = 1; i <= m; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    G[u][v] = G[v][u] = true;
  }
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    ins_edge(u, v);
  }
  printf("%lld\n", calc());
  return 0;
}