题目链接：
http://www.lydsy.com/JudgeOnline/problem.php?id=4455
考虑枚举原图中我选择哪一些点，然后用树中的点匹配我枚举的集合中的点，匹配的点可以重复，如果两个点再树上有边，那么他们在图中也一定要有边。
枚举原图中的集合状态，这一步是${O(2^{n})}$的令${f[i][j]}$表示第$i$个点匹配了原图中第$j$个点的方案，一个${O(n^{3})}$树形DP可以求出。
但是因为匹配的点可以重复，这样的话匹配不重的方案数就是答案，用所有方案减去有重的，就是一个容斥了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 21
#define llg int
#define LL long long
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,q[maxn],w,g[maxn][maxn];
LL ans,f[maxn][maxn];
vector<llg>a[maxn]; void jy(llg x)
{
w=;
for (llg i=;i<=n;i++)
{
if (x&) q[++w]=i;
x>>=;
}
} void init()
{
llg x,y;
cin>>n>>m;
for (llg i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
g[x][y]=g[y][x]=;
}
for (llg i=;i<n;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y),a[y].push_back(x);
}
} void dp(llg x,llg fa)
{
llg E=a[x].size();
for (llg i=;i<=w;i++) f[x][q[i]]=;
for (llg i=;i<E;i++)
{
llg v=a[x][i];
if (v==fa) continue;
dp(v,x);
for (llg j=;j<=w;j++)
{
LL tot=;
for (llg k=;k<=w;k++) if (g[q[j]][q[k]]) tot+=f[v][q[k]];
f[x][q[j]]*=tot;
}
}
} int main()
{
yyj("star");
init();
for (llg S=;S<(<<n);S++)
{
jy(S);
dp(,);
LL sum=;
for (llg i=;i<=w;i++) sum+=f[][q[i]];
if ((w&)==(n&)) ans+=sum;else ans-=sum;
}
cout<<ans;
return ;
}