派对最大快乐值

题目描述 #

整个公司的人员结构可以看作是一棵标准的多叉树。树的头节点是公司唯一的老板，除老板外，每个员工都有唯一的直接上级，叶节点是没有任何下属的基层员工，除基层员工外，每个员工都有一个或多个直接下级，另外每个员工都有一个快乐值。

这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下的原则：

1. 如果某个员工来了，那么这个员工的所有直接下级都不能来。
2. 派对的整体快乐值是所有到场员工快乐值的累加。
3. 你的目标是让派对的整体快乐值尽量大。

给定一棵多叉树，请输出派对的最大快乐值。

二叉树递归套路 #

1. X 节点来，x.value + a 不来的 max + b 不来的 max + c 不来的 max…
2. X 节点不来
   • max(a 来，a 不来) + max(b 来，b 不来) + max(c 来，c 不来) +…

class Solution {
 private:
  struct Info {
    int yes, no;
    Info(int yes, int no) : yes(yes), no(no){};
  };

  Info* process(Employee* x) {
    if (x == nullptr) return new Info(0, 0);
    int no = 0, yes = x->happys;
    for (Employee* next : x->nexts) {
      Info* nextInfo = process(next);
      no += max(nextInfo->no, nextInfo->yes);
      yes += nextInfo->no;
    }

    return new Info(yes, no);
  }

 public:
  int maxHappy(Employee* boss) {
    Info* info = process(boss);
    return max(info->no, info->yes);
  }
};