好题。
首先一个显然的 DP 是 \(dp_{u, i, S}\) 表示 \(u\) 映射到 \(i\)，\(u\) 子树双射到 \(S\) 集合中的点的方案数，转移是 \(\mathcal{O}(n^3 3^n)\) 的，似乎精细实现常数很小可过。
考虑这个东西瓶颈在哪里，就是这个 \(s\)，要是不要求映射是一个双射，即我们设 \(f_s\) 为树上所有点到 \(s\) 中点的映射是一个满射的方案数，\(g_s\) 为树上所有点和 \(s\) 的映射的方案数，即 \(f_s\) 要求每个 \(s\) 中的点被映射了至少一次，\(g_s\) 则要求每个 \(s\) 中的点被映射了任意次。显然有子集反演的转移：
\[g_S = \sum\limits_{T \subseteq S} f_T
\]
\[f_S = \sum\limits_{T \subseteq S} (-1)^{|S| - |T|} g_T
\]
最后求的显然是 \(f_{2^n - 1}\)，而 \(g_s\) 还有一种转移，我们将 \(dp_{u, i, S}\) 设为 \(u\) 映射到 \(i\)，\(u\) 子树到 \(S\) 中的点的映射的方案数。\(g_S = \sum_{i \in S} dp_{0, i, S}\)，原因显然。所以最后不需要算其它 \(f_S\)，只要算 \(f_{2^n-1}\) 即可。
时间复杂度 \(\mathcal{O}(n^3 2^n)\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 17, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int n, m, s, tot, a[N], b[N][N];
ll dp[N][N], ans;
basic_string<int>e[N];
void dfs(int u, int fa) {for (int i = 0; i < tot; i++) dp[u][i] = 1;for (int v : e[u]) if (v != fa) {dfs(v, u);for (int i = 0; i < tot; i++) {ll tmp = 0;for (int j = 0; j < tot; j++) if (b[a[i]][a[j]]) tmp += dp[v][j];dp[u][i] *= tmp;}}
}
void main() {cin >> n >> m;for (int i = 1, u, v; i <= m; i++) {cin >> u >> v; u--; v--;b[u][v] = b[v][u] = 1;}for (int i = 1, u, v; i < n; i++) {cin >> u >> v; u--; v--;e[u] += v; e[v] += u;}for (; s < (1 << n); s++) {tot = 0;for (int i = 0; i < n; i++) if (s >> i & 1) a[tot++] = i;dfs(0, 0);ll g = 0;for (int i = 0; i < tot; i++) g += dp[0][i];ans += ((n - tot) & 1) ? -g : g;}cout << ans << '\n';
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T = 1;// cin >> T;while (T--) Loop1st::main();return 0;
}