解题思路

这道题求的是二叉树任意两个结点的最大路径和，因此计算思路是从最下层的子结点往上计算，记录每个结点的最大路径长度，一路算到根结点。

在记录每个结点的最大路径长度时，还要考虑该结点跟它的左右子结点是不是最终的最大路径。

计算方法

1.每个结点dp值的计算

要么跟左子树连接，要么跟右子树连接，要么自身

2.最大路径和计算

每个结点都要算一次最大和，4种情况：跟左子树连接、跟右子树连接、跟左右子树一起连接、自身。

3.记录每个结点的子结点

因为这道题特殊的输入方式，二叉树是从上到下输入结点，每个结点只知道对应的父结点。但我们计算时要找子结点，因此用一个child数组记录子结点。

代码 

import java.util.Scanner;

public class Main{
     
    public static void main(String[] args){
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] node = new int[n];
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            node[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            parent[i] = sc.nextInt();
        }
        
        // 记录子节点
        int[][] child = new int[n][2];

        for (int i = 0; i < n; i++) {
            child[i][0] = child[i][1] = -1;

            if (parent[i] > 0) {
                int[] childNode = child[parent[i] - 1];
                if (childNode[0] == -1) {
                    childNode[0] = i;
                } else {
                    childNode[1] = i;
                }
            }
        }

        int max = node[0];
        int[] dp = new int[n];
        // 从子节点往父节点记录dp
        for (int i = n - 1; i >= 0; i--) {
            int left = 0, right = 0;
            if (child[i][0] != -1)
                left = dp[child[i][0]];
            if (child[i][1] != -1)
                right = dp[child[i][1]];
            dp[i] = Math.max(Math.max(left, right), 0) + node[i];
            max = max(max, node[i], node[i] + left, node[i] + right, node[i] + left + right);
        }
        System.out.println(max);
        
    }
    
    public static int max(int a, int b, int c, int d, int e) {
        return Math.max(Math.max(Math.max(Math.max(a, b), c), d), e);
    }
}