2837. wcg树

【题目描述】

wcg有一棵节点数为n 的有根树，现在需要给每个节点标号，要求对应子树同构的节点标号相同。

若图G1,G2 同构，则存在G1 点集和G2 点集之间的双射ϕ，满足u → v 是G1 中的一条边当且仅当

ϕ(u) → ϕ(v) 是G2 中的一条边。

【输入格式】

第一行包含一个数n(1 <= n <= 10e5)，表示树的点数。

第二行包含n - 1 个数，第i 个数表示编号为i + 1 点的父节点编号，满足父节点的编号小于子节点，根

节点编号为1。

【输出格式】

一行包含n 个数，表示节点标号，标号大小范围在1 到n 之间。如果有多种标号，给出字典序最小的标

号。

【样例输入】

9



1 2 2 1 5 5 7 7

【样例输出】

1 2 3 3 4 3 2 3 3

【提示】

对于30% 的数据，n <= 12。

对于50% 的数据，n <= 100。

对于100% 的数据，n <= 10e5。

如果看不懂题目描述，可以这么理解：将树上每个节点构成的子树（以此节点为根）分到不同的集合里，每个集合里所有的子树的结构都必须相同，然后输出每个节点构成的子树所属的集合，同时尽量满足答案的字典序小。

【来源】

qbxt 2017.10.6 t2