この問題は、以下のような動的計画法(DP)を用いることにより解くことができます。

動的計画法とは、小さいサイズの部分問題から順に解いていって答えをメモしていき、大きいサイズの問題は小さいサイズの問題の答えを元に計算するようなアルゴリズムのことを言います。

「\(\mathrm{DP}[i]=\) 人 \(1\) は人 \(i\) の何代前か」という長さ \(N\) の配列 \(\mathrm{DP}\) を考えます。このとき、解は \(\mathrm{DP}[N]\) です。

まず、\(\mathrm{DP}[1]=0\) です。

人 \(i\) の親が人 \(P_i\) であることより、\(\mathrm{DP}[i]=\mathrm{DP}[P_i]+1\) であることがわかります。

\(i=2,3,\dots,N\) の順に上の式を使い \(\mathrm{DP}[i]\) を求めることで \(\mathrm{DP}[N]\) を求めることができます。

全体の計算量は \(\mathrm{O}(N)\) です。

ちなみに、この問題はグラフの用語を使うと以下のように言い換えられます。

$N$ 頂点の根付き木があります。根は頂点 $1$ です。 頂点 $i(2 \le i \le N)$ の親は頂点 $P_i$ です。ここで、$P_i < i$ であることが保証されます。 頂点 $1$ と頂点 $N$ の距離を求めてください。

上記の言い換えをすることで、BFS や DFS によってもこの問題を解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=1;i<n;i++){
    cin>>a[i];
    a[i]--;
  }
  vector<int> dp(n);
  for(int i=1;i<n;i++){
    dp[i]=dp[a[i]]+1;
  }
  cout<<dp[n-1]<<endl;
}