Consider an array \(\mathrm{DP}\) of length \(N\) that stores “\(\mathrm{DP}[i]=\) how many generations away from Person \(i\) is Person \(1\)?” (DP stands for Dynamic Programming.) Here, the solution is \(\mathrm{DP}[N]\).

First, \(\mathrm{DP}[1]=0\).

Since Person \(i\)’s person is Person \(P_i\), we have \(\mathrm{DP}[i]=\mathrm{DP}[P_i]+1\).

We can use the expression above in the order \(i=2,3,\dots,N\) to find \(\mathrm{DP}[i]\) so that we get \(\mathrm{DP}[N]\).

The overall time complexity is \(\mathrm{O}(N)\).

By the way, the problem can be rephrased using the terms of graph theory as follows:

There is a rooted tree with $N$ vertices rooted at Vertex $1$. The parent of Vertex $i(2 \le i \le N)$ is Vertex $P_i$, where $P_i < i$ is guaranteed. Find the distance between Vertex $1$ and Vertex $N$.

The rephrased problem statement above leads you to a solution using BFS and DFS.

Sample Code (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;
}