E61 树形DP P8744 [蓝桥杯 2021 省 A] 左孩子右兄弟

// 树形DP O(n)
#include <bits/stdc++.h>
using namespace std;

const int N=100005;
int n,f[N],son[N];
int head[N],idx;
struct E{int v,ne;}e[N<<1];
void add(int u,int v){
  e[++idx]={v,head[u]};head[u]=idx;
}

void dfs(int u){
  for(int i=head[u];i;i=e[i].ne){
    int v=e[i].v;
    dfs(v);
    f[u]=max(f[u],f[v]);
  }
  f[u]+=son[u];
}
signed main(){
  cin>>n;
  for(int i=2,u;i<=n;++i)
    cin>>u,add(u,i),++son[u];
  dfs(1);
  cout<<f[1];
}