容斥+树形dp
枚举集合S，要求所有点只能和S中的点配对，可以多个点匹配一个点。f[x][y]表示x匹配的是y，以x为根的子树的方案数，转移很简单，稍微认真思考就知道。 #include <bits/stdc++.h> #define gc getchar() #define ll long long #define N 18 #define M N*N/2 using namespace std; int n,m,x,y,first[N],First[N],Number,number,q[N],w; int mp[N][N],fa[N]; ll dp[N][N],Ans; struct edge { int from,to,next; void add(int x,int y) { from=x,to=y,next=first[x],first[x]=number; } }e[M]; int read() { int x=1; char ch; while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1; int s=ch-'0'; while (ch=gc,ch<='9'&&ch>='0') s=s*10+ch-'0'; return s*x; } void tree_dp(int x) { for (int i=1;i<=w;i++) dp[x][q[i]]=1; for (int i=first[x];i;i=e[i].next) if (fa[x]!=e[i].to) { fa[e[i].to]=x; tree_dp(e[i].to); for (int j=1;j<=w;j++) { ll sum=0; for (int k=1;k<=w;k++) if (mp[q[j]][q[k]]) sum+=dp[e[i].to][q[k]]; dp[x][q[j]]*=sum; } } } int main() { n=read(),m=read(); for (int i=1;i<=m;i++) { x=read(),y=read(); mp[x][y]=mp[y][x]=1; } for (int i=1;i<n;i++) { x=read(),y=read(); e[++number].add(x,y); e[++number].add(y,x); } Ans=0; for (int i=1;i<(1<<n);i++) { memset(dp,0,sizeof(dp)); w=0; for (int k=i,j=1;k;k>>=1,j++) if (k&1) q[++w]=j; tree_dp(1); ll sum=0; for (int j=1;j<=w;j++) sum+=dp[1][q[j]]; if ((n&1)==(w&1)) Ans+=sum; else Ans-=sum; } printf("%lld\n",Ans); return 0; }