来一点更清楚的、实现方面的东西。
做法同 这篇，他的实现很优美但略微繁琐了些。
枚举 \(T\) 的形态，发现这个匹配不过是把每个 \(T\) 中当前点的儿子塞进一个 \(S\) 中当前点的儿子内。于是 \(f_{u, v}\) 表示 \(S\) 中 \(u\) 匹配 \(T\) 中 \(v\) 且 \(v\) 整棵子树被匹配完的方案数。发现转移时必须知道哪些 \(v\) 的儿子还需要匹配一个 \(u\) 的儿子，于是转移时开辅助数组 \(g_{msk}\) 表示 \(msk\) 代表的 \(v\) 儿子集合已经匹配。
转移顺序大致是：枚举 \(T\) 的根并清空 \(f\)（因为这是记搜） -> 枚举 \(u\)，这需要一个 dfs，因为需要知道 \(u\) 的父亲 -> 枚举 \(u\) 的儿子、枚举 \(v\) 的儿子，进行匹配。
后面那个匹配是：\(g_{S} f_{su, sv} \to g_{S \cup \{sv\}}\)，\(su\) 是 \(s\) 的一个儿子，\(sv\) 是 \(v\) 的一个儿子。\(g_{son(v)}\) 即 \(f_{u, v}\)，注意这里的 \(g\) 是为了求 \(f_{u, v}\) 开的。
注意到这个匹配是一个分组背包，可以开辅助数组辅助 \(g\) 的转移，也可以从大到小枚举 msk 保证已经被更新过的状态不更新其余状态。这里写了第二种。
对于 \(S\) 的一张子图出现多种匹配方式，算出 \(T\) 与自己有标号匹配的方法数，除掉 \(S\) 有标号匹配方法数，就是 \(S\) 无标号匹配方法数。
复杂度是 \(O(n m^2 2^m)\)，跑不满，因为那个 \(m 2^m\) 本质上是 \(\sum d 2^d\)，\(d\) 是度数。
不大懂为什么要把儿子的匹配情况记进状态里。这道题挺自然，做起来与写起来都挺舒服。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
using tree = std::vector<std::vector<int>>;
int qpow(int a, int b) {
int ans(1);
for (; b; b >>= 1) {
if (b & 1) ans = 1ll * ans * a % mod;
a = 1ll * a * a % mod;
}
return ans;
}
void add(int &x, int y) { if ((x += y) >= mod) x -= mod; }
int main() {
int n, m; scanf("%d", &n);
std::vector<std::vector<int>> s(n), t;
for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v), --u, --v;
s[u].push_back(v), s[v].push_back(u);
}
scanf("%d", &m), t.resize(m);
for (int i = 1, u, v; i < m; i++) {
scanf("%d %d", &u, &v), --u, --v;
t[u].push_back(v), t[v].push_back(u);
}
bool o = 0;
auto match = [&](tree s, tree t) -> int {
std::vector<std::vector<int>> f(n, std::vector<int> (m, -1));
// S 中 u 匹配 T 中 v 的方案数，另外两参数是父亲
auto dfs = [&](auto self, int u, int fu, int v, int fv) -> int {
if (f[u][v] != -1) return f[u][v];
int k = (int) t[v].size() - (fv == -1 ? 0 : 1);
std::vector<int> g(1 << k);
g[0] = 1;
for (auto su : s[u]) if (su != fu) {
std::vector<int> tmp(k);
int cnt = 0;
for (auto sv : t[v]) if (sv != fv)
tmp[cnt++] = self(self, su, u, sv, v);
for (int i = (1 << k) - 1; i >= 0; i--) if (g[i])
for (int j = 0; j < k; j++) if (!(i & (1 << j))) {
add(g[i | (1 << j)], 1ll * g[i] * tmp[j] % mod);
}
}
return f[u][v] = g[(1 << k) - 1];
} ;
int sum = 0;
for (int i = 0; i < m; i++) {
f = std::vector<std::vector<int>> (n, std::vector<int> (m, -1));
// T 以 i 为根，i 匹配 S 中 u 的方案数
auto solve = [&](auto self, int u, int fa) -> int {
int ans = dfs(dfs, u, fa, i, -1);
for (auto v : s[u]) if (v != fa)
add(ans, self(self, v, u));
return ans;
} ;
add(sum, solve(solve, 0, -1));
}
return sum;
} ;
printf("%d\n", 1ll * match(s, t) * qpow(match(t, t), mod - 2) % mod);
return 0;
}