package com.jiucaiyuan.net.algrithm.tree;



import java.util.List;



/**

 * <pre>

 * 树形dp套路

 * 树形dp套路使用前提：

 * 如果题目求解目标是S规则，则求解流程可以定成每一个节点为头节点的子树

 * 在S规则下的每个答案，并且最终答案一定在其中

 * 案例题

 * 【题目】派对的最大快乐值

 * 员工信息定义如下

 * class Employee{

 * public int happy; //这名员工带来的快乐值

 * List<Employee> subordinates; //这名员工有哪些直接下级

 * }

 * 公司每名员工都符合Employee类的描述，整个公司的人员结构可以看做是

 * 标准的、没有环的多叉树，树的头结点可以看做是公司唯一的老板，除了老板

 * 外，每个员工都有唯一的上级。叶子结点是没有直接下级的基层员工（subordinates

 * 列表为null），除了基层员工外，每个员工都有一个或多个直接下级。

 * 这个公司要办party，你可以决定哪些员工来，哪些员工不来，但是要遵循

 * 如下规则：

 * 1.如果某个员工来了，那么这个员工的直接下级都不能来；

 * 2.派对的整体快乐值是到场的所有员工快乐值的累加；

 * 3.你的目标是让派对的整体快乐值最大；

 * 给定一个多叉树的头结点boss，请返回派对的最大快乐值

 * 【思路】

 * 划分为几种情况：

 * 1.头结点参与，最大快乐值=直属员工不参与的情况下最大快乐值的累加和；

 * 2.头结点不参与，轮训所有直属员工，直属员工来的情况下最大快乐值的累加和+直属员工不来的情况下最大快乐累加值；

 * 从两种中累加，就是整party最大的快乐值

 * 子树返回的结果：头结点来时的最大快乐值，头结点不来时的最大快乐值

 * </pre>

 *

 * @Author jiucaiyuan  2022/5/6 23:06

 * @mail services@jiucaiyuan.net

 */



public class MaxHappyValue {

    public static class Employee {

        public int happy;

        public List<Employee> subordinates;

    }



    public static class Info {

        public int yesMaxHappy;  //来的时候最大快乐值

        public int noMaxHappy;   //不来时最大快乐值



        public Info(int yes, int no) {

            this.yesMaxHappy = yes;

            this.noMaxHappy = no;

        }

    }



    /**

     * 取得以boss为老板的公司组织party获得的最大快乐值

     *

     * @param boss 整个公司唯一的老板

     * @return 最大快乐值

     */

    public static int maxHappy(Employee boss) {

        Info info = process(boss);

        return Math.max(info.yesMaxHappy, info.noMaxHappy);

    }



    /**

     * @param employee 当前员工来与不来获得的最大快乐值

     * @return

     */

    private static Info process(Employee employee) {

        if (employee == null) {

            return new Info(employee.happy, 0);

        }

        //当前员工来，再统计直属下级不来时最大快乐值累加

        int yes = employee.happy;

        //当前员工不来，再统计直属下级来与不来时最大快乐值累加

        int no = 0;

        for (Employee e : employee.subordinates) {

            Info eInfo = process(e);

            //当前员工来，直接下属不来时的快乐值

            yes += eInfo.noMaxHappy;

            //当前员工不来，下属可以来也可以不来，得到最大快乐值

            no += Math.max(eInfo.yesMaxHappy, eInfo.noMaxHappy);

        }

        return new Info(yes, no);

    }

}