$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

基础树形 DP 练习题。
设 $dp_{i,0/1}$ 表示以 $i$ 为根的子树，选或不选根节点 $i$ 的最大快乐值。

转移较简单，见代码。

#include <bits/stdc++.h>
using namespace std;
int v[10010], happy[10010];
int dp[10010][2], n;
vector<int> son[10010];
void DP(int x) {
    dp[x][0] = 0;
    dp[x][1] = happy[x];
    for (int i = 0;i < son[x].size(); i++) {
        int y = son[x][i];
        DP(y);
        dp[x][0] += max(dp[y][0], dp[y][1]);
        dp[x][1] += dp[y][0];
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &happy[i]);
    for (int i = 1;i < n; i++) {
        int x, y; scanf("%d%d", &x, &y);
        v[x] = 1;       //x节点有父节点
        son[y].push_back(x);
    }
    int root = 0;
    for (int i = 1;i <= n; i++) if (!v[i]) {root = i; break;}
    DP(root);
    printf("%d\n", max(dp[root][0], dp[root][1]));
    return 0;
}