D2T1. P8499 [NOI2022] 挑战 NPC Ⅱ

首先题目已经明示树哈希了，我们需要一个正确的树哈希方法解决树同构问题。

设树哈希函数 $f$，需满足若 $T_1 \cong T_2$，则 $f(T_1) = f(T_2)$，否则极大概率 $f(T_1) \neq f(T_2)$。

对于有根树 $G, H$，设它们的根分别为 $R_G$ 和 $R_H$，其子节点集合分别为 $S(R_G)$ 和 $S(R_H)$，易得另一种描述同构的方法为 $G\cong H$ 当且仅当

• $|S(R_G)| = |S(R_H)|$。
• 存在一种 $S(R_G) \to S(R_H)$ 的 双射 $I$，使得对于任意 $g\in S(R_G)$，$g\cong I(g)$。

说人话就是根节点儿子数量相等，且存在两棵树的根儿子的一一对应关系，使得对应儿子子树同构。这样我们就将问题缩小至儿子子树的规模，这给予我们树形 DP 的思路。

具体地，设 $f_G(i)$ 表示 $G$ 以 $i$ 为根的子树的哈希值，转移时考虑当前节点 $x$ 及其所有子节点 $y$。回顾上述结论，我们发现它提出了这样的要求：父节点哈希值与所有子节点相关，但与子节点顺序无关。做到这一点即可满足对于任意 $T_1\cong T_2$，$f(T_1) = f(T_2)$。

因此，我们需要用 具有交换律 的运算结合所有 $f_G(y)$，以消除各个子节点之间的顺序。容易想到加法或乘法，即 $f_G(x) = \sum f_G(y)$ 或 $f_G(x) = \prod f_G(y)$。但是这样冲突概率较大，我们需要进行一些改进。笔者的写法是 $f_G(x) = (P_1 + B ^ {|son_G(x)|}\prod f_G(y))\bmod P_2$，将乘法和加法结合起来，更不容易冲突，其中 $B, P_1, P_2$ 都是自选的一些质数。

搞定了树同构，让我们回到原问题。注意到 $k$ 很小，所以也许爆搜 + 剪枝 + 记忆化就可以了？

设 $f(x, y)$ 表示 $G$ 以 $x$ 为根的子树删去若干节点后能否同构于 $H$ 以 $y$ 为根的子树。看似需要做一遍二分图匹配，但注意到若 $a\in son_G(x)$ 的子树同构于 $b\in son_H(y)$ 的子树，我们可以直接将它们匹配掉。

证明：不妨设 $a$ 和 $b'$ 对应，$a'$ 和 $b$ 对应，若 $a\cong b'$，则交换 $b, b'$ 仍成立，对于 $a'\cong b$ 同理。因此 $a$ 删去若干节点同构于 $b'$，$a'$ 删去若干节点同构于 $b$。因为 $a, b$ 同构，所以容易根据 $a'$ 变成 $b$ 和 $a$ 变成 $b'$ 的方案构造出 $a'$ 变成 $b'$ 的方案，这样 $a$ 仍可匹配 $b$。换言之，在最终匹配方案中，我们总可以通过调整使得 $a, b$ 匹配。

因此，不断删去 $son_G(x)$ 和 $son_H(y)$ 之间同构的元素，得到 $I_G(x)$ 和 $I_H(y)$。由于这两个集合之间两两不同构，所以对于每个 $a\in I_G(x)$，都需要在其子树内删去至少一个节点，甚至删空，可知 $|I_G(x)| \leq sz_x - sz_y$。考虑直接全排列枚举所有可能的匹配，递归到子问题处理。

注意递归处理前需要判一下是否存在 $a\in I_G(x)$ 和 $b\in I_H(y)$ 满足 $sz_a \leq sz_b$，此时直接不合法，否则可能导致 $sz_x - sz_y$ 变大，复杂度看起来就不正确。

加入上述剪枝后复杂度看起来很对，因为 $k\leq 5$。时间复杂度一个比较松的上界是 $\mathcal{O}(nk!k)$，如果用 map 做记忆化还要多一个 $\log$，但这个 $\log$ 不是直接乘在 $nk!k$ 上面，所以常数很小，或者说时间复杂度可以更紧，但已经足够了。

Upd：实际上复杂度是 $\mathcal{O}(n2 ^ k)$，每次令 $sz_{a_1} = C + k - 1$，$sz_{a_2} = C + 1$，$sz_{b_1} = sz_{b_2} = C$ 即可令 $k$ 减去 $1$ 但情况数乘 $2$，卡满上界。枚举全排列换成网络流即可将匹配复杂度做到 $\mathcal{O}(\mathrm{poly}(k))$，注意判不合法：若 $a, b$ 匹配后不存在对于所有 $a'$ 和 $b'$ 均有 $sz_{a'} > sz_{b'}$ 的匹配，则 $f(a, b)$ 就是无用的，不能递归。

好玄学啊这题，树哈希和时间复杂度分析都很玄学。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
inline int read() {
  int x = 0, sgn = 0;
  char s = getchar();
  while(!isdigit(s)) sgn |= s == '-', s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return sgn ? -x : x;
}
inline void print(int x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
bool Mbe;
constexpr int N = 1e5 + 5;
constexpr int base = 131;
constexpr int mod = 1e9 + 7;
int C, T, k, pw[N];
vector<int> G[N], H[N];
struct solver {
  vector<int> e[N];
  int n, R, f[N], sz[N];
  void dfs(int id) {
    f[id] = pw[e[id].size()], sz[id] = 1;
    for(int it : e[id]) dfs(it), f[id] = 1ll * f[id] * f[it] % mod, sz[id] += sz[it];
    f[id] = (f[id] + 19260817) % mod;
    sort(e[id].begin(), e[id].end(), [&](int x, int y) {return f[x] < f[y];});
  }
  void init() {
    n = read();
    for(int i = 1; i <= n; i++) e[i].clear();
    for(int i = 1; i <= n; i++) {
      int ff = read();
      if(ff != -1) e[ff].push_back(i);
      else R = i;
    }
    dfs(R);
  }
} g, h;
map<int, int> f[N];
bool dfs(int x, int y) {
  if(g.e[x].size() < h.e[y].size()) return 0;
  if(g.sz[x] == h.sz[y]) return g.f[x] == h.f[y];
  if(f[x].find(y) != f[x].end()) return f[x][y];
  vector<int> gson, hson;
  int pg = 0, ph = 0;
  auto grt = [&]() {gson.push_back(g.e[x][pg++]);};
  auto hrt = [&]() {hson.push_back(h.e[y][ph++]);};
  while(pg < g.e[x].size() && ph < h.e[y].size()) {
    if(g.f[g.e[x][pg]] == h.f[h.e[y][ph]]) pg++, ph++;
    else if(g.f[g.e[x][pg]] < h.f[h.e[y][ph]]) grt();
    else hrt();
  }
  while(pg < g.e[x].size()) grt();
  while(ph < h.e[y].size()) hrt();
  int cut = g.sz[x] - h.sz[y];
  if(gson.size() > cut) return 0;
  vector<int> p(gson.size());
  for(int i = 0; i < gson.size(); i++) p[i] = i;
  do {
    bool ok = 1;
    for(int i = 0; i < hson.size(); i++) ok &= g.sz[gson[p[i]]] > h.sz[hson[i]];
    if(!ok) continue;
    for(int i = 0; i < hson.size(); i++) ok &= dfs(gson[p[i]], hson[i]);
    if(ok) return f[x][y] = 1;
  } while(next_permutation(p.begin(), p.end()));
  return f[x][y] = 0;
}
void solve() {
  g.init(), h.init();
  for(int i = 1; i <= g.n; i++) f[i].clear();
  puts(dfs(g.R, h.R) ? "Yes" : "No");
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("d.in", "r", stdin);
    FILE* OUT = freopen("d.out", "w", stdout);
  #endif
  for(int i = pw[0] = 1; i < N; i++) pw[i] = 1ll * pw[i - 1] * base % mod;
  C = read(), T = read(), k = read();
  while(T--) solve();
  cerr << TIME << " ms\n";
  return 0;
}
/*
2022/8/29
author: Alex_Wei
start coding at 8:55
finish debugging at 9:14
*/