uoj185

挺不错的容斥题

// Author: 23forever
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
typedef long long LL;
const int MAXN = 18;
using namespace std;

inline int read() {
  int x = 0, w = 1; char c = ' ';
  while (!isdigit(c)) {
    c = getchar();
    if (c == '-') w = -1;
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  return x * w;
}

int n, m;
LL dp[MAXN + 5][MAXN + 5];
bool ga[MAXN + 5][MAXN + 5], banned[MAXN + 5];

namespace tree {
const int MAXM = 2 * MAXN;

int tot, head[MAXN + 5];
struct Edge {
  int to, nxt;
  Edge() {}
  Edge(int _to, int _nxt) : to(_to), nxt(_nxt) {}
} edge[MAXM + 5];
void init() {
  tot = 0, memset(head, -1, sizeof(head));
}
void addEdge(int u, int v) {
  edge[tot] = Edge(v, head[u]), head[u] = tot++;
  edge[tot] = Edge(u, head[v]), head[v] = tot++;
}

void dfs(int u, int fa) {
  for (int i = 1; i <= n; ++i) dp[u][i] = 1;

  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (v == fa) continue;
    dfs(v, u);

    for (int j = 1; j <= n; ++j) {
      if (banned[j]) continue;

      LL cnt = 0;
      for (int k = 1; k <= n; ++k) {
        if (ga[j][k] && !banned[k]) cnt += dp[v][k];
      }
      dp[u][j] *= cnt;
    }
  }
}

}

void init() {
  n = read(), m = read();
  tree::init();

  for (int i = 1; i <= m; ++i) {
    int u = read(), v = read();
    ga[u][v] = ga[v][u] = true;
  }
  for (int i = 1; i < n; ++i) {
    int u = read(), v = read();
    tree::addEdge(u, v);
  }
}

int main() {
#ifdef forever23
  freopen("test.in", "r", stdin);
  freopen("test.out", "w", stdout);
#endif  
  init();

  LL ans = 0;
  for (int s = 0; s < (1 << n); ++s) {
    memset(banned, false, sizeof(banned));

    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (s >> i & 1) {
        banned[i + 1] = true; 
        ++cnt;
      }
    }
    tree::dfs(1, 0);

    LL sum = 0;
    for (int i = 1; i <= n; ++i) {
      if (!banned[i]) sum += dp[1][i];
    }
    ans += (cnt & 1) ? -sum : sum;
  }

  printf("%lld\n", ans);

#ifdef forever23
    printf("Running Time = %d ms\n", int(clock() * 1000.0 / CLOCKS_PER_SEC));
#endif
  return 0;
}

本博客所有文章均采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处
本文链接:https://23forever.com/2019/11/15/uoj185/