想不到也写不出, 在OI界普遍突出计数类题目时, 计数的困难到底出在哪呢?

Description

给一棵树, 求重映射的方案数, 使得这是一个一一映射, 且原来在树上相邻的点, 映射后在给出的图中依然有边相连.

Solution

膜题解来的想法.

我们硬点映射到哪些点, 从根向下每个点都选一下, 这样是肯定会撞的, 所以容斥. 对树上的父子边, 在图上也要选相邻的点.

状态就是$f_{i,j}$, 以$i$为根的子树, $i$映射到$j$的方案数.

然后根据奇偶性容斥一下.

并没有想得很明白这道题的思考过程.

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
82
83
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 18;
const int maxm = 2005;
const int maxs = (1 << 18);

int n, m, mtc[maxn][maxn];

struct edge {
  int to, nxt;
}e[maxm], e2[maxm];
int ptr, lnk[maxn], inq[maxn], qhd;
int ptr2, lnk2[maxn], rev[maxn];
ll ans, dp[maxn][maxn];

inline void add(int bgn, int end) {
  e[++ptr] = (edge){end, lnk[bgn]};
  lnk[bgn] = ptr;
}
inline void add2(int bgn, int end) {
  e2[++ptr2] = (edge){end, lnk2[bgn]};
  lnk2[bgn] = ptr2;
}
void dfs(int x, int f)  {
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == f) continue;
    dfs(y, x);
  }
  for (int j = 1; j <= qhd; ++j) {
    dp[x][j] = 1;
    // for (int p2 = lnk2[x]; p2; p2 = lnk2[x]); +
    for (int p = lnk[x]; p; p = e[p].nxt) {
      if (e[p].to == f) continue; 
      ll sum = 0;
      /*for (int q = lnk2[inq[j]]; q; q = e2[q].nxt) {
        sum += dp[e[p].to][rev[e2[q].to]];
      }*/
      for (int q = 1; q <= qhd; ++q) {
        if (mtc[inq[j]][inq[q]])
          sum += dp[e[p].to][q];
      }
      dp[x][j] *= sum;
      if (!dp[x][j]) break;
    }   
  }
}

int main() {
  scanf("%d%d", &n, &m);
  int u, v;
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &u, &v);
    mtc[u][v] = mtc[v][u] = 1;
  }
  for (int i = 1; i < n; ++i) {
    scanf("%d%d", &u, &v);
    add(u, v); 
    add(v, u);
  }
  int lim = (1 << n) - 1;
  for (int i = 1; i <= lim; ++i) {
    int st = i; qhd = 0;
    for (int j = 1; j <= n; ++j)
      if (st & (1 << (j - 1))) inq[++qhd] = j, rev[j] = qhd;
    ptr2 = 0; 
    memset(lnk2, 0, sizeof lnk2);
    /*for (int j = 1; j <= qhd; ++j)
      for (int k = 1; k <= qhd; ++k)
        if (mtc[inq[j]][inq[k]])
          add2(inq[j], inq[k]);//, add2(inq[k], inq[j]);*/
    dfs(1, 0);
    ll sum = 0;
    for (int j = 1; j <= qhd; ++j) sum += dp[1][j];
    if ((qhd & 1) == (n & 1)) ans += sum;
    else ans -= sum;
  }
  printf("%lld\n", ans);
  return 0;
}