算法刷题目二叉树
Source
Edit
History

派对的最大快乐值

一、题目

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

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

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

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

3.你的目标是让派对的整体快乐值尽量大。

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

输入描述：

第一行两个整数 n 和 root，n 表示公司的总人数，root 表示公司的老板。

第二行 n 个整数 happy_i 表示员工 i 的快乐值。

接下来 n - 1 行每行两个整数 u_i 和 v_i 表示 u_i 是 v_i 的直接上级。

输出描述：

输出一个整数表示最大快乐值。

题目链接：https://www.nowcoder.com/practice/a5f542742fe24181b28f7d5b82e2e49a?tpId=101&tqId=33255&tPage=1&rp=1&ru=%2Fta%2Fprogrammer-code-interview-guide&qru=%2Fta%2Fprogrammer-code-interview-guide%2Fquestion-ranking&tab=answerKey

二、分析

树形 DP 的套路，

当前节点有两种选择，来和不来。

来的情况，当前节点的快乐值加上下级节点不来的快乐值

不来的情况，0 加上（下级节点来或者不来的快乐值）

上下级之间是一个多叉树。这个题目和 二叉树节点间的最大距离问题很相似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>

struct MultiTree {
    int happy;
    std::vector<MultiTree*> sub_arr;

    explicit MultiTree(int val) : happy(val) {}
};

struct Elem {
    int ok_happy;
    int no_happy;

    Elem(int ok_happy_, int no_happy_) : ok_happy(ok_happy_), no_happy(no_happy_) {}
};

class Solution {
public:
    int get_max_happy(const MultiTree* tree) {
        auto info = process(tree);
        return std::max(info.ok_happy, info.no_happy);
    }

private:
    Elem process(const MultiTree* tree) {
        if (tree->sub_arr.empty()) {
            return Elem(tree->happy, 0);
        }
        int ok = tree->happy;
        int no = 0;
        for (int i = 0; i < tree->sub_arr.size(); ++i) {
            auto info = process(tree->sub_arr[i]);
            ok += info.no_happy;
            no += std::max(info.no_happy, info.ok_happy);
        }
        return Elem(ok, no);
    }
};

int main() {
    int n, root;
    std::cin >> n >> root;
    std::vector<MultiTree*> arr(n);
    int val;
    for (int i = 0; i < n; i++) {
        std::cin >> val;
        arr[i] = new MultiTree(val);
    }
    int u, v;
    for (int i = 1; i < n; i++) {
        std::cin >> u >> v;
        arr[u-1]->sub_arr.emplace_back(arr[v-1]);
    }
    Solution s;
    auto res = s.get_max_happy(arr[root-1]);
    std::cout << res << std::endl;
    return 0;
}