你好！我是你的 OI 教练。今天我们要深入探讨的是树论中一个非常经典且优美的问题——树同构 (Tree Isomorphism)。

这个问题在 NOI 级别竞赛中经常作为复杂树形 DP 或图论题的预处理子模块出现。掌握了它，你就掌握了识别“本质相同”结构的有力武器。

一、 预备知识点

在解决树同构问题前，你需要打好以下基础：

1. 树的重心与中心 (Centers of a Tree)：
   • 重心：删除该点后，剩下的最大子树尺寸最小的点。
   • 中心：树中直径的中点。
   • 性质：一棵树的重心或中心只有 1 个或 2 个。这是将“无根树”转化为“有根树”处理的关键。
2. 树哈希 (Tree Hashing)：
   • 通过递归的方式，将树的结构映射为一个数值。
   • 核心思想：$H(u) = f \left( \{H(v_1), H(v_2), \dots, H(v_k)\} \right)$，其中 $v_i$ 是 $u$ 的子节点，$f$ 是一个对子树哈希值顺序不敏感的函数。
3. 等价类划分：
   • 利用哈希值将对象归类。

二、 题目描述 (NOI 风格)

题目名称：树同构 (Tree Isomorphism) 时间限制：1.0s 内存限制：256MB

【问题描述】 在图论中，两棵树 $T_1$ 和 $T_2$ 被称为同构的，是指能够通过对 $T_1$ 的节点进行重新编号，使得其结构与 $T_2$ 完全一致。 现在给定 $M$ 棵无根树，请你判断每棵树与之前给出的哪些树同构，并输出每一棵树所属类别的最小编号（即与它同构的第一棵树的序号）。

【输入格式】 第一行包含一个整数 $M$，表示树的数量。 接下来 $M$ 行，每行描述一棵树：

• 首先是一个整数 $N$，表示该树的节点数。
• 随后 $N$ 个整数，第 $i$ 个整数表示编号为 $i$ 的节点的父亲节点编号。若该整数为 $0$，表示该节点为当前的根。

【输出格式】 输出共 $M$ 行，每行一个整数。第 $i$ 行的整数表示与第 $i$ 棵树同构的所有树中，编号最小的那棵树的编号。

【样例输入】

4 
4 0 1 1 2 
4 2 0 2 3 
4 0 1 1 1 
4 0 1 2 3

【样例输出】

1 
1 
3 
1

【数据范围】

• $1 \le M, N \le 50$
• 注意：虽然 $N, M$ 较小，但理解通用的 $O(N \log N)$ 树哈希算法对竞赛更有意义。

三、 启发式教学：草稿纸上的推理过程

想象你手里拿着两束杂乱的“挂饰”（树），你如何一眼看出它们是不是同一种形状？

1. 消除“根”的干扰

提问：无根树没有固定的根，同一个结构选不同的点当根，哈希值会变。怎么办？ 引导：找树的“绝对位置”。

• 在草稿纸上画一棵长链树。它的中心点是确定的。
• 结论：找到树的重心。如果重心有两个，我们就分别以这两个点为根求哈希，取其中较小的一个作为这棵无根树的“唯一指纹”。

2. 设计“指纹”函数 (Tree Hash)

提问：如何保证子树顺序不同，哈希值相同？ 引导：子树 $A, B$ 的哈希值 $H_A, H_B$，无论谁先谁后，结果要一致。

• 方案 A (AHU算法)：将子树哈希串按字典序排序，拼接后加括号。如 (()())。
• 方案 B (随机映射哈希)：使用位移和质数映射。 例如：$f(H) = \text{shift}(H \oplus \text{mask})$。 公式推荐：$H(u) = 1 + \sum_{v \in children(u)} \text{poly}(H(v))$，其中 $\text{poly}$ 是某种随机映射。

3. 复杂度分析思考

• 时间：$M$ 棵树，每棵树找重心 $O(N)$，计算哈希（含排序）$O(N \log N)$。 总复杂度 $O(M \cdot N \log N)$。对于 $N=50$ 绰绰有余。
• 空间：存储 $M$ 个哈希值 $O(M)$，邻接表存储树 $O(N)$。

四、 算法流程图 (伪代码提示)

我们将展示如何处理单棵树并获取其“指纹”：

graph TD
    Start("开始处理第 i 棵树") --> Build("构建邻接表并存储树")
    Build --> FindCenter("寻找树的重心 Centers")
    FindCenter --> LoopCenter{"遍历重心 c"}
    
    LoopCenter -- "存在未处理重心" --> Rooting("以 c 为根进行 DFS")
    Rooting --> SubHash("计算子树哈希: 递归处理所有子节点")
    SubHash --> SortChild("将子节点哈希值排序")
    SortChild --> Combine("Hash of u 等于 f_函数_排序后的序列")
    Combine --> SaveHash("存入该重心的结果集")
    SaveHash --> LoopCenter
    
    LoopCenter -- "处理完毕" --> GetMin("取所有重心 Hash 的最小值作为 TreeID")
    GetMin --> Compare("与前 i 减 1 棵树的 TreeID 比较")
    Compare --> Output("输出匹配到的最小编号")
    Output --> End("结束")

    style Combine fill:#f9f,stroke:#333
    style FindCenter fill:#bbf,stroke:#333

五、 读题关键词与易错点总结

1. 关键词提取：

• “重新标号”：这是同构的定义，提示你需要寻找某种“标号无关”的特征量。
• “父亲节点编号”：注意输入给出的是父子关系，但在同构判断中，我们通常视其为无向图。
• “最小编号”：暗示你需要记录每一棵树的特征值，并与之前的记录对比。

2. 易错点预警：

• 哈希冲突：千万不要简单地把子树哈希值相加。推荐使用随机种子映射，例如： h[u] = 1; for(int v : G[u]) h[u] += shift(h[v]); 其中 shift(x) 可以是一个复杂的位移异或函数。
• 重心的个数：树的重心可能有两个。如果漏掉一个，会导致两棵完全一样的树因为根选得不同而判为不同。
• 节点编号：输入中的节点编号可能从 1 开始，也可能从 0 开始（父节点 0 代表没有父节点），注意偏移量。

通过这道题的练习，你将能熟练处理树的形态特征。记住，树同构的核心就是：找准定点（重心），设计稳定的哈希函数。加油！