没有上司的舞会 - 树形动态规划

题意

某大学有 \(n\) 个职员，编号为 \(1\ldots n\)。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 \(r_i\)，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入的第一行是一个整数 \(n\)。

第 \(2\) 到第 \((n + 1)\) 行，每行一个整数，第 \((i+1)\) 行的整数表示 \(i\) 号职员的快乐指数 \(r_i\)。

第 \((n + 2)\) 到第 \(2n\) 行，每行输入一对整数 \(l, k\)，代表 \(k\) 是 \(l\) 的直接上司。

输出一行一个整数代表最大的快乐指数。

样例输入输出

算法

树形动态规划 (树形DP)

\(\to\) OI-Wiki

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。

解题思路

对于这道题目，我们首先建树，然后递归处理每一个树上的节点，最后找最大值。

由于这道题目中没有给出明确的根节点的编号，因此我们需要找到这个根节点，而根节点的性质是没有父节点，因此循环判断这个点有没有父亲节点即可。

1. 确定状态

二维状态。

\(f_{u, 0}\) 表示所有从以 \(u\) 为根的子树中选择，并且不包含 \(u\) 点的最大高兴值。

\(f_{u, 1}\) 表示所有从以 \(u\) 为根的子树中选择，并且包含 \(u\) 点的最大高兴值。

2. 划分阶段 & 决策选择

递归处理 \(u\) 点的所有子节点。

对于求 \(f_{u, 0}\)

如果求 \(f_{u, 0}\)，则代表不选 \(u\) 这个点，那么 \(u\) 点的所有子节点都可选可不选。所以 \(f_{u, 0} = \sum \max(f_{v, 0}, f_{v, 1})\)，其中 \(v\) 是 \(u\) 的所有子节点。

对于求 \(f_{u, 1}\)

如果求 \(f_{u, 1}\)，则代表选 \(u\) 这个点，那么 \(u\) 点的所有子节点都不可选。所以 \(f_{u, 1} = r_u + \sum f_{v, 0}\)，其中 \(v\) 是 \(u\) 的所有子节点。

3. 求解目标

最终求的是所有人的总情况，也就是跟这棵树的根节点有关。而根节点可选可不选，所以最终答案为 \(\max(f_{root, 1}, f_{root, 0})\)。

代码

#include <iostream>
#include <vector>

using namespace std;

const int N = 6e3 + 10;

int n, l, k, root = 1;
int r[N];
int f[N][2];
/*
f[i][0] 表示所有从以 u 为根的子树中选择，并且不包含 u 点的最大高兴值
f[i][1] 表示所有从以 u 为根的子树中选择，并且包含 u 点的最大高兴值
*/
bool has_father[N];		// 存储每个节点是否都存在父节点，不存在的点为根节点 
vector<int> g[N];		// 邻接表 

void dp(int u){
	// 加上 u 点的高兴值 
	f[u][1] += r[u];
	
	for(auto v : g[u]){	// 枚举 u 的左右子节点 
		dp(v);			// 递归 
		f[u][0] += max(f[v][0], f[v][1]);
		f[u][1] += f[v][0];
	}
}

int main(){
	// 读入 
	scanf("%d", &n);
	
	for(int i=1; i<=n; i++)
		scanf("%d", r + i);
	
	for(int i=1; i<n; i++){
		scanf("%d %d", &l, &k);
		has_father[l] = true;	// 标记 l 点存在父节点 
		g[k].push_back(l);
	}
	
	// 寻找根节点 
	while(has_father[root])
		root++;
	
	dp(root); 	// 树形 DP 
	
	
	printf("%d", max(f[root][1], f[root][0]));	// 找最大值输出 
	
	return 0;
}