dalao教导我们,看到计数想容斥……
卡常策略:枚举顺序、除去无效状态、(树结构)
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int N=;
LL f[N][N];
int n,m,d[N][N],full;
bool yeah[N];
int st[N],cnt;
struct V{
int to,next;
}c[N<<];
int head[N],t;
inline void add(int x,int y){
c[++t].to=y,c[t].next=head[x],head[x]=t;
}
inline void dfs(int x,int fa){
register int i,j,k;LL sum=;
for(i=head[x];i;i=c[i].next)
if(c[i].to!=fa)
dfs(c[i].to,x);
for(i=;i<=n;++i){
if(!yeah[i]){
f[x][i]=;
continue;
}
f[x][i]=;
for(j=head[x];j;j=c[j].next)
if(c[j].to!=fa){
sum=;
for(k=;k<=cnt;++k)
if(d[i][st[k]])
sum+=f[c[j].to][st[k]];
f[x][i]*=sum;
}
}
}
int main(){
scanf("%d%d",&n,&m);
full=(<<n)-;
int i,j,x,y;
for(i=;i<=m;++i){
scanf("%d%d",&x,&y);
d[x][y]=d[y][x]=;
}
for(i=;i<n;++i){
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
LL ans=,sum;
for(i=;i<=full;++i){
cnt=,sum=;
for(j=;j<n;++j)
if(i&(<<j))yeah[j+]=true,st[++cnt]=j+;
else yeah[j+]=false;
dfs(,);
for(j=;j<=n;++j)
sum+=f[][j];
ans+=(((n-cnt)&)?-:)*sum;
}
printf("%lld\n",ans);
return ;
}