分析

题意：一棵树中，选择的点不能出现“父子”关系，因为父亲节点就相当于儿子节点的“上司”；不能出现直接上司，但可以出现“上司的上司”

状态表示 ：用 f[i][0] 表示 在不选择 i 的情况下，以 i 为根节点的所有子树中，能够选择的节点最多数目。
f[i][1] 表示 在选择了 i 的情况下，以 i 为根节点的所有子树中，能够选择的节点最多数目。

由于 i 的所有子树相互独立【两棵子树之间不会存在父子节点】，故以 i 为根，能选择的最多节点，就是它的所有子树能选择的最多节点之和，即

//没有选根节点 i，则儿子节点可选可不选，取两者最大计入答案即可
f[i][0] = max(f[son_1][0],f[son_1][1]) +  max(f[son_2][0],f[son_2][1]) + ....

//选了根节点 i，则儿子节点一定不能选
f[i][1] = f[son_1][0] + f[son_2][0] + ....

而答案就是

max (f[root][0], f[root][1])

C++ 代码

#include <cstring>
#include <iostream>
using namespace std;

const int N = 6010;
int n, w[N];                 // w[i] 是i号员工的快乐指数
int h[N], e[N], ne[N], cur;  //邻接表
int f[N][2];
bool st[N];  //表示某个节点是否有父节点

void add(int a, int b) {
    e[cur] = b, ne[cur] = h[a], h[a] = cur++;
}

//搜节点u
void dfs(int u) {
    f[u][0] = 0;  //快乐指数有负数，但最差也是一个员工都不选，快乐指数为0【全局变量本就为0，可不写】
    f[u][1] = w[u];

    for (int i = h[u]; ~i; i = ne[i])  // cur是从0开始的，所以条件是i>=0
    {
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> w[i];

    memset(h, -1, sizeof h);

    for (int i = 1; i <= n - 1; i++)  // n-1对关系
    {
        int a, b;
        cin >> a >> b;
        add(b, a);
        st[a] = true;  // a就有了父节点
    }

    int root = 1;
    while (st[root]) root++;  //找到根节点的员工编号

    dfs(root);

    cout << max(f[root][0], f[root][1]) << endl;
    return 0;
}