树形dp2

力扣相同题目：二叉树中的最大路径和也需要看一看，用递归做的

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] node=new int[n+1];
        int[] parent=new int[n+1];
        int[] dp=new int[n+1];
        int[] dp1=new int[n+1];
        for(int i=1;i<=n;i++){
            node[i]=sc.nextInt();
            dp[i]=node[i];
            dp1[i]=node[i];
        }
        for(int i=1;i<=n;i++){
            parent[i]=sc.nextInt();
        }
        int max=0;
        for(int i=n;i>1;i--){
            //dp数组用来记录每次访问的某个节点的单路径最大值，即当前节点，当前节点+左子树或者当前节点+右子树的三者的最大值
            dp[parent[i]]=Math.max(node[parent[i]]+dp[i],node[parent[i]]);
            //dp1用来记录某个节点的最大值，每次从子节点依次向上更新，更新父节点。
            dp1[parent[i]]=Math.max(dp1[parent[i]],dp1[parent[i]]+dp[i]);
            //取每个节点的最大值即为最终结果
            max=Math.max(max,dp1[parent[i]]);
        }
        if(n==1){
            System.out.println(node[1]);
            return ;
        }
        System.out.println(max);
    }
}