BZOJ4455 [ZJOI2016]小星星

题意

小Y是一个心灵手巧的女孩子,她喜欢手工制作一些小饰品。她有$n$颗小星星,用$m$条彩色的细线串了起来,每条细线连着两颗小星星。有一天她发现,她的饰品被破坏了,很多细线都被拆掉了。这个饰品只剩下了$n-1$条细线,但通过这些细线,这颗小星星还是被串在一起,也就是这些小星星通过这些细线形成了树。小Y找到了这个饰品的设计图纸,她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连,那么要求对应的小星星原来的图纸上也有细线相连。小Y想知道有多少种可能的对应方式。只有你告诉了她正确的答案,她才会把小饰品做为礼物送给你呢。
$n \leqslant 17,m \leqslant \frac{n(n-1)}{2}$。

题解

首先看到题,不难想到一个$O(n^3)$的错误的树形DP,即记$dp[i][j]$表示考虑了以$i$为子树的映射情况,且$i$号点映射到原图中的$j$号点的方案数。但这个DP是有问题的,因为你可能会把多个树上的点映射到图中的同一个点上去,于是我们考虑容斥。设$dp[S][i][j]$表示只将树上的点映射到集合$S$的方案数,那么再在每一次计算时乘上一个容斥系数即可。这样时间复杂度是$O(2^n \times 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
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=17+3;
int G[maxn][maxn],to[maxn<<1],nex[maxn<<1],beg[maxn];
ll dp[maxn][maxn];
int e,n;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline void add(int x,int y){
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}
inline void Dp(int x,int fa,int Set){
int i,j,k;
for(i=beg[x];i;i=nex[i]){
if(to[i]==fa)continue;
Dp(to[i],x,Set);
}
for(i=1;i<=n;i++){
if(!(Set & (1<<(i-1))))continue;
ll tot=1;
for(j=beg[x];j;j=nex[j]){
if(to[j]==fa)continue;
ll sum=0;
for(k=1;k<=n;k++){
if(!G[i][k])continue;
sum+=dp[to[j]][k];
}
tot*=sum;
}
dp[x][i]=tot;
}
}
int main(){
int i,j,k,m;
#ifndef ONLINE_JUDGE
freopen("BZOJ4455.in","r",stdin);
freopen("BZOJ4455.out","w",stdout);
#endif
n=read();m=read();
for(i=1;i<=m;i++){
int x,y;
x=read();y=read();
G[x][y]=G[y][x]=1;
}
for(i=1;i<n;i++){
int x,y;
x=read();y=read();
add(x,y);add(y,x);
}
ll ans=0;
for(i=1;i<(1<<n);i++){
memset(dp,0,sizeof(dp));
Dp(1,0,i);
int sum=__builtin_popcount(i);
ll tot=0;
for(j=1;j<=n;j++)tot+=dp[1][j];
if((n-sum)%2==1)ans-=tot;
else ans+=tot;
}
printf("%lld\n",ans);
return 0;
}