二叉树中的最大路径和

import java.util.*; 

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static class Node {
        public Node(int val) {
            this.val = val;
        }
        public int val;
        public Node left;
        public Node right;
    }
    public static int ans = Integer.MIN_VALUE;
    public static Map<Integer, Node> map = new HashMap<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int nodeNum = in.nextInt();
        in.nextLine();
        if (nodeNum == 0) {
            return;
        }
        int[][] child = new int[nodeNum][2];
        String[] strings1 = in.nextLine().split(" ");
        String[] strings2 = in.nextLine().split(" ");
        for (int i = 1; i <= nodeNum; i++) {
            map.put(i, new Node(Integer.valueOf(strings1[i-1])));
            if (map.get(Integer.valueOf(strings2[i-1])) != null) {
                if (map.get(Integer.valueOf(strings2[i-1])).left == null) {
                    map.get(Integer.valueOf(strings2[i-1])).left = map.get(i);
                } else {
                    map.get(Integer.valueOf(strings2[i-1])).right = map.get(i);
                }
            }
        }

        
        Node root = map.get(1);
        dfs(root);
        System.out.println(ans);
    }

    public static int dfs(Node root) {
        if (root == null) {
            return 0;
        }
        int maxL = Math.max(dfs(root.left), 0);
        int maxR = Math.max(dfs(root.right), 0);

        ans = Math.max(ans, root.val + maxL + maxR);
        return Math.max(root.val + maxL, root.val + maxR);
    }
}