python/TangDou/AcWing/TreeDP/285.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 6010;

int happy[N]; // 快乐值
int in[N];    // 入度
int f[N][2];  // dp的状态结果数组
int n;

// 构建邻接表
int h[N], e[N], ne[N], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 通过深度优先搜索，对树进行遍历
void dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        dfs(v);                           // 继续探索它的孩子,它的值是由它的孩子来决定的
        f[u][1] += f[v][0];               // 它选择了，它的孩子就不能再选
        f[u][0] += max(f[v][0], f[v][1]); // 它不选择，那么它的每一个孩子，都是可以选择或者不选择的
    }
    // 不管是不是叶子结点，都会产生happy[u]的价值
    f[u][1] += happy[u];
}

int main() {
    // 邻接表表头初始化
    memset(h, -1, sizeof h);

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

    // 读入树
    for (int i = 1; i < n; i++) { // n-1条边
        int x, y;
        cin >> x >> y;
        add(y, x);
        in[x]++; // 记录入度，因为需要找出大boss
    }

    // 从1开始找根结点
    int root = 1;
    while (in[root]) root++; // 找到根结点,入度为0

    // 递归
    dfs(root);

    // 取两个
    printf("%d\n", max(f[root][0], f[root][1]));

    return 0;
}