题意

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

\(\;\)

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\)与它的每个儿子在图中是否有边即可。
因此状态转移方程也易得出：

时间复杂度：\(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;
} 

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

原文：https://www.cnblogs.com/czyty114/p/13455596.html