「ZJOI2016」小星星 题解

题目描述

Link

题解

看数据范围 \(n \le 17\)，想到状态压缩，那必然是将点的状态作为 \(01\) 串。

那和最终的答案有什么关系呢。

我们用 \(dp_{i}\) 表示 \(i\) 的子树内的方案数量，考虑到一定要有连边的要求，再加一维 \(j\) 表示映射到的是哪一个点。

这时候会产生多个点映射到同一个点的情况，就是说原来的点集 \(S\)，映射到的是 \(1 \sim S\)，同理若是 \(S-1\) 则映射到 \(1 \sim S-1\)，那么我们枚举 \(S\)，用容斥原理算出真正的 \(S\)。

转移方程是 \(dp_{u, i} = \prod\limits_{v \in son(u)}\sum\limits_{j = 1}^n dp_{v, j}[\text{Unicom(u, v)}]\)。

理解一下，要转移首先要保证两个点联通，然后枚举点映射到哪一个原图上的点。每棵子树是独立的，根据乘法原理取 \(\prod\)。

然后套用一下容斥原理就好了，每次枚举选取/删除了哪些点。

#include <cstdio>
#include <cstring>
#include <vector>

#define int long long

const int N = 20;

int n, m;
std::vector<int> g[N], h[N];
bool vis[N];
int dp[N][N];

void Dfs(int u, int fa) {
  for (int i = 0; i < n; ++i)
    dp[u][i] = 1;
  for (auto v : h[u]) {
    if (v == fa)
      continue;
    Dfs(v, u);
    for (int i = 0; i < n; ++i) {
      int sum = 0;
      for (int j = 0; j < n; ++j)
        sum += dp[v][j] * (g[i][j] * vis[i] * vis[j]);
      dp[u][i] *= sum;
    }
  }
}

signed main() {
  scanf("%lld%lld", &n, &m);
  for (int i = 0; i < n; ++i)
    g[i].resize(n);
  for (int i = 1, u, v; i <= m; ++i) {
    scanf("%lld%lld", &u, &v), --u, --v;
    g[u][v] = g[v][u] = 1;
  }
  for (int i = 2, u, v; i <= n; ++i) {
    scanf("%lld%lld", &u, &v), --u, --v;
    h[u].push_back(v), h[v].push_back(u);
  }
  int ans = 0;
  for (int mask = 1; mask < (1 << n); ++mask) {
    int cnt = n;
    memset(vis, false, sizeof(vis));
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; ++i)
      if (mask >> i & 1)
        vis[i] = true, --cnt;
    Dfs(0, 0);
    int res = 0;
    for (int i = 0; i < n; ++i)
      res += dp[0][i];
    ans += ((cnt & 1) ? -1 : 1) * res;
    // printf("%lld %lld\n", mask, res);
  }
  printf("%lld\n", ans);
  return 0;
}