3422、左孩子右兄弟

直接使用树型dp的模版之后加上一下规律就行

#include<iostream>
#include<cstring>
using namespace std;
//树型Dp 
//f[u] =其子树的高度+儿子的个数 
int n;
const int N = 1e5+10;
const int M = N*2;
int e[M],ne[M],h[N],idx;
int f[N];
int num[N];
void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs(int u,int father)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j= e[i];
        if(j!=father)
        {
            dfs(j,u);
            f[u] = max(f[u],f[j]+num[u]);
        }
    }
}
int main()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    int a;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&a);
        add(i,a);
        add(a,i);
        num[a]++; 
    }
    dfs(1,-1);
    cout<<f[1];
}