C++编码：描述 某学校有 n 个职员，编号为 1到n。 他们之间有上下级关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。 现在有个周年庆舞会，舞会每邀请来一个职员都会增加一定的快乐指数vali​，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。 所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。 输入 输入的第一行是一个整数n （1<=n<=100000）。 第2到第n+1行，每行一个整数，第i+1行的整数表示i号职员的快乐指数val (-200<=val<=200)。 第n+2到2n行，每行输入一对整数l、k,表示k是l的直接上司。 输出 输出一行一个整数代表最大的快乐指数。 样例输入 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 样例输出 5

这是一道树形 DP 的经典题目，可以使用 DFS 或 BFS 进行求解。以下是一种基于 DFS 的解法：

首先，我们需要定义一个结构体来保存每个职员的信息：

struct Employee {
    int val;  // 快乐指数
    vector<int> subordinates;  // 直接下属的编号
};

然后，我们需要读入输入数据，并构建出以校长为根的树。由于树的形态已经确定，我们可以使用数组来保存每个职员的信息，数组下标即为职员的编号：

int n;
Employee employees[100001];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> employees[i].val;
    }
    for (int i = 1; i < n; i++) {
        int l, k;
        cin >> l >> k;
        employees[l].subordinates.push_back(k);
    }
    // ...
    return 0;
}

接下来，我们可以使用 DFS 来计算最大的快乐指数。对于每个职员，我们需要分别计算其参加舞会和不参加舞会两种情况下的快乐指数。

对于参加舞会的情况，我们需要计算其所有直接下属不参加舞会时的最大快乐指数之和。由于每个职员只能被邀请一次，因此我们需要使用一个 visited 数组来记录每个职员是否已经被邀请过。

对于不参加舞会的情况，我们只需要计算其所有直接下属参加舞会时的最大快乐指数之和即可。

最终，我们需要返回这两种情况中的较大值，并将其加上当前职员的快乐指数。整个过程可以使用递归来实现。

最后，我们只需要从根节点开始调用 DFS，即可得到最大的快乐指数：

int dfs(int u, bool visited[]) {
    visited[u] = true;
    int happy_with_me = employees[u].val;  // 参加舞会的情况
    int happy_without_me = 0;  // 不参加舞会的情况
    for (int v : employees[u].subordinates) {
        if (!visited[v]) {
            happy_with_me += dfs(v, visited->val);
            happy_without_me += dfs(v, visited);
        }
    }
    return max(happy_with_me, happy_without_me);
}

int main() {
    // ...
    bool visited[100001] = {};
    cout << dfs(1, visited) << endl;
    return 0;
}