有根树同构分类（Rooted Tree Isomorphism Classification）

问题描述

给定一棵含 $N$ 个顶点的有根树，根为顶点 $0$；顶点 $i$（$i \ge 1$）的父节点为 $p_i$。
通过选择一个顶点作为新根，可得到 $N$ 棵有根子树（以该顶点为根的子树）。
请将这 $N$ 棵子树按有根树同构关系分类，并输出：

• 一个整数 $K$：不同同构类的数量；
• 一个长度为 $N$ 的整数序列 $a_0, a_1, \dots, a_{N-1}$，其中 $a_i$ 表示以顶点 $i$ 为根的子树所属的同构类编号（满足 $0 \le a_i < K$），且对任意 $i, j$，有$$a_i = a_j \iff \text{以 } i \text{ 和 } j \text{ 为根的子树同构}.$$

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $0 \leq p_i < i$

输入格式

$N$
$p_1\ p_2\ \cdots\ p_{N-1}$

输出格式

$K$
$a_0\ a_1\ \cdots\ a_{N-1}$

若存在多个合法解，输出任意一个即可。

11
0 1 1 2 2 0 6 6 8 8

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

5
0 1 2 3

5
4 3 2 1 0