分析
树形 dp。
定义状态 \(dp_{~i,~0}\) 为在以 \(i\) 为根节点的子树中，不选第 \(i\) 个人的最大快乐值，\(dp_{~i,~1}\) 为在以 \(i\) 为根节点的子树中，选第 \(i\) 个人的最大快乐值。
寻找根节点，然后从根节点开始 dfs，当前节点 \(u\) 的 \(dp\) 初始状态为 \(dp_{~i,~0}=0,~dp_{~i,~1}=happy_{~i}\)。
思考状态转移方程：
注：下文中当前节点以 \(u\) 来表示，\(u\) 的儿子以 \(v\) 来表示。
- 没有选择当前节点这个人：他的下司可以被选择和不被选择，状态转移方程为 \(dp_{~u,~0} = \sum max(dp_{~v,~0},dp_{~v,~1})\),
- 选择当前节点这个人：不能选择他的下司，状态转移方程为 \(dp_{~u,~1} = \sum dp_{~v,~0}\)
Accepted Code
#include <bits/stdc++.h>
using namespace std;
const int N = 6e3 + 5;
struct Edge{
int v, nxt;
}edge[N];
int head[N], happy[N], dp[N][2], in[N];
void dfs(int u)
{
dp[u][0] = 0; dp[u][1] = happy[u];
for (int i = head[u]; i; i = edge[i].nxt)
{
int v = edge[i].v;
dfs(v);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
int main()
{
int n, rt;
cin >> n;
for (int i = 1; i <= n; i++)cin >> happy[i];
for (int i = 1; i < n; i++)
{
int u, v;
cin >> v >> u;
in[v]++;
edge[i] = (Edge){v, head[u]}; head[u] = i;
}
for (int i = 1; i <= n; i++)if (!in[i])rt = i;
dfs(rt);
cout << max(dp[rt][0], dp[rt][1]);
return 0;
}