题解

思路

输入选定的根不是树的固有部分，所以不能直接比较从该根出发的有根树表示。无根树的中心只有一个或两个，并且在任意同构映射下，中心必然映射到中心。于是可以从中心构造与编号、输入根都无关的规范表示。

做法

先把每行父亲数组转换为无向邻接表。不断删除当前所有叶子，直至剩下一到两个点，这些点就是树的中心。

对于一个指定根，递归求每个孩子子树的表示，将所有孩子表示排序后依次拼接，并在外层加上一对括号。这样，孩子次序和点编号都不会影响结果。

若树只有一个中心，就使用以它为根的表示；若有两个中心，就分别以两个中心为根求表示，并取字典序较小者。两棵无根树同构，当且仅当所得规范表示相同。

按输入顺序维护每种规范表示第一次出现的编号，即可回答每棵树所属等价类的最小编号。

正确性说明

有根树的规范表示对孩子表示排序，因此它相同当且仅当两棵有根树同构。无根树同构保持所有点的度数与删叶层数，所以保持中心集合；把根选在中心后，同构必然对应某一种中心选择。反之，两个中心根表示相同会直接给出保持边关系的顶点对应。因此，无根树的最终规范表示相同当且仅当它们同构。记录同一表示最早出现的位置，所得答案正是同构类中的最小编号。

复杂度

单棵树的字符串总长度为 $O(N^2)$，排序与拼接总时间为 $O(N^2\log N)$，空间复杂度为 $O(N^2)$。