题目传送门
最近做的题真是越来越水了（以前没有自己做过树形 DP 题，所以特来水一篇博客）
好了，进入正题。
思路
上司和下属的关系就是一种树形关系，上下级共同构成了一棵树，我们要考虑在这棵树里进行 DP。
由于上司对下属是有影响的（即上司选了下属就不能选了），这是有后效性的吗，所以需要从下属到上司进行 DP，因为下属的选择不会影响到上司的选择。（输入方式已经暗示了一切，因为先输入下属再输入其上司）
用一个二维数组表示状态。dp[v][0/1] 表示到节点 v 所获得的最大快乐指数，0/1 表示是否选择当前点 v。
易推出状态转移方程为
（其中 u 是 v 的下属）
这两个方程也很好理解，即上司不去选择下属去不去的快乐指数最大值；上司去时下属不能去，所以只加上上司自己的快乐指数。
最后取所有 dp 数组中的数的最大值就可以了。
写代码时需要从底层向上递推，最底层的点是没有入度的，所以可以维护一个队列，每次加入没有入度的点，枚举其上司，而且在枚举到这个点的子节点时让入度减 1（相当于它的下属已经枚举过了，上司入度要减去 1）
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int maxN = 6005;
struct Edge {
int next, to;
} edge[maxN << 1];
int head[maxN], ha[maxN], indeg[maxN];
int dp[maxN][2];
int cnt, n, ans;
queue<int> que;
void add(int from, int to) {
edge[++cnt].next = head[from];
edge[cnt].to = to;
head[from] = cnt;
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &ha[i]);
for (int i = 1; i < n; i++) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
indeg[b]++;
}
for (int i = 1; i <= n; i++) {
dp[i][1] = ha[i]; // 直接把快乐指数赋值给 dp[i][1] 了
if (!indeg[i]) que.push(i);
}
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
dp[v][1] += dp[u][0];
dp[v][0] += max(dp[u][0], dp[u][1]);
indeg[v]--;
if (!indeg[v]) que.push(v);
}
}
for (int i = 1; i <= n; i++)
ans = max(ans, max(dp[i][0], dp[i][1]));
printf("%d\n", ans);
return 0;
}