【UOJ】【BZOJ】 [Zjoi2016]小星星

题目链接：

http://www.lydsy.com/JudgeOnline/problem.php?id=4455

考虑枚举原图中我选择哪一些点，然后用树中的点匹配我枚举的集合中的点，匹配的点可以重复，如果两个点再树上有边，那么他们在图中也一定要有边。

枚举原图中的集合状态，这一步是${O(2^{n})}$的令${f[i][j]}$表示第$i$个点匹配了原图中第$j$个点的方案，一个${O(n^{3})}$树形DP可以求出。

但是因为匹配的点可以重复，这样的话匹配不重的方案数就是答案，用所有方案减去有重的，就是一个容斥了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<cstring>
 8 using namespace std;
 9 #define maxn 21
10 #define llg int
11 #define LL long long
12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
13 llg n,m,q[maxn],w,g[maxn][maxn];
14 LL ans,f[maxn][maxn];
15 vector<llg>a[maxn];
16 
17 void jy(llg x)
18 {
19     w=0;
20     for (llg i=1;i<=n;i++) 
21     {
22         if (x&1) q[++w]=i;
23         x>>=1;
24     }
25 }
26 
27 void init()
28 {
29     llg x,y;
30     cin>>n>>m;
31     for (llg i=1;i<=m;i++)
32     {
33         scanf("%d%d",&x,&y);
34         g[x][y]=g[y][x]=1;
35     }
36     for (llg i=1;i<n;i++)
37     {
38         scanf("%d%d",&x,&y);
39         a[x].push_back(y),a[y].push_back(x);
40     }
41 }
42 
43 void dp(llg x,llg fa)
44 {
45     llg E=a[x].size();
46     for (llg i=1;i<=w;i++) f[x][q[i]]=1;
47     for (llg i=0;i<E;i++)
48     {
49         llg v=a[x][i];
50         if (v==fa) continue;
51         dp(v,x);
52         for (llg j=1;j<=w;j++)
53         {
54             LL tot=0;
55             for (llg k=1;k<=w;k++) if (g[q[j]][q[k]]) tot+=f[v][q[k]];
56             f[x][q[j]]*=tot;
57         }
58     }
59 }
60 
61 int main()
62 {
63     yyj("star");
64     init();
65     for (llg S=1;S<(1<<n);S++)
66     {
67         jy(S);
68         dp(1,0);
69         LL sum=0;
70         for (llg i=1;i<=w;i++) sum+=f[1][q[i]];
71         if ((w&1)==(n&1)) ans+=sum;else ans-=sum;
72     }
73     cout<<ans;
74     return 0;
75 }

【UOJ】【BZOJ】 [Zjoi2016]小星星

推荐阅读