CF762F Tree nesting

来一点更清楚的、实现方面的东西。

做法同 这篇，他的实现很优美但略微繁琐了些。

枚举 \(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;
}