← 返回题目列表

AtCoder · agc009_b

B. 锦标赛

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

分数: 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 赢了。
783f7be9c88350e31963edba8a958879.png

本次比赛的深度是 3,由于参赛者 5 必须打三场比赛才能赢得冠军。 没有哪场比赛有深度 2 或更少与给定信息一致,因此输出应该是 3.


示例输入 2

7
1
2
1
3
1
4

示例输出 2

3

示例输入 3

4
4
4
1

示例输出 3

3