题解

思路

树的左右顺序可以任意选择，关键是识别相同的有根子树类型，并判断每种类型能否成对放在中轴两侧。

做法

子树类型

把树以结点 $1$ 为根。两棵有根树同构，当且仅当它们根结点的所有子树类型构成的多重集相同。自底向上处理结点，把排序后的子树类型序列映射成一个唯一整数编号，就能无碰撞地表示该结点对应的有根子树类型。

对称性的递推

设一个结点的每种子树类型出现若干次。相同类型的两棵子树可以放在左右对称的位置，因此每种类型的偶数个副本都能两两配对。

若没有类型出现奇数次，该结点对应的子树一定对称。若恰有一种类型出现奇数次，其中一棵必须放在正中间；此时该类型自身也必须对称。若有至少两种类型出现奇数次，就不可能只留下一个中间位置。

因此，自底向上求出每种子树类型的编号及其是否对称，最后检查根结点即可。

正确性证明

对结点深度做归纳。叶结点没有子树，显然对称。

假设所有更深结点的子树类型和对称性均已正确求出。相同类型的子树互为镜像时可以成对放置；不同类型不能配成镜像。因此，一个结点能对称排列，当且仅当奇数次出现的子树类型至多一种，并且唯一的奇数类型本身可以放在中轴上，也就是该类型对称。递推条件与此完全一致，所以当前结点判断正确。由归纳法，根结点的判断即为整棵树的正确答案。

复杂度分析

对每个结点排序其子树类型。单个测试用例时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$；所有测试用例按总结点数计算。