嘟嘟嘟
这题刚开始把(17!)想成了(2 ^ {17})，以为全排暴力枚举就行，然后写一半发现好像只能过(n leqslant 10)的点。
讨论正解之前，我们先想状压dp，毕竟这个数据范围就像状压。(dp[i][j][S])表示点(i)所在子树中，(i)对应(j)，子树的对应情况为(S)时的方案数。转移的时候枚举子树(v)和对应编号(k)，然后因为编号不能重，我们枚举(S)的补集的子集，然后暴力合并两个集合。
用子集dp的话，复杂度能达到(O(n ^ 3 3 ^ {n}))，仍然会超时。
然后题解就说，如果不考虑编号不能重的限制，我们就可以省去第三维了。
现在加上了限制，就可以用容斥。
考虑如果有一些点的编号被用了好多遍，那一定说明有一些点没被用到。那我们干脆直接删掉这些点然后再dp。于是(O(2 ^ n))枚举哪些点被删掉，然后根据个数奇偶性容斥一下即可。
相当于我们要求的是图中恰好有(n)个点都被映射的方案数=至少有(n)个点被映射的方案数-至少有(n - 1)个点被映射的方案数+至少有(n - 2)个点被映射-至少有(n - 3)个点……
总的来说，我们容斥的是图上被删去的点，即哪些点没有被映射，而不是树上哪些点不参与dp。（这里我纠结了好久）
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<assert.h>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 20;
In ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen("star3.in", "r", stdin);
freopen("ha.out", "w", stdout);
#endif
}
int n, m, G[maxn][maxn];
struct Edge
{
int nxt, to;
}e[maxn << 1];
int head[maxn], ecnt = -1;
In void addEdge(int x, int y)
{
e[++ecnt] = (Edge){head[x], y};
head[x] = ecnt;
}
int pos[maxn];
In bool dfs0(int now, int _f)
{
for(int i = head[now], v; ~i; i = e[i].nxt)
{
if((v = e[i].to) == _f) continue;
if(!G[pos[now]][pos[v]]) return 0;
if(!dfs0(v, now)) return 0;
}
return 1;
}
In void work0()
{
for(int i = 1; i <= n; ++i) pos[i] = i;
int ans = 0;
do
{
ans += dfs0(1, 0);
}while(next_permutation(pos + 1, pos + n + 1));
write(ans), enter;
}
bool vis[maxn];
ll dp[maxn][maxn], ans;
In void dfs(int now, int _f)
{
for(int i = 1; i <= n; ++i) dp[now][i] = 1;
for(int i = head[now], v; ~i; i = e[i].nxt)
{
if((v = e[i].to) == _f) continue;
dfs(v, now);
for(int j = 1; j <= n; ++j)
{
ll sum = 0;
for(int k = 1; k <= n; ++k)
sum += dp[v][k] * (G[j][k] & vis[j] & vis[k]);
dp[now][j] *= sum;
}
}
}
int main()
{
//MYFILE();
Mem(head, -1);
n = read(), m = read();
for(int i = 1; i <= m; ++i)
{
int x = read(), y = read();
G[x][y] = G[y][x] = 1;
}
for(int i = 1; i < n; ++i)
{
int x = read(), y = read();
addEdge(x, y), addEdge(y, x);
}
if(n <= 10) {work0(); return 0;} //开局写了个n!暴力……
for(int S = 1; S < (1 << n); ++S)
{
int tot = n;
for(int i = 1; i <= n; ++i)
if((S >> (i - 1)) & 1) vis[i] = 1, --tot;
else vis[i] = 0;
dfs(1, 0);
ll tp = 0;
for(int i = 1; i <= n; ++i) tp += dp[1][i];
if(tot & 1) ans -= tp;
else ans += tp;
}
write(ans), enter;
return 0;
}