← 返回题目列表

Codeforces · 442/D

D. 亚当和树

中文机器翻译题面 查看原题

当 Adam 得到一棵有根树(无环的连通无向图)时,他立即开始为其着色。更正式地说,他为树的每条边分配一种颜色,使其满足以下两个条件:

- 没有顶点有两个以上的入射边被涂成相同的颜色。
- 对于具有相同颜色(例如,c)的入射边的任何两个顶点,它们之间的路径由颜色 c 的边组成。

并非所有的树画都同样适合亚当。让我们考虑从某个顶点到根的路径。我们将该路径上不同颜色的数量称为顶点的成本。树的着色成本将是所有顶点中最大的成本。帮助亚当确定画树的最低可能成本。

最初,亚当树由单个顶点组成,该顶点的编号为 1,并且是根。 Adam 在一次移动中向已有的顶点添加了一个新顶点,新顶点的数字等于可用的最小正整数。每次操作后,您需要计算为结果树着色的最小成本。

输入

第一行包含整数 n (1 ≤ n ≤ 106) — 添加新顶点的次数。第二行包含 n 个数字 pi (1 ≤ pi ≤ i) — 我们添加另一个顶点的顶点的编号。

输出

打印 n 个整数 — 每次相加后树绘制的最小成本。

示例

输入 #1

11
1 1 1 3 4 4 7 3 7 6 6

输出 #1

1 1 1 1 1 2 2 2 2 2 3

注意

下图显示了在最后一刻根据样本绘制树的可能变体之一。编号为 11 和 12 的顶点的成本等于 3。