题面：求一棵树嵌入一张图里有多少种不同的方案数
题解：首先是一个树形DP。dp[x][s]表示以x为根的子树使用了s这个集合。然而发现这个转移要枚举子集，复杂度好像很高的样子，我也不知道加了神奇的优化能不能过去。
然后我们发现如果一个数可以同时对应多个数就可以避免枚举子集，现在假设不用一一对应，状态就变成了dp[x][s]表示x这个点对应了s这个点，然后转移的话只要枚举它儿子对应着哪个点就行了。
然而我们发现这样计算会多出不合法的方案来，所以考虑用容斥。减去有一个点没被用过的方案数，加上两个点没被用过的方案数......。首先枚举哪些点用了，然后进行DP。由于避免了枚举子集，所以复杂度从3^n*n^2变成了2^n*n^3。然后只要不写得太暴力应该都能过去的。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,cnt,num,map[1005][1005],last[1000005],a[1000005],b[1000005];
long long f[18][18],ans;
struct node{
int to,next;
}e[1000005];
void add(int a,int b){
e[++cnt].to=b;
e[cnt].next=last[a];
last[a]=cnt;
}
void dp(int x,int fa){
for (int i=1; i<=num; i++) f[x][i]=1;
for (int i=last[x]; i; i=e[i].next){
int V=e[i].to;
if (V==fa) continue;
dp(V,x);
for (int c=1; c<=num; c++){
long long sum=0;
for (int d=1; d<=num; d++) if (map[b[c]][b[d]]) sum+=f[V][d];
f[x][c]*=sum;
}
}
}
void dfs(int t,int ss){
if (t>n){
num=0;
for (int i=1; i<=n; i++)
if (a[i]) b[++num]=i;
for (int i=1; i<=num; i++)
for (int j=1; j<=num; j++)
f[i][j]=0;
dp(1,0);
for (int i=1; i<=num; i++) ans+=1ll*ss*f[1][i];
return;
}
a[t]=0;
dfs(t+1,-ss);
a[t]=1;
dfs(t+1,ss);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1; i<=m; i++){
int x,y;
scanf("%d%d",&x,&y);
map[x][y]=map[y][x]=1;
}
for (int i=1; i<n; i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs(1,1);
printf("%lld
",ans);
return 0;
}