洛谷 题解 P1352 【没有上司的舞会】

树形DP的一道较为基础的模板题

• 状态

dp[i][0/1]为第i个员工是否来参加的最大值

• 转移

先找到根节点
先遍历完它的儿子，再来更新答案
dp[i][0]+=max(dp[j][0],dp[j][1]);//j为i的儿子，i不来，那j可来可不来
dp[i][1]+=dp[j][0];//j为i的儿子，i来，那只能不来

• 初始

dp[i][0]=0;//不来的初始值为0
dp[i][1]=r[i];//来的初始值就是此人的快乐指数

• 答案

很明显就是大BOSS来不来的问题了
max(dp[root][0],dp[root][1]);

完整代码:

#include<bits/stdc++.h>
using namespace std;
const int N=6000+10;
int n,m;
int r[N];
bool v[N];
vector<int>son[N];
int dp[N][2];
inline int read()
{
	int tot=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		tot=tot*10+c-'0';
		c=getchar();
	}
	return tot*f;
}
inline void f(int now)
{
	dp[now][0]=0;
	dp[now][1]=r[now];
	for(int i=0;i<son[now].size();i++)
	{
		int x=son[now][i];
		f(x);
		dp[now][0]+=max(dp[x][0],dp[x][1]);
		dp[now][1]+=dp[x][0];
	}
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)r[i]=read();
	int x,y;
	for(int i=1;i<n;i++)
	{
		x=read();y=read();
		son[y].push_back(x);
		v[x]=1;
	}
	int root;
	for(int i=1;i<=n;i++)
	if(!v[i])
	{
		root=i;
		break;	
	}
	f(root);
	int ans=max(dp[root][1],dp[root][0]);
	cout<<ans<<endl;
	return 0;
}