c++树形dp求解左孩子右兄弟

解题思路:使用邻接表存储树。以当前节点为根的树转换后的最大高度是子节点数量加上子树的最大高度

注意事项:

参考代码:

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e5+10;

int h[N],e[N],ne[N],idx;

int f[N];

void add(int a,int b)

{

    e[idx]=b,ne[idx]=h[a],h[a]=idx++;

}

int dp(int a)

{

    int res=0,sum=0;

    for(int i=h[a];i!=-1;i=ne[i])

    {

        int j=e[i];

        res++;

        sum=max(sum,dp(j));

    }

    res+=sum;

    return res;

}

int main()

{

    int n;

    cin>>n;

    memset(h,-1,sizeof h);

    for(int i=2;i<=n;i++)

    {

        int a;

        cin>>a;

        add(a,i);

    }

    int res=dp(1);

    cout<<res;

    return 0;

}