题目描述某大学有 n 个职员编号为 1…n。他们之间有从属关系也就是说他们的关系就像一棵以校长为根的树父结点就是子结点的直接上司。现在有个周年庆宴会宴会每邀请来一个职员都会增加一定的快乐指数 ri​但是呢如果某个职员的直接上司来参加舞会了那么这个职员就无论如何也不肯来参加舞会了。所以请你编程计算邀请哪些职员可以使快乐指数最大求最大的快乐指数。输入格式输入的第一行是一个整数 n。第 2 到第 (n1) 行每行一个整数第 (i1) 行的整数表示 i 号职员的快乐指数 ri​。第 (n2) 到第 2n 行每行输入一对整数 l,k代表 k是 l 的直接上司。输出格式输出一行一个整数代表最大的快乐指数。这是一道树形dp题目。看这题的描述以及输入我们发现他只是输入了谁是谁的上司并没有告诉我们根是谁所以我们要在dfs之前提前找到root。思考一下root有什么特点他不会被别人当成儿子。所以只需要在输入时标记所有儿子结点然后遍历所有数字看看他当没当过儿子就可以了。然后就是重点——树形dp当到达这个结点时可以选择他或者不选所以dp数组定义为dp[num][0/1].0代表不选1代表选。1.dp[num][0]求和dp[儿子][1]2.dp[num][1]r[num]求和max(dp[儿子][0],dp[儿子][1]);dfs思路会和之前的一样先从根结点遍历到所有叶子结点然后在层层递归到时候动态规划。最后输出max(dp[root][0],dp[root][1])就可以了。AC code#include bits/stdc.h using namespace std; int n; const int MAX100005; vector int g[MAX]; int r[MAX]; bool son[MAX]; int dp[MAX][2]; void dfs(int num) { int sum00; int sum10; for (int i0;ig[num].size();i) { dfs(g[num][i]); sum0dp[g[num][i]][0]; sum1max(dp[g[num][i]][1],dp[g[num][i]][0]); } dp[num][1]r[num]sum0; dp[num][0]sum1; return; } int main () { cinn; for (int i1;in;i) { cinr[i]; } int l,k; for (int i1;in;i) { cinlk; g[k].push_back(l); son[l]1; } int root; for (int i1;in;i) { if (son[i]0) { rooti; break; } } dfs(root); coutmax(dp[root][0],dp[root][1]); return 0; }