题目链接：小星星
首先有个暴力很好想。令(f_{i,j,S})表示把(i)这棵子树对应到原图中的(S)集合，(i)号点对应到了(j)号点的方案数。这玩意儿复杂度是(O(3^nn^3))的，但是稍微加点优化就能有(40)分。
然后看看这个转移的方程，实际上就是集合或卷积。于是我们就可以优化转移了，总复杂度就变成了(O(2^nn^4))。
然后我们发现，我们完全可以(dp)的整个过程都在(n)维前缀和类似物下进行，最后再用差分类似物弄回来就可以了。于是复杂度成功降为(O(2^nn^3))。
这个复杂度算出来好像是会(TLE)的样子……但是复杂度是不满的，所以我们卡一卡常数就能(AC)了。
我写的东西比较丑陋，只能卡着时间过去……然后去膜了一发王队的代码，发现空间复杂度都可以只需(O(2^n))……只要每次先枚举状态(S)，再对整棵树进行(dp)就可以了。而且这样做常数也非常之小。
至于正解的容斥，就先坑在这里吧。
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define N 17
using namespace std;
typedef long long llg;
int n,m,lim,mp[1<<N],G[N];
llg f[N][N],res,g[1<<N];
int h[N][N],lh[N];
void dfs(int u,int fa,int S){
for(int i=S;i;i-=i&(-i)) f[u][mp[i&(-i)]]=1;
for(int l=0;l<lh[u];l++){
if(h[u][l]==fa) continue;
dfs(h[u][l],u,S);
for(int i=S,x;i;i-=i&(-i)){
res=0; x=mp[i&(-i)];
for(int j=G[x]&S;j;j-=j&(-j))
res+=f[h[u][l]][mp[j&(-j)]];
f[u][x]*=res;
}
}
}
int main(){
File("a");
scanf("%d %d",&n,&m); lim=1<<n;
for(int i=1,u,v;i<=m;i++){
scanf("%d %d",&u,&v); u--,v--;
G[u]|=1<<v; G[v]|=1<<u;
}
for(int i=2,u,v;i<=n;i++){
scanf("%d %d",&u,&v); u--,v--;
h[u][lh[u]++]=v,h[v][lh[v]++]=u;
}
for(int i=0;i<n;i++) mp[1<<i]=i;
for(int i=1;i<lim;i++){
dfs(0,-1,i);
for(int j=0;j<n;j++)
if((i>>j)&1) g[i]+=f[0][j];
}
for(int i=0;i<n;i++)
for(int j=0;j<lim;j++)
if((j>>i)&1) g[j]-=g[j^(1<<i)];
printf("%lld",g[lim-1]);
return 0;
}
BZOJ提交网址：BZOJ 4455 小星星