[ZJOI2016]小星星

Posted on In
  • $f[i][j]$:以i为根的子树，且i在原图中的映射为j时的方案数
  • $f[i][j]=\prod{u\in i.child}\Sigma ^n {k=1} f[u][k]*map[i][u]$
  • 但这样求出的dp值包括了不合法的重复选点状态。重复选了一个的，两个的……选了(1,2)的，(1,3)的……..
  • 容斥的套路呼之欲出。
  • 所以需要套用容斥定理，枚举删点方案dp。
  • $ps.$其实列出柿子之后首先想到的应该是状压，多加一维表示子集转移。
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
#include<cstdio>
typedef long long ll;

int N, M, cnt = 0;
int mp[20][20] = {0}, h[20] = {0};
ll dp[20][20];
struct E{
    int t, nxt;
}Ed[50];

void Add(int f, int t){Ed[++cnt].t = t; Ed[cnt].nxt = h[f]; h[f] = cnt;}

void Dfs(int u, int fa, int S)
{
    for (int i = 1; i <= N; i++) dp[u][i] = 1;
    for (int i = h[u]; i; i = Ed[i].nxt)
    {
        int v = Ed[i].t; if (v == fa) continue;
        Dfs(v, u, S);
        for (int j = 1; j <= N; j++)
        {
            if (((1 << (j - 1)) & S) == 0) {dp[u][j] = 0; continue;}
            ll sum = 0;
            for (int k = 1; k <= N; k++)
            {
                if (((1 << (k - 1)) & S) == 0) continue;
                sum += dp[v][k] * mp[k][j];
            }
            dp[u][j] *= sum;
        }
    }
}

int main()
{
    scanf("%d%d", &N, &M);
    int f, t; ll Ans = 0;
    for (int i = 1; i <= M; i++) {scanf("%d%d", &f, &t); mp[f][t] = mp[t][f] = 1;}
    for (int i = 1; i < N; i++) {scanf("%d%d", &f, &t); Add(f, t); Add(t, f);}
    for (int S = 1; S < (1 << N); S++)
    {
        int tot = 0, mul = 1;
        for (int j = 1; j <= N; j++)
            if ((S & (1 << (j - 1))) == 0) tot++;
        if (tot & 1) mul = -1;
        Dfs(1, 0, S); 
        for (int j = 1; j <= N; j++) Ans += 1LL * mul * dp[1][j];
    }
    printf("%lld", Ans);
    return 0;
}