题解 P3349 【[ZJOI2016]小星星】

· · 题解

只能说是容斥原理好题啊……

但是直接想到容斥原理还是比较难的

(如果熟练的话不是很困难吧)

题目中要求我们求一个从树T到图S的映射，使得树上的两个点如果在树上右边，也会在图上有边，并且两个点不可以映射到同一个点上

暴力1

我们可以暴力枚举映射的种类，也就是说由于树上的点和图上的点是一一对应的关系，所以说我们可以用一个关于n的全排列来描述这个映射，qbl[i]表示树上的点i映射到的图上的点的编号

所以我们可以N!枚举所有的映射，之后就暴力的枚举每一条树边检查这个全排列是否合法就行了。(应该这个暴力还是非常好理解的)

暴力2

如果你足够熟练的话(参见ZJOI2015地震后的幻想乡&NOIP2017宝藏)你会发现全排列暴力的优化永远都是指向了一个东西——子集dp

大概是这样想的，我们按照树形dp的一般套路令dp[i]表示以i为根的子树映射方案，之后我们根据题目中的限制条件逐个添加限制维度

首先我们发现因为现在是在做树形dp了，所以只需考虑点i和父亲的关系了。

那么我们发现，为了满足映射后树上两点在图上仍有连边的限制，我们需要加一维j。

dp[i][j]表示以i为根的子树中的点，在点i映射为图上点j后所有的映射方案数

此时我们发现尽管可以满足映射后仍有连边的限制条件了，但是仍然无法满足不可以重复映射的限制条件，为此我们再加入一维k

dp[i][j][k]表示以i为根的子树中的点，在点i映射为图上点j且所有的映射之后构成了图上的点集K时，所有的映射方案数(这里的K是一个仅在二进制下有意义的01串，第p位为1表示p号点在集合中)

由于这只是一个暴力，不再赘述转移过程，大概是我们在新加入一个子树v的时候枚举v的父亲u的所有状态，对于u的一个状态(u,u',s)我们枚举s的补集的子集暴力的进行合并即可

很遗憾的是，本题n=17的超大数据使得我们这个复杂度是O(3^{n}n)的算法沦为了暴力，我们还需要考虑一些别的优化手段

正解：容斥原理

(请先阅读一下暴力2，这个做法对于正解的启发还是很大的)

假如说没有了那个不可以重复映射的限制呢？

那么我们可以删去最后一维,只保留dp[i][j]两维了，转移方程为

Dp_{u,i}=\prod_{v∈u.son}\sum_{j=1}^{n}Dp_{v,j}map_{i,j}

其中map_{i,j}表示的是图的邻接矩阵

之后我们可以暴力的dp出来这个映射数量，复杂度O(n^{3})

但是这样明显是错的，我们算出来的正确答案明显偏大了，因为这样做尽管一定包含了一一映射的所有合法情况，这时被映射的图点集都是全集S，但是还包含了一些不合法的情况，比如映射的集合小了一点，是S减去一个点。

为此我们删去图上的一个点，枚举删去之后可能产生的n个集合，还是按照上边的转移方程暴力的dp，并且减去这些方案数。

此时我们发现，这样dp出来的东西，有些映射可能不是恰好S-1的集合，而是还要小一点，比如S减去两个点，这些映射的集合在刚才的减法中被减了两次。

所以我们删去图上的任意两个点，枚举这样产生的C_{n}^{2}个集合，还是按照上边的转移方程暴力的dp，并且加上这个方案数

此时我们发现上边的加法会多加上S-3，所以枚举C_{n}^{3}个集合，暴力枚举之后减去方案数即可

以此类推，我们每次枚举一些集合，加上或者减去方案数，最后我们就可以不重不漏的计算出仅剩全集S的方案数了

我们一共要做2^{n}次O(n^{3})的树形dp，所以算法复杂度是O(2^{n}n^{3})凭借信仰即可过掉此题，(然而其实代码非常短)

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=22;typedef long long ll;
ll dp[N][N];ll res;bool book[N];int ban[N];int mp[N][N];
struct data{int v;int x;}e[N];int al[N];int ct;int n;int m;
inline void add(int u,int v){e[++ct].v=v;e[ct].x=al[u];al[u]=ct;}
void dfs(int x)
{
    book[x]=true;//暴力树d 
    for(int i=1;i<=n;i++){dp[x][i]=1;}
    for(int i=al[x],v=e[i].v;i;i=e[i].x,v=e[i].v)
    {
        if(book[v])continue;dfs(v);
        for(int j=1;j<=n;j++)
        {
            ll sum=0;//这里ban数组为0表示我们删去了这个点 
            for(int k=1;k<=n;k++){sum+=dp[v][k]*(mp[k][j]&ban[k]&ban[j]);}
            dp[x][j]*=sum;//按照转移方程去转移就好了 
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {int u;int v;scanf("%d%d",&u,&v);mp[u][v]=mp[v][u]=1;}
    for(int i=1;i<n;i++)
    {int u;int v;scanf("%d%d",&u,&v);add(u,v);add(v,u);}
    for(int k=1;k<=(1<<n)-1;k++)//实际操作的时候我们不必按照删几个点顺序枚举 
    {
        int siz=n;for(int i=1;i<=n;i++){ban[i]=0;}//按二进制串就行了 
        for(int i=1,p=k;p;p>>=1,i++){ban[i]=(p&1);siz-=(p&1);}
        for(int i=1;i<=n;i++){book[i]=false;}dfs(1);ll ret=0;
        for(int i=1;i<=n;i++){ret+=dp[1][i];}//看一下删了奇数个还是偶数个点 
        if(siz%2){res-=ret;}else {res+=ret;}//±上就行了 
    }printf("%lld",res);return 0;//拜拜程序~ 
}