AcWing 285. 没有上司的舞会（树形DP）

题面链接

https://www.acwing.com/problem/content/description/287/

思路

对于每一个员工都不希望自己和直接上司参加宴会，那么我们对于当前这个节点就有两种选法选和不选，于是我们定义 f [ p ] [ 0 ] f[p][0] f[p][0]表示不选p这个点的且以当前点为根的子树选法最大值， f [ p ] [ 1 ] f[p][1] f[p][1]表示选p这个点的且以当前点为根的子树选法最大值,假设 p p p的子节点集合为 V V V那么显然 f [ p ] [ 0 ] = ∑ m a x ( f [ V i ] [ 0 ] , f [ V i ] [ 1 ] ) f[p][0] = \sum{max(f[V_i][0],f[V_i][1])} f[p][0]=∑max(f[Vi​][0],f[Vi​][1])， f [ p ] [ 1 ] = w [ p ] + ∑ f [ V i ] [ 0 ] f[p][1] = w[p] + \sum{f[V_i][0]} f[p][1]=w[p]+∑f[Vi​][0]，于是我们先递归处理叶子节点，然后再归的时候做一个抉择就好啦，详情请看代码

代码

#include
using namespace std;

const int N = 6e3+10;
vector E[N];
int n,w[N],dp[N][2],d[N];
//dp[p][0]表示的是 不选p这个点的子树选法最大值
//dp[p][1]表示的是 选p这个点的子树选法的最大值

void tree_dp(int p){
//	if(E[p].empty()) return;
	dp[p][1] = w[p];
	int ans = 0;
	for(int i = 0,l = E[p].size();i >n;
	for(int i = 1;i >w[i];
	
	int u,v;
	for(int i = 1;i >u>>v,E[v].push_back(u),d[u]++;
	int root = 1;
	for(int i = 1;i