题目传送门：P3349 [ZJOI2016] 小星星。
考虑一个暴力 dp，设 \(f_{i,j,s}\) 表示以 \(i\) 为根的子树，且 \(a_i=j\) 且 \(i\) 的子树选择的集合为 \(s\) 的方案数。
转移的话直接钦定儿子选择什么。
这样做是 \(O(n^33^n)\) 的，无法通过。
如果我们将 \(s\) 从状态中删去，我们显然会算重，那么我们考虑容斥，枚举 \(s\) 且每个 \(a\) 都只能在 \(s\) 中选取（忽略排列的限制），相当于钦定了选择的范围，那么这样就可以 dp 了，然后随便容斥一下即可。
#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N=20,M=1<<17;
inline int read(){char c=getchar();int f=1,ans=0;while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();return ans*f;
}
int vis[N][N],n,m;
vector<int>g[N];
int f[N][N];
vector<int>tmp;
inline int get(int x){int ans=0;while(x) ans++,x&=x-1;return ans;}
void dfs(int u,int fa){for (auto i:tmp) f[u][i]=1;for (auto v:g[u]) if (v^fa){dfs(v,u);for (auto i:tmp){int sum=0;for (auto j:tmp) if (j!=i&&vis[i][j]) sum+=f[v][j];f[u][i]*=sum;}}
}
main(){n=read(),m=read();for (int i=1,u,v;i<=m;i++) u=read(),v=read(),vis[u][v]=vis[v][u]=1;for (int i=1,u,v;i<n;i++) u=read(),v=read(),g[u].push_back(v),g[v].push_back(u);int ans=0;for (int i=0;i<(1<<n);i++){for (int i=0;i<=n+1;i++) for (int j=0;j<=n+1;j++) f[i][j]=0;tmp.clear();for (int j=0;j<n;j++) if ((i>>j)&1) tmp.push_back(j+1);dfs(1,0);int sum=0;for (auto i:tmp) sum+=f[1][i];if (n-get(i)&1) ans-=sum;else ans+=sum;}cout <<ans;return 0;
}