分数: 800 点
问题陈述
N 参赛者参加了比赛。总计 N-1 比赛在淘汰赛中进行。 由于某些原因,比赛可能对所有参赛者来说并不“公平”。 也就是说,每个参赛者为了赢得冠军而必须进行的比赛的数量可能是不同的。本声明末尾正式描述了锦标赛的结构。
每场比赛结束后,总是有一胜一负。最后站立的选手被宣布为冠军。
图:锦标赛示例
为了方便起见,对参赛者进行了编号 1 通过 N。参赛者编号 1 获得冠军,参赛者编号 i(2 ≦ i ≦ N) 在与编号为 的参赛者的比赛中被击败 a_i.
我们将定义 深度 比赛的 作为为了在所有参赛者中赢得冠军而必须进行的最大比赛场数。
求锦标赛的最小可能深度。
锦标赛结构的正式描述如下。在 i第场比赛,以下其中一场相互对战:
- 两名预定参赛者
- 一名预定参赛者和获胜者 j第一场比赛,其中 j(j<i) 已预定
- 获胜者 j第场比赛和获胜者 k第一场比赛,其中 j 和 k (j,k<i, j ≠ k) 已预定
这种结构是锦标赛的有效结构,当且仅当已经在比赛中失败的参赛者不再参加比赛,无论比赛结果如何。
约束
- 2 ≦ N ≦ 10^5
- 1 ≦ a_i ≦ N(2 ≦ i ≦ N)
- 保证输入是一致的(即至少存在一个与给定信息匹配的锦标赛)。
输入
输入由标准输入按以下格式给出:
N a_2 : a_N
输出
打印锦标赛的最小可能深度。
示例输入 1
5 1 1 2 4
示例输出 1
3
以下赛事及比赛结果与所给信息一致:
- 在第一场比赛中,参赛者 4 和 5 互相对战,参赛者 4 赢了。
- 第二场比赛中,参赛者 2 和 4 互相对战,参赛者 2 赢了。
- 第三场比赛中,参赛者 1 和 3 互相对战,参赛者 1 赢了。
- 第四场比赛,参赛者 1 和 2 互相对战,参赛者 1 赢了。
本次比赛的深度是 3,由于参赛者 5 必须打三场比赛才能赢得冠军。 没有哪场比赛有深度 2 或更少与给定信息一致,因此输出应该是 3.
示例输入 2
7 1 2 1 3 1 4
示例输出 2
3
示例输入 3
4 4 4 1
示例输出 3
3