[Luogu 3349] [ZJOI2016]小星星

Posted on | In , | Views:

题目链接

Luogu 3349

做法

发现每个树上的点要对应不同的图上的点不好处理，我们考虑求树上的点可以对应相同的点。
我们以$g_i$表示树上的点可以对应相同的点，且对应的点中没出现状态$i$的方案数。
那么根据容斥我们知道最后的答案即为

所以我们先枚举状态i，在用$f_{j,k}$表示做完j的子树，j这个点的对应k的方案数。转移的话先枚举自己对应哪个点，然后分别计算每个子树的贡献即可。
总复杂度$O(2^n*n^3)$

代码

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (25)
using namespace std;
int n,m,x,y,tot,s,all;
int head[N],nxt[N<<1],son[N<<1],map[N][N];
LL f[N][N],ans,tt; 
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
inline void add(int x,int y){
    son[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
inline void dfs(int u,int fa){
    for (register int p=head[u];p;p=nxt[p]){
        if (son[p]!=fa) dfs(son[p],u);
    }
    for (register int i=1;i<=n;i++){
        if ((1<<i-1)&(all-s)) f[u][i]=1;
        else f[u][i]=0;
        for (register int p=head[u];p;p=nxt[p]){
            int v=son[p];
            if (v!=fa){
                tt=0;
                for (register int j=1;j<=n;j++){
                    if (map[i][j]) tt+=f[v][j];
                }    
                f[u][i]*=tt;    
            }
        }
    }
}
int main(){
    read(n),read(m);
    for (int i=1;i<=m;i++){
        read(x),read(y);
        map[x][y]=map[y][x]=1;
    }
    for (int i=1;i<n;i++){
        read(x),read(y);
        add(x,y),add(y,x);
    }
    all=(1<<n)-1;
    for (s=0;s<=all;s++){
        dfs(1,0);
        int k=__builtin_popcount(s);
        if (k&1){
            for (int i=1;i<=n;i++) ans-=f[1][i];
        }
        else for (int i=1;i<=n;i++) ans+=f[1][i];
    }
    printf("%lld",ans);
    return 0;
}