Luogu P1352没有上司的舞会

分析

树形 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;
}