P3349 小星星 【DP+容斥原理】

· · 题解

题意

给定一棵n个点的树T，和一张n个点m条边的图S，求有多少种点之间的对应关系的方案使得T为S的一个子图(等价于T中的每条边在某种点的对应关系下在S中都存在)

n\leq 17 \;

Solution

暴力

一种朴素的想法就是暴力的枚举每一种对应方式：

如下是n=3的情况，箭头左边是树中的每个点，右边对应的是图中的每个点

1->1, 2->2, 3->3

1->1, 2->3, 3->2

1->2, 2->3, 3->1

1->2, 2->1, 3->3

1->3, 2->1, 3->2

1->3, 2->2, 3->1

然后我们对每种情况我们再用O(n)的时间去判断树中的每条边是否在图中都存在即可

时间复杂度:O(n!\times n)

子集枚举DP

我们由题中得出T是一棵树，而其实如果T是一张图，用上面的暴力算法也是可做的，所以我们要思考如何利用树的特殊性质来挖掘隐含的细节

我们发现，题中的最大难点并不是处理T是S的子图这个限制条件，而是去计算点之间的对应关系，使得方案数不重不漏

所以我们得到了一个思路：在树T上进行树形DP

首先是设计状态

第一维：i，当然存的是以i为根的子树的信息

第二维：j，由于子树与外界之间还有限制条件，即：根节点i与其父亲在DP中在图中分别对应的点会有边的限制条件，所以j表示的是i在图中的对应点

第三维：k，由于树上的每个点只能唯一对应图中的点，所以如果只有前两维状态，我并不能知道目前这棵子树中每个点已经对应到了图中的哪些点，所以就可能导致我们会算重，即：树上的某几个点对应到了图中的同一个点上，所以k是表示我们目前选的点集，用一个压缩后的二进制数来表示

综上所述：f_{i,j,k}表示以i为根的子树，其中i对应的是图中的编号为j的点，且子树中已经选了集合为k的点，满足这棵子树是T中把集合为k的点在其中的对应点挑出来所对应的图的子图

呃，可能有点长，读者可以仔细地多读几遍再消化理解。

那么对于子图也就是边的这个限制条件，我们只需在DP的过程中判断i与它的每个儿子在图中是否有边即可。

因此状态转移方程也易得出：

f_{i,j,k}=\prod_{v\in son_u} \sum_{p\in Edge_{p,j}} \sum_{q\in k} f_{v,p,q}

时间复杂度：O(n^3\times 3^n)

\;

容斥原理优化

我们发现，上面的DP限制时间的主要因素是我们枚举了k，也就是我们目前选的点集。

这样导致时间暴增。

我们考虑如何去优化这个东西。

而仔细分析即可发现枚举k是为了防止算重，那我们不妨可以大胆的扔掉k，直接进行DP。

而这样的时间复杂度只有O(n^3)

但这样显然是错的。

所以我们考虑如何去减掉重复的情况。

我们发现，因为多个点对应图中的一个点。那么图中一定存在若干个点没有与树中的点对应

于是这个东西就可以容斥了：我们在图中枚举与树中对应的点有哪些，记为点集A，容斥系数显然为(-1)^{n-|A|}

则我们就可以通过这种方式，在DP时只需选我们枚举的点集进行状态转移即可。 时间复杂度：O(n^3 \times 2^n)

\;

Code

#include <bits/stdc++.h>
const int N = 20;
#define LL long long
int n, m, mp[N][N], c[N], len;
LL res, f[N][N];
std::vector<int> G[N];
void Dfs(int u, int fa)
{
    for(int i=1;i<=len;i++) f[u][c[i]] = 1;
    for(int i=0;i<G[u].size();i++)
    {
        int v = G[u][i];
        if(v == fa) continue;
        Dfs(v, u);
        for(int j=1;j<=len;j++)
        {
            LL now = 0;
            for(int k=1;k<=len;k++)
            {
                if(mp[c[j]][c[k]]) now += f[v][c[k]];
            }
            f[u][c[j]] *= now;
        }   
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        mp[u][v] = mp[v][u] = 1;
    }
    for(int i=1;i<n;i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v); G[v].push_back(u);
    }
    for(int S=1;S<(1<<n);S++)
    {
        memset(f, 0, sizeof(f));
        len = 0; int cnt = 0;
        for(int i=0;i<n;i++)
        {
            if(S >> i & 1) c[++len] = i + 1, cnt ++;
        }
        Dfs(1, 0);
        LL t;
        if((n - cnt) & 1) t = -1;
        else t = 1;
        for(int i=1;i<=len;i++) res += t * f[1][c[i]];
    }
    printf("%lld", res);
    return 0;
}