AcWing 285. 没有上司的舞会 (树形dp)
原题链接
简单
作者:
NumPy
,
2021-05-10 22:26:05
,
所有人可见
,
阅读 247
树形dp
$O(n)$
C++ 代码
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N = 6010;
int H[N], st[N], n;
int f[N][2];
vector<int> son[N];
// 状态表示: f[root, state]
// f[root, 0] 表示以root为根的数中, 根不参加的情况下可以得到的最大快乐指数
// f[root, 1] 表示以root为根的数中, 根参加的情况下可以得到的最大快乐指数
// 状态计算类似于打家劫舍问题
// 采用中序遍历, 先计算左右子树再更新父节点
void dfs(int root){
if(!root) return;
if(son[root].size() > 0){
for(int i = 0; i < son[root].size(); i++){
dfs(son[root][i]);
}
int x1 = 0, x2 = 0;
for(int i = 0; i < son[root].size(); i++){
x1 += f[son[root][i]][0]; // 直接下属不参加
x2 += f[son[root][i]][1]; // 直接下属参加
}
f[root][0] = max(x1, x2);
f[root][1] = x1 + H[root];
}
else{ // 到达叶子结点
f[root][0] = 0;
f[root][1] = H[root];
}
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &H[i]);
for(int i = 1; i <= n - 1; i++){
int l, k;
scanf("%d %d", &l, &k);
son[k].push_back(l);
st[l] = true;
}
int root;
for(int i = 1; i <= n; i++) if(!st[i]) root = i;
dfs(root);
printf("%d\n", max(f[root][0], f[root][1]));
return 0;
}