博客食用更佳： https://www.cnblogs.com/czyty114/p/13455596.html

题意

$\;$
给定一棵$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;
}