Description：

给一棵树和一个图，问有几种把树上的点映射到图上的方式使得树上的边在原图中也有。

$1\leqslant n\leqslant17$

Solution：

考虑一种暴力树形 $DP$ ： $f[i][j][S]$ 表示 $i$ 的子树中 $i$ 对应的点是 $j$ 选取的集合为 $S$ 的方案数，不难发现时间复杂度瓶颈在 $S$ ，考虑 $S$ 的作用，不难发现是为了保证映射是一一对应的，那么我们可以尝试让映射不是一一对应的，然后再想办法求出最后的答案，这样直接 $DP$ 就不用加 $S$ 那一维，转移为： $$ f[k][j]=\prod_{i\in son[j]}\sum_{j'=1}^nf[i][j']\times map[j][j'] $$ 这样的话我们会计算了一些不合法的状态，这些状态中存在一些点没有树上的点映射到他，我们考虑容斥，也就是 $2^n$ 在原图上枚举删掉了哪个点，然后最后容斥，容斥的系数应该是 $\pm 1$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 20

int map[MAXN][MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

bool tag[MAXN];

long long f[MAXN][MAXN];

void dp(int k,int fa)

{

	for(int i = 1;i <= n;++i)

	{

		if(!tag[i])f[k][i] = 1;

		else f[k][i] = 0;

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		dp(e[i].to,k);

		for(int j = 1;j <= n;++j)if(!tag[j])

		{

			long long sum = 0;

			for(int j_ = 1;j_ <= n;++j_)if(!tag[j_])

			{

				sum += f[e[i].to][j_] * map[j][j_];

			}

			f[k][j] *= sum;

		}

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		a = rd();b = rd();

		map[a][b] = map[b][a] = 1;

	}

	for(int i = 1;i < n;++i)add(rd(),rd());

	int tot = (1 << n) - 1;

	long long ans = 0;

	for(int s = 0;s <= tot;++s)

	{

		int cnt = 0;

		memset(tag,false,sizeof(tag));

		for(int i = 1;i <= n;++i)if((s >> (i - 1)) & 1)tag[i] = true,++cnt;

		dp(1,0);

		long long sum = 0;

		for(int i = 1;i <= n;++i)sum += f[1][i];

		if(cnt % 2 == 0)ans += sum;

		else ans -= sum;

	}

	cout << ans << endl;

	return 0;

}