求める答えは親のアメーバに対する答え \(+1\) になります。したがって、各アメーバが生まれたタイミングで答えを記録することで、\(O(N)\) で解くことができます。

実装例(Python)

N=int(input())
A=list(map(int,input().split()))
ans=[0]*(2*N+1)
for i,a in enumerate(A):
  ans[2*i+1]=ans[a-1]+1
  ans[2*i+2]=ans[a-1]+1

print(*ans,sep="\n")