考察算法：树形 \(DP\)。
题目概述
给你一个树，每个结点有一个“上司”。每个节点都有一个快乐指数 \(h_i\)。
但是，如果有某个节点的上司(父亲)，已经来到了舞会，那么它的儿子就不能去了。
求：最大的快乐指数（所有人的快乐指数之和）。
思路
树形 \(DP\)。设 \(f_{i,0}\) 表示以 \(i\) 作为根节点，不去舞会时的最大欢乐指数。反之，\(f_{i,1}\) 表示 \(i\) 去舞会时，最大的快乐指数。
答案为：\(max(f_{r,0},f_{r,1})\)。\(r\) 代表该树的根。
边界条件：
如果该节点 \(u\) 为叶子节点，则：不去的话没人去，去的话就自己。\(f_{u,0} = 0;f_{u,1} = r_u\)。
状态转移方程设计：
- 如果结点 \(x\) 不去，则它的儿子们去不去都行。\(f_{x,0} += max(f_{u,0},f_{u,1})\)。
- 如果 \(x\) 去，则它的儿子们必须不去。\(f_{x,1} += f_{u,0}\)。
\(u\) 代表 \(x\) 的每一个子节点。
最后，搞定 \(AC\) ！
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 6e3 + 10;
int Happy[N], deg[N], fa[N]; // deg[] 表示每一个节点的度。
int n, f[N][2];
// 链式前向星
struct node {
int to, next;
} a[N];
int pre[N], k, father, son;
void add(int x, int y) {
a[++k] = (node){y, pre[x]};
pre[x] = k;
fa[y] = x;
deg[x]++; // 记录出边
}
void dfs(int x) {
for (int i = pre[x]; i; i = a[i].next) {
int to = a[i].to;
dfs(to);
f[x][0] += max(f[to][0], f[to][1]); // 这个点不来，儿子来不来都行，去max
f[x][1] += f[to][0]; // 这个点来，儿子不能来
}
f[x][1] += Happy[x];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &Happy[i]);
for (int i = 1; i < n; i++) {
scanf("%d%d", &son, &father);
add(father, son);
}
int ans;
for (int i = 1; i <= n; i++) {
if (!fa[i]) { // 这个点是根，从根开始搜。
dfs(i);
ans = max(f[i][0], f[i][1]);
break;
}
}
printf("%d", ans);
return 0;
}