程序员代码面试指南 3.21：派对的最大快乐值

1、思路

• 多叉树问题，每名员工有若干个直接下级员工，除老板外，每名员工都有唯一的直接上级；

• 某一级节点来不来参加派对，要看这级节点来还是不来两种情况下，哪一种获得的收益最多，分两种情况：

  1、当前节点来参加派对收的益 = 当前节点的快乐值 + 其所有子节点不来参加派对的收益之和（注意：子节点不来参加派对的收益不一定为0，因为它的孙子节点可能来参加，这种情况要递归计算）；

  2、当前节点不来参加派对的收益 = max(子节点来参加派对的收益， 子节点不来参加派对的收益)。

2、代码

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode
{
    int happy;
    vector<TreeNode*> employees;

    TreeNode(int _happy) : happy(_happy) {}
};

struct ReturnData
{
    int yes;        //该员工来参加派对的收益
    int no;         //该员工不来参加派对的收益

    ReturnData(int _yes, int _no) : yes(_yes), no(_no) {}
};

ReturnData* getMax(TreeNode *node)
{
    int yesNode = node->happy;      //该员工来参加派对的收益就是他本身的快乐值
    int noNode = 0;                 //不来参加，收益先初始化为 0

    if (node->employees.empty())
    {
        return new ReturnData(yesNode, noNode);
    }
    else                            //若子树不为空，继续递归计算子员工来与不来的收益
    {
        for (auto employee : node->employees)
        {
            ReturnData *subTreeInfo = getMax(employee);
            yesNode += subTreeInfo->no;
            noNode += max(subTreeInfo->yes, subTreeInfo->no);
        }
    }

    return new ReturnData(yesNode, noNode);
}

int main()
{
    int n, root;
    cin >> n >> root;

    int happyVal, boss, employee;
    vector<TreeNode*> happy(n + 1);

    for (int i = 1; i <= n; ++ i)   //一共有 n 个员工，下标从 1 开始
    {
        cin >> happyVal;
        happy[i] = new TreeNode(happyVal);
    }

    for (int i = 2; i <= n; ++ i)   //除老板外一共有 n - 1 个员工，下标从 2 开始
    {
        cin >> boss >> employee;
        happy[boss]->employees.push_back(happy[employee]);
    }

    ReturnData *allTreeInfo = getMax(happy[root]);          //从根节点的老板开始
    cout << max(allTreeInfo->yes, allTreeInfo->no) << endl;

    return 0;
}