对每棵树，至多只有两个重心。显然两棵无根树同构等价于以两个无根树的某个重心为根的两个有根树同构。
于是无根树同构问题可以转化为有根树同构问题，故下面只考虑有根树同构问题。
利用哈希 $O(n)$ 时间判断树同构，不能保证完全正确。
构造各种哈希函数，当所有哈希值相同时才认为同构，下面给出两种哈希函数。
$$h_{1,u}=\text{sz}_u+\sum_{v\in \text{son}(u)}\text{sz}_vh_{1,v}$$
$$h_{2,u}=\text{sz}_u+\text{sz}_u\sum_{v\in \text{son}(u)}\text{sz}_vh_{2,v}$$
如果需要更高准确率，可以考虑构造 $f\{1,2\cdots n\}\to \{p_1,p_2\cdots p_n\}$，并将上式 $\text{sz}_u$ 替换为 $p_{\text{sz}_u}$，其中 $p$ 序列可以为随机数表，素数表等等。
利用每棵树的最小字典序的括号序列判断树同构。
易知两棵树同构等价于两棵树最小字典序的括号序列相同。当然实现的时候不需要真正模拟括号序列，可以考虑使用 $01$ 串。
于是考虑如何快速求出每棵树的最小表示法。
一个比较暴力的算法是先求出所有子树的最小表示法，然后用 $\text{Trie}$ 树实现 $O(n)$ 排序，然后顺次拼接，最后最外层添加括号。
上述算法的时间复杂度为 $O(n^2)$，考虑优化算法。
发现可以用名次代替括号序列。考虑根据对所有同一深度的树排序，每个深度为 $d$ 的结点的序列由深度为 $d+1$ 的儿子结点的名次构成。
注意名次是指在两棵树中所有深度为 $d+1$ 的结点中的名次，初始叶子结点名次均为 $0$。
然后对所有深度为 $d$ 的结点的序列再次排序，如果使用基数排序，可以使得总时间复杂度为 $O(n)$。但是树哈希太香了
给定两棵带标号无根树，保证其中一棵树删去一个结点后可以与另一棵树同构。
问需要删去哪个结点才能使两棵树同构，如果有多个满足条件的结点，输出编号最小的。
对结点数较少的树，考虑换根 $\text{dp}$ 枚举以每个点为根的情况同时将哈希值存入 $\text{set}$。
对结点数较多的树，考虑换根 $\text{dp}$ 枚举以每个点为根的情况，如果该结点度为一，则在 $\text{set}$ 中查找是否存在与该结点相连结点的哈希值。
时间复杂度 $O(n\log n)$。
给定两棵带标号有根树，保证同构。要求修改两棵树的标号，将两棵树变成完全相同的树，问最小修改次数。
先树哈希求出每棵子树的哈希值，再考虑 $\text{dp}$，定义 $\text{dp}(u_1,u_2)$ 为将以 $u1,u2$ 为根的两棵树匹配时最多的标号相同的位置个数。
对两棵同构的树，暴力考虑枚举所有儿子结点。将所有的同构的儿子 $v1,v2$ 结点连上一条权值为 $\text{dp}(v_1,v_2)$ 的边，然后跑最大二分图匹配。
注意如果根节点标号相同需要将最大匹配结果加一。
最终答案为 $n-\text{dp}(\text{root}_1,\text{root}_2)$，时间复杂度 $O\left(\sum (\text{son}^2+\text{son}^3)\right)=O(n^3)$。