题目描述

员工信息的定义如下:

struct employee
{
    int happy; // 这名员工可以带来的快乐值
    list<employee*> inferior; // 这名员工有哪些直接下级
    employee(int _happy):happy(_happy){}
};

公司的每个员工都符合 employee 结构体的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。

叶节点是没有任何下属的基层员工(inferior链表为空)，除基层员工外，每个员工都有一个或多个直接下级。这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来。

规则：

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

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

3.你的目标是让派对的整体快乐值尽量大 给定一棵多叉树的头节点 boss，请返回派对的最大快乐值。

思路过程

1. 一个员工只可能出现两种情况：来，或者不来。
2. 一个员工不来有两种情况：上级来了，或者上级没来但自己不想来。
3. 一个员工来，说明：上级没来，且自己想来。
4. 统计一个员工来或者不来情况下的快乐值（包括对下级的影响），取其最大值。

现有公司层级如下图：

struct employee
{
    int happy; // 这名员工可以带来的快乐值
    list<employee*> inferior; // 这名员工有哪些直接下级
    employee(int _happy):happy(_happy){}
};

int process(employee* superior, bool present)
{
    int max = 0;
    auto p = superior->inferior.begin();
    while(p != superior->inferior.end())
    {
        if(present == true)//上级来了,则该员工不能来
            max += process((*p), false);
        else//上级没来，该员工可来可不来
        {
            int go = (*p)->happy + process((*p), true);
            int notGo = process((*p), false);
            max += std::max(go, notGo);
        }
        p++;
    }
    return max;
}

int happyVal(employee* root)
{
    if(root == nullptr)
        return 0;
    int m = std::max(process(root, true), process(root, false));
    return m;
}

测试：

int main()
{
//       4
//     / | \
//    13 3  10
//   /\\    /\\
//  1 3 8  5 3 1
//     / \
//    5   4
    employee* root = new employee(4);
    root->inferior.push_back(new employee(13));
    root->inferior.push_back(new employee(3));
    root->inferior.push_back(new employee(10));
    root->inferior.back()->inferior.push_back(new employee(5));
    root->inferior.back()->inferior.push_back(new employee(3));
    root->inferior.back()->inferior.push_back(new employee(1));
    root->inferior.front()->inferior.push_back(new employee(1));
    root->inferior.front()->inferior.push_back(new employee(3));
    root->inferior.front()->inferior.push_back(new employee(8));
    root->inferior.front()->inferior.back()->inferior.push_back(new employee(5));
    root->inferior.front()->inferior.back()->inferior.push_back(new employee(4));
    int val = happyVal(root);
    std::cout << val;
}