[AGC009B] Tournament
题意翻译
有$n$个选手进行淘汰赛,每场比赛后输的一方就会立刻被淘汰。现在比赛已经结束,我们已知$1$号是最后的胜者,而第$i(i>1)$号是被$a_i$号淘汰的。
让我们假设回到比赛开始前的时刻,请问所有选手中,如果想要取得胜利,必须赢的场数最多的那位选手,至少要赢多少场?
题目描述
[problemUrl]: https://atcoder.jp/contests/jrex2017/tasks/agc009_b
$ N $ 人の人が大会に出場しました。この大会はトーナメント形式であり、$ N-1 $ 回の試合が行われました。 諸事情により、このトーナメントは全参加者に平等に組まれているとは限りません。 すなわち、各人に対し、優勝するために必要なその人が勝者となるような試合数が等しいとは限りません。 トーナメントの構造は、正式には問題文の末尾で定義されます。
各試合では必ず片方の人が勝者、もう片方の人が敗者となり、最後まで負けなかった $ 1 $ 人が優勝となります。
![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT_agc009_b/60b2a9eae65eb70a75e8c33bcbb94cf7111ee45a.png)図: トーナメントの例
人には $ 1 $ から $ N $ までの番号がついており、$ 1 $ 番の人が優勝し、優勝者以外の人 $ i(2\ ≦\ i\ ≦\ N) $ は人 $ a_i $ との試合で負けました。
トーナメントの深さとは、すべての人に対する、その人が優勝するために必要な、その人が勝者となるような試合数の最大値です。
トーナメントの深さとしてありうる最小の値を求めてください。
トーナメントの構造の正式な定義は以下の通りです。$ i $ 回目の試合では、
- あらかじめ決められた、まだ試合をしていない $ 2 $ 人の人
- あらかじめ決められたまだ試合をしていない人 $ 1 $ 人と、あらかじめ決められた $ j(j\ <\ i) $ に対する、$ j $ 回目の試合の勝者
- あらかじめ決められた $ j,k(j,k\ <\ i,\ j\ ≠\ k) $ に対する、$ j $ 回目の試合の勝者と $ k $ 回目の試合の勝者
のうちのいずれかの $ 2 $ 人が試合を行います。このような構造であって、どのように試合結果を決めても、すでに一度試合に負けた人が再び試合をすることのないようなものをトーナメントと呼びます。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ a_2 $ : $ a_N $
输出格式
トーナメントの深さとしてありうる最小の値を出力せよ。
输入输出样例
输入样例 #1
5
1
1
2
4
输出样例 #1
3
输入样例 #2
7
1
2
1
3
1
4
输出样例 #2
3
输入样例 #3
4
4
4
1
输出样例 #3
3
说明
### 制約
- $ 2\ ≦\ N\ ≦\ 10^5 $
- $ 1\ ≦\ a_i\ ≦\ N(2\ ≦\ i\ ≦\ N) $
- 入力の試合結果と合致するようなトーナメントが存在する
### Sample Explanation 1
次のような試合結果が条件を満たします。 - $ 1 $ 回目の試合では、人 $ 4 $ と 人 $ 5 $ が対戦し、人 $ 4 $ が勝つ - $ 2 $ 回目の試合では、人 $ 2 $ と 人 $ 4 $ が対戦し、人 $ 2 $ が勝つ - $ 3 $ 回目の試合では、人 $ 1 $ と 人 $ 3 $ が対戦し、人 $ 1 $ が勝つ - $ 4 $ 回目の試合では、人 $ 1 $ と 人 $ 2 $ が対戦し、人 $ 1 $ が勝つ !\[783f7be9c88350e31963edba8a958879.png\](https://atcoder.jp/img/agc009/783f7be9c88350e31963edba8a958879.png) このトーナメントは、人 $ 5 $ が優勝するためには $ 3 $ 回勝利する必要があるので、深さ $ 3 $ のトーナメントとなります。 逆に、深さ $ 2 $ 以下の条件を満たすトーナメントは存在しないので、$ 3 $ を出力します。