题解 | #派对的最大快乐值#

package interview;

import java.util.*;

/*
字节面试一面算法题

 */
public class Main{
    static class TreeNode {
        int val;
        List<TreeNode> childs;

        public TreeNode() {
        }

        public TreeNode(int val, List<TreeNode> childs) {
            this.val = val;
            this.childs = childs;
        }
    }

    //广度优先遍历 树形dp
    //inhappy是参加 outhappy不参加
    //参加了子节点都不能参加info[1],不参加子节点可参加info[0]可不参加info[1],取较大
    public static int[] findMaxHappy(TreeNode root) {
        int inhappy = root.val, outhappy = 0;
        for (TreeNode node : root.childs) {
            int[] info = findMaxHappy(node);
            inhappy += info[1];
            outhappy += Math.max(info[0], info[1]);
        }
        return new int[]{inhappy, outhappy};
    }

    public static void main(String[] args) {
        HashMap<Integer, TreeNode> map = new HashMap<>();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();
        int[] a = new int[n];
        for (int i = 1; i <= n; i++) {
            int happy = sc.nextInt();
            TreeNode node = new TreeNode(happy, new ArrayList<TreeNode>());
            map.put(i, node);
        }
        for (int i = 0; i < n - 1; i++) {
            int j = sc.nextInt();
            int k = sc.nextInt();
            map.get(j).childs.add(map.get(k));
        }
        int[] maxHappy = findMaxHappy(map.get(root));
        System.out.println(Math.max(maxHappy[0], maxHappy[1]));
    }
}