为了方便你创建 OJ 测试数据，我为你编写了一个完整的数据生成器。该程序遵循 NOIP C++14 标准，能够自动生成 1-10 号测试点的 .in 和 .out 文件。

数据生成器设计逻辑

1. 多样性覆盖：

   • 1：样例数据。
   • 2：极小数据（$N=1, N=2$）。
   • 3：星形树（高度极小）。
   • 4：链形树（高度极大，测试深度）。
   • 5-6：随机生成的树（使用随机父节点法和随机加边法）。
   • 7-8：同构压力测试。生成几棵基础树，通过随机重排编号（Permutation）和更换根节点来生成看起来完全不同但结构同构的树。
   • 9-10：综合极端数据（$M=50, N=50$），包含各种同构类和非同构类的混合。

2. 安全性与性能：

   • 使用 std::vector 和邻接表处理树结构。
   • 非递归哈希：为了防止极端链形树导致栈溢出，在生成答案（.out）时采用基于 BFS 层级的逆序遍历（从叶到根）来计算哈希值。
   • 随机性：使用 std::mt19937 配合 chrono 种子，确保每次生成的随机性。

完整数据生成器代码 (DataGenerator.cpp)

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <chrono>
#include <map>
#include <queue>

using namespace std;

typedef unsigned long long ull;

// --- 树哈希核心算法 (用于生成标准输出) ---
ull shift(ull x) {
    x ^= x << 13; x ^= x >> 7; x ^= x << 17;
    return x;
}
ull mask(ull x) { return shift(x + 0x9e3779b97f4a7c15ULL); }

// 非递归计算树哈希（层序逆序处理，模拟后序遍历）
ull get_tree_hash_at_root(int n, int root, const vector<vector<int>>& adj) {
    vector<int> order;
    vector<int> parent(n + 1, 0);
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (v != parent[u]) {
                parent[v] = u;
                q.push(v);
            }
        }
    }
    vector<ull> h(n + 1, 1);
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];
        vector<ull> children;
        for (int v : adj[u]) {
            if (v != parent[u]) children.push_back(h[v]);
        }
        sort(children.begin(), children.end());
        for (ull ch : children) h[u] += mask(ch);
    }
    return h[root];
}

ull get_canonical_hash(int n, const vector<vector<int>>& adj) {
    ull min_h = -1ULL;
    for (int i = 1; i <= n; ++i) {
        min_h = min(min_h, get_tree_hash_at_root(n, i, adj));
    }
    return min_h;
}

// --- 数据生成辅助 ---
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Tree {
    int n;
    vector<int> p; // p[i] 是节点 i+1 的父亲
};

// 将邻接表形式转化为题目要求的父亲表示法（随机选根）
Tree adj_to_parents(int n, const vector<vector<int>>& adj) {
    int root = uniform_int_distribution<int>(1, n)(rng);
    vector<int> parents(n + 1, 0);
    queue<int> q; q.push(root);
    vector<bool> vis(n + 1, false); vis[root] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                parents[v] = u;
                q.push(v);
            }
        }
    }
    Tree res; res.n = n;
    for (int i = 1; i <= n; ++i) res.p.push_back(parents[i]);
    return res;
}

// 随机重排编号生成同构树
Tree shuffle_tree(int n, const vector<vector<int>>& adj) {
    vector<int> mapping(n + 1);
    for (int i = 1; i <= n; ++i) mapping[i] = i;
    shuffle(mapping.begin() + 1, mapping.end(), rng);
    vector<vector<int>> new_adj(n + 1);
    for (int u = 1; u <= n; ++u) {
        for (int v : adj[u]) {
            new_adj[mapping[u]].push_back(mapping[v]);
        }
    }
    return adj_to_parents(n, new_adj);
}

// 生成随机树 (Random Parent 算法)
vector<vector<int>> gen_rand_adj(int n) {
    vector<vector<int>> adj(n + 1);
    for (int i = 2; i <= n; ++i) {
        int u = i, v = uniform_int_distribution<int>(1, i - 1)(rng);
        adj[u].push_back(v); adj[v].push_back(u);
    }
    return adj;
}

// --- 生成流程 ---
void run_task(int tid) {
    string in_file = to_string(tid) + ".in";
    string out_file = to_string(tid) + ".out";
    ofstream fin(in_file);
    
    int M;
    vector<Tree> forest;

    if (tid == 1) { // 样例
        fin << "4\n4 0 1 1 2\n4 2 0 2 3\n4 0 1 1 1\n4 0 1 2 3\n";
        fin.close();
    } else {
        if (tid == 2) M = 5; // 边界
        else if (tid < 5) M = 20;
        else M = 50;

        for (int i = 0; i < M; ++i) {
            int n = (tid == 2) ? (i % 2 + 1) : 50;
            vector<vector<int>> base_adj;
            if (tid == 3) { // 星形
                base_adj.resize(n + 1);
                for (int j = 2; j <= n; ++j) { base_adj[1].push_back(j); base_adj[j].push_back(1); }
            } else if (tid == 4) { // 链形
                base_adj.resize(n + 1);
                for (int j = 1; j < n; ++j) { base_adj[j].push_back(j+1); base_adj[j+1].push_back(j); }
            } else if (tid >= 7 && i > M/2) { // 故意制造同构
                // 此时直接对之前的树进行 shuffle
                int prev_idx = i % (M/2);
                vector<vector<int>> prev_adj(51);
                // 还原之前的邻接表
                for(int k=0; k<forest[prev_idx].p.size(); ++k){
                    int u = k+1, v = forest[prev_idx].p[k];
                    if(v != 0){ prev_adj[u].push_back(v); prev_adj[v].push_back(u); }
                }
                forest.push_back(shuffle_tree(n, prev_adj));
                continue;
            } else {
                base_adj = gen_rand_adj(n);
            }
            forest.push_back(adj_to_parents(n, base_adj));
        }

        fin << M << "\n";
        for (auto &t : forest) {
            fin << t.n;
            for (int p_val : t.p) fin << " " << p_val;
            fin << "\n";
        }
        fin.close();
    }

    // 生成输出文件
    ifstream f_check(in_file);
    ofstream fout(out_file);
    int cur_M; f_check >> cur_M;
    map<ull, int> seen;
    for (int i = 1; i <= cur_M; ++i) {
        int n; f_check >> n;
        vector<vector<int>> adj(n + 1);
        for (int j = 1; j <= n; ++j) {
            int p_val; f_check >> p_val;
            if (p_val != 0) { adj[j].push_back(p_val); adj[p_val].push_back(j); }
        }
        ull h = get_canonical_hash(n, adj);
        if (seen.find(h) == seen.end()) seen[h] = i;
        fout << seen[h] << "\n";
    }
    fout.close();
    cout << "Testcase " << tid << " generated." << endl;
}

int main() {
    for (int i = 1; i <= 10; ++i) run_task(i);
    return 0;
}

数据说明 (适合 OJ 使用)

1. 文件说明：
   • 生成器会自动产生 1.in 到 10.out。
   • 文件体积极小（总共不到 200KB），适合快速评测。
2. 测试点特征：
   • Test 1: 官方样例。
   • Test 2: 只有一个节点或两个节点的最小树，测试 $N$ 的下界。
   • Test 3-4: 极端的“菊花图”和“长链图”，测试哈希算法对极端形态的分辨能力和递归深度限制。
   • Test 7-8: 核心同构测试。程序会生成基础树，然后随机改变其根节点位置和节点编号。如果考生的哈希算法对“根的选取”敏感或对“子节点顺序”敏感，则无法通过此测试点。
   • Test 9-10: 满额数据（$M=50, N=50$），随机和同构混合，覆盖全范围。
3. 时间与空间限制：
   • Time Limit: 1.0s (KMP 或 Tree Hash 均为 $O(N^2 \log N)$ 或 $O(N \log N)$，该范围内远低于 1s)。
   • Memory Limit: 256MB。

读题关键词提取

在辅导学生时，引导他们注意：

• "无根树"：意味着父亲关系是假的，需要按无向图处理。
• "父亲结点编号 0"：只是为了描述结构，不代表整棵树的绝对形态。
• "最小编号"：典型的等价类输出要求，需要用到 map 或哈希表记录首次出现的 ID。

在树同构问题中，我们的目标是找到一种“指纹”，使得两棵结构相同的树无论如何编号、如何摆放，其“指纹”都保持一致。

下面我将带你从最原始的思路出发，逐步演进到竞赛级的高效树哈希算法。

一、 复杂度演进分析

二、 阶段 2：基于 AHU 的字符串表示法 (思路提示)

由于本题 $N=50$ 极小，你可以想象将树变成一串括号。

1. 对于叶子节点，返回 ()。
2. 对于非叶子节点，收集所有子树返回的字符串，按字典序排序后拼接，外面再套一层括号。
3. 为了处理无根树，你需要枚举每一个点 $r \in [1, N]$ 作为根，求出 $N$ 个字符串，取字典序最小的那个。

三、 阶段 3 & 4：NOI 竞赛级标准代码 (树哈希实现)

这是目前竞赛中最主流的写法。我们采用随机映射哈希（Shift Hash），它比简单的加法或乘法哈希更难被构造数据卡掉。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

/**
 * 预备知识：树哈希 (Tree Hashing)
 * 核心公式：H(u) = 1 + sum( f(H(v)) )
 * 其中 f(x) 是一个高冲突抵抗的随机映射函数。
 */

typedef unsigned long long ull;

// 一个经典的随机映射函数，用于加强哈希的抗碰撞性
ull shift(ull x) {
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    return x;
}

// 模拟随机掩码，防止被特定数据构造碰撞
ull mask(ull x) {
    return shift(x + 0x9e3779b97f4a7c15ULL);
}

int N, M;
vector<int> adj[55];

// 计算以 u 为根、p 为父亲的子树哈希值
ull get_hash(int u, int p) {
    ull h = 1; // 基础值，区分空树
    vector<ull> child_hashes;
    
    for (int v : adj[u]) {
        if (v == p) continue;
        child_hashes.push_back(get_hash(v, u));
    }
    
    // 关键点：必须排序！
    // 因为同构树的子树顺序在输入中可能不同，排序保证了“顺序无关性”
    sort(child_hashes.begin(), child_hashes.end());
    
    for (ull ch : child_hashes) {
        h += mask(ch); // 累加经过映射后的子树哈希
    }
    return h;
}

// 处理每一棵无根树
ull get_tree_id() {
    int n;
    cin >> n;
    // 每次处理新树前清空邻接表
    for (int i = 0; i <= n; ++i) adj[i].clear();
    
    for (int i = 1; i <= n; ++i) {
        int fa;
        cin >> fa;
        if (fa != 0) {
            adj[i].push_back(fa);
            adj[fa].push_back(i);
        }
    }

    ull min_hash = -1ULL; // 初始化为最大值
    /**
     * 时间复杂度优化建议：
     * 对于 N=50，枚举所有点为根是 O(N^2 log N)，完全没问题。
     * 若 N=10^5，请先求出树的重心（1或2个），仅以重心为根计算哈希，
     * 复杂度将降为 O(N log N)。
     */
    for (int r = 1; r <= n; ++r) {
        min_hash = min(min_hash, get_hash(r, 0));
    }
    return min_hash;
}

int main() {
    // 竞赛标准：取消同步流，提速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    if (!(cin >> m)) return 0;

    // 记录每种哈希值第一次出现的树编号
    map<ull, int> seen_hashes;
    vector<ull> tree_hashes;

    for (int i = 1; i <= m; ++i) {
        ull tid = get_tree_id();
        if (seen_hashes.find(tid) == seen_hashes.end()) {
            seen_hashes[tid] = i;
        }
        // 输出该哈希值对应的最小树编号
        cout << seen_hashes[tid] << "\n";
    }

    return 0;
}

四、 关键点与易错点 (教练的嘱托)

1. 子树排序 (Sorting Children)：
   • 易错点：很多选手记得递归计算哈希，却忘了给子节点的哈希值排序。如果不排序，H(A, B) 和 H(B, A) 会被识别为不同的树，导致同构识别失败。
2. 无根树转有根树：
   • 关键点：无根树同构的难点在于“根不确定”。本代码采用全根枚举法（取所有根哈希的最小值），这在 $N \le 500$ 时非常稳健。在 $N$ 极大时，必须使用重心。
3. 哈希冲突：
   • 建议：简单的 h += h_child 容易被特殊的“星形树”或“链形树”卡掉。使用 x ^ (x << 13)... 这种位移映射（即 shift 函数）能显著提高散列程度。
4. 空间复杂度分析思考过程：
   • 本题空间消耗极小。主要在于邻接表 $O(N)$ 和递归深度 $O(N)$。$M$ 棵树的指纹存入 map 是 $O(M)$。
   • 总空间：$O(M + N)$，在 256MB 限制下极其安全。

五、 读题关键词 (如何一眼识破同构题)

• “重新标号”：这是判同构的灵魂词汇。
• “形态相同”：明确告诉你忽略编号，只看拓扑结构。
• “等价类”：通常意味着你需要为每个对象算一个“特征值”或“指纹”。
• “无根树”：看到这个词，脑子里要立刻反映出：要么枚举所有根，要么找重心。

通过这道题，你不仅学会了如何处理树的指纹，更理解了如何通过 “找中心” 和 “排序消除顺序性” 来处理图论中的对称性问题。继续练习吧！