【思路】
题目的意思是选出一些点,这些点中不存在两个点有边相连,换句话说这道题求得是树的最大权值的独立集合
我们使用树形DP来递归求解
- 状态表示:
f[u][1]
表示选u
点时,u
和其子树所能选的最大快乐指数 ;f[u][1]
表示不选u
点时u
和其子树所能选的最大快乐指数 -
状态转移: 当
u
点不选时,那么它的子节点都可选或不选,f[u][0]
= $\sum max(f[k][0], f[k][1])$,设k
是u
的子节点。当u
点选时,那么它的子节点不可选,f[u][1]
= $\sum max(f[k][0]) + w[u])$ -
递归
我们先找出根节点u
,从这个点开始进行 $dfs$搜索,每次初始化f[u][1] = w[u]
和f[u][0] = 0
当递归到某个子树最底部的叶子节点时,才开始计算f
数组,然后从底部向上回溯出父节点的f
数组值,递归完一个子树再处理另一个子树,最后汇总到根节点的f
值。
AC代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 6010;
int h[N], e[N], ne[N], idx, w[N];
int n;
int f[N][2], st[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs(int u) {
f[u][1] = w[u], f[u][0] = 0; // 初始化结点 u 选或者不选
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
dfs(j);
f[u][0] += max(f[j][1], f[j][0]);
f[u][1] += f[j][0];
}
}
int main() {
memset(h, -1, sizeof h);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> w[i];
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
add(b, a); // b指向a
st[a] = true; // 有父节点
}
int u = 1;
// u找出根节点:即没有父节点的点
for (int i = 1; i <= n; i++) {
if (!st[i]) {
u = i;
break;
}
}
dfs(u);
cout << max(f[u][0], f[u][1]) << endl;
return 0;
}