题意回顾

给定两棵有根树 $G$ 和 $H$，满足：

• $|H| \le |G| \le |H| + k$
• $k \le 5$（小常数）

我们可以从 $G$ 中删除一些节点（必须保留根节点，且删除后仍连通），问能否使 $G$ 与 $H$ 同构（有根树同构，根对应根）。

数据范围：$|G| \le 10^5$，$\sum |G| \le 5 \times 10^5$。

---

核心思路

1. 关键观察

由于 $k \le 5$，$G$ 最多比 $H$ 多 $5$ 个节点，因此：

• 最多只能删除 $5$ 个节点
• 这给了我们搜索/枚举的可能性

2. 问题转化

我们需要判断：是否存在一个 $G$ 的连通子图 $G'$，满足：

• 包含 $G$ 的根节点
• $|G'| = |H|$
• $G'$ 与 $H$ 同构

这等价于一个带删除的树同构匹配问题。

---

算法设计

方法一：树哈希 + 递归匹配

步骤 1：预处理树哈希

为每棵子树计算哈希值，用于快速判断子树同构。

typedef unsigned long long ull;
const ull BASE = 13131;

ull tree_hash(int u, vector<vector<int>>& adj) {
    vector<ull> child_hashes;
    for (int v : adj[u]) {
        child_hashes.push_back(tree_hash(v, adj));
    }
    sort(child_hashes.begin(), child_hashes.end());  // 消除顺序影响
    
    ull hash = 1;
    for (ull h : child_hashes) {
        hash = hash * BASE + h;
    }
    return hash;
}

步骤 2：递归匹配函数

定义 $match(u_G, u_H, remain)$：
$G$ 中以 $u_G$ 为根的子树能否通过删除最多 $remain$ 个节点变成 $H$ 中以 $u_H$ 为根的子树。

bool match(int uG, int uH, int remain, 
           vector<vector<int>>& adjG, vector<vector<int>>& adjH,
           vector<ull>& hashG, vector<ull>& hashH) {
    
    // 基本情况
    if (remain < 0) return false;
    if (hashG[uG] == hashH[uH] && remain >= 0) {
        return true;  // 哈希相同，直接匹配成功
    }
    
    // 度数检查
    if (adjG[uG].size() < adjH[uH].size()) {
        return false;
    }
    
    // 子节点匹配
    return match_children(uG, uH, remain, adjG, adjH, hashG, hashH);
}

步骤 3：子节点匹配

这是算法的核心，需要找到 $G$ 的子节点集合与 $H$ 的子节点集合之间的匹配。

bool match_children(int uG, int uH, int remain,
                   vector<vector<int>>& adjG, vector<vector<int>>& adjH,
                   vector<ull>& hashG, vector<ull>& hashH) {
    
    int m = adjH[uH].size();  // H 的子节点数
    int n = adjG[uG].size();  // G 的子节点数
    
    // 二分图匹配：G 的子节点匹配到 H 的子节点
    vector<vector<int>> graph(m);
    for (int i = 0; i < m; i++) {
        int vH = adjH[uH][i];
        for (int j = 0; j < n; j++) {
            int vG = adjG[uG][j];
            if (match(vG, vH, remain - (sizeG[vG] - sizeH[vH]), 
                     adjG, adjH, hashG, hashH)) {
                graph[i].push_back(j);
            }
        }
    }
    
    // 二分图最大匹配
    return max_match(graph, m, n) == m;
}

方法二：更实用的剪枝搜索

由于 $k$ 很小，我们可以采用更直接的搜索方法：

bool dfs(int uG, int uH, int remain, 
         vector<vector<int>>& adjG, vector<vector<int>>& adjH) {
    
    if (remain < 0) return false;
    
    // 尝试所有可能的子节点匹配方案
    vector<int>& childrenG = adjG[uG];
    vector<int>& childrenH = adjH[uH];
    
    int m = childrenH.size();
    int n = childrenG.size();
    
    if (n < m) return false;
    
    // 枚举 G 的子节点选择方案
    vector<int> perm(n);
    for (int i = 0; i < n; i++) perm[i] = i;
    
    do {
        bool valid = true;
        int used = n - m;  // 删除的节点数
        
        for (int i = 0; i < m && valid; i++) {
            int idx = perm[i];
            if (!dfs(childrenG[idx], childrenH[i], 
                     remain - used, adjG, adjH)) {
                valid = false;
            }
        }
        
        if (valid && used <= remain) {
            return true;
        }
    } while (next_permutation(perm.begin(), perm.end()));
    
    return false;
}

---

优化技巧

1. 记忆化搜索

使用 $dp[uG][uH][remain]$ 记录状态，避免重复计算。

2. 提前剪枝

• 如果 $sizeG[uG] - sizeH[uH] > remain$，直接返回 false
• 如果 $depthG[uG] < depthH[uH]$，直接返回 false
• 如果 $maxDepthG[uG] < maxDepthH[uH]$，直接返回 false

3. 哈希优化

• 使用多重哈希避免碰撞
• 预处理所有子树哈希值

---

完整算法流程

1. 读入并建树
2. 预处理每棵树的信息：
   • 子树大小
   • 子树深度
   • 子树哈希值
3. 递归匹配：
   • 从根节点开始
   • 尝试所有可能的子节点匹配方案
   • 利用 $k$ 小的特点进行剪枝
4. 输出结果

---

复杂度分析

• 预处理：$O(n)$
• 匹配过程：最坏 $O(n \cdot m!)$，但通过剪枝实际运行很快
• 由于 $k \le 5$，实际搜索空间很小

---

代码框架

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int MAXN = 100005;
const ull BASE1 = 13131, BASE2 = 131313, MOD = 1e9+7;

struct Tree {
    int n, root;
    vector<vector<int>> adj;
    vector<int> size, depth;
    vector<ull> hash1, hash2;
    
    void read() {
        cin >> n;
        adj.resize(n + 1);
        vector<int> parent(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> parent[i];
            if (parent[i] == -1) {
                root = i;
            } else {
                adj[parent[i]].push_back(i);
            }
        }
    }
    
    void dfs(int u) {
        size[u] = 1;
        vector<pair<ull, ull>> child_hashes;
        for (int v : adj[u]) {
            depth[v] = depth[u] + 1;
            dfs(v);
            size[u] += size[v];
            child_hashes.push_back({hash1[v], hash2[v]});
        }
        sort(child_hashes.begin(), child_hashes.end());
        
        hash1[u] = hash2[u] = 1;
        for (auto [h1, h2] : child_hashes) {
            hash1[u] = hash1[u] * BASE1 + h1;
            hash2[u] = hash2[u] * BASE2 + h2;
        }
    }
    
    void preprocess() {
        size.resize(n + 1);
        depth.resize(n + 1);
        hash1.resize(n + 1);
        hash2.resize(n + 1);
        depth[root] = 0;
        dfs(root);
    }
};

Tree G, H;
int k;
map<tuple<int, int, int>, bool> memo;

bool match(int uG, int uH, int remain) {
    if (remain < 0) return false;
    
    auto state = make_tuple(uG, uH, remain);
    if (memo.count(state)) return memo[state];
    
    // 基本情况
    if (G.hash1[uG] == H.hash1[uH] && G.hash2[uG] == H.hash2[uH]) {
        return memo[state] = (remain >= 0);
    }
    
    // 剪枝
    if (G.size[uG] - H.size[uH] > remain) 
        return memo[state] = false;
    if (G.depth[uG] < H.depth[uH])
        return memo[state] = false;
    
    // 子节点匹配
    vector<int>& childrenG = G.adj[uG];
    vector<int>& childrenH = H.adj[uH];
    
    int m = childrenH.size(), n = childrenG.size();
    if (n < m) return memo[state] = false;
    
    // 枚举匹配方案
    vector<int> perm(n);
    for (int i = 0; i < n; i++) perm[i] = i;
    
    do {
        bool valid = true;
        int deleted = n - m;
        
        for (int i = 0; i < m && valid; i++) {
            int idx = perm[i];
            if (!match(childrenG[idx], childrenH[i], remain - deleted)) {
                valid = false;
            }
        }
        
        if (valid && deleted <= remain) {
            return memo[state] = true;
        }
    } while (next_permutation(perm.begin(), perm.end()));
    
    return memo[state] = false;
}

int main() {
    int C, T;
    cin >> C >> T >> k;
    
    while (T--) {
        memo.clear();
        G.read();
        H.read();
        
        G.preprocess();
        H.preprocess();
        
        if (match(G.root, H.root, k)) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    
    return 0;
}

---

总结

本题的关键在于利用 $k$ 很小的特点，通过搜索剪枝解决树同构匹配问题：