5.2 KiB
一、题目描述
Ural
大学有 N
名职员,编号为 1
∼N
。
他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。
每个职员有一个快乐指数,用整数 H_i
给出,其中 1≤i≤N
。
现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。
在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。
输入格式
第一行一个整数 N
。
接下来 N
行,第 i
行表示 i
号职员的快乐指数 Hi
。
接下来 N−1
行,每行输入一对整数 L,K
,表示 K
是 L
的直接上司。
输出格式 输出最大的快乐指数。
输入样例:
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
输出样例:
5
二、理解与分析
-
看完题,知道这是一道与树相关的试题
-
对于某个人来讲,他是否参加都是可以的,但他是否参加直接影响着他下属的选择
- 他参加,那么,他的直接下属不来了,下属的下属不受此影响
- 他不参加,那么,他的直接下属还是有两种选择,参加或不参加
-
分析到这里,似乎这和最初的
01
背包是多么的相像,可以选时,有可能选择,可能放弃;不能选时,直接放弃,这不就是dp
吗? -
因为上面提到了是一道与树相关的试题,在树上
dp
,躲不开dfs
-
如果是
dp
的话,需要设计一下状态的计算结果数组,有人管它叫做 状态表示。那怎么表示呢?dp
的话,强调的是状态转移要方便快捷,第一个维度肯定是子树的根节点,比如f[u]
。 -
如果只有一维就可以的话,就不用考虑增加维度了。我们来思考一下一维是否够用:一个小领导
A
,他要关心自己下属子树的Happy
值最大,他面临两种选择- 自己参加舞会
- 自己不参加舞会
-
这两种选择,使得后继的员工选择会发生变化,导致整体的
Happy
值变化。A
需要思考两种情况,拿到两种情况的最大值后,进行一次max
运算,才是答案。 -
这两种情况,可以视为两条路,分别是在
A
参加和不参加情况下。 -
这两条路径,递推的结果汇总是不一样的,所以增加二维,变成
f[u][0],f[u][1]
,分别- 表示以
u
为根的子树,并且,不选择u
的情况 - 表示以
u
为根的子树,并且,选择u
的情况
- 表示以
-
上面都想明白后,再考虑一些细节
- 如何建树呢?谁向谁建边呢?树一般就是树向分枝建边,也就是 一对多正确,多对一错误
dfs
需要从哪个节点开始进行搜索呢?一般是根,本题没有告诉我们几号员工是大老板,我们还需要根据入度出度的关系来决策谁是大老板。
三、动态规划分析
状态表示
f[u][1]
表示以u
为根节点的子树并且包括u
的总快乐指数
f[u][0]
表示以u
为根节点并且不包括u
的总快乐指数
状态计算
要想求得一棵以u
为根节点的子树的最大指数分为两种:选u
节点或不选u
节点
记点u
的子节点是j
- 1.选
u
,\large f[u][1]=\sum f[v][0]
- 2.不选
u
,\large f[u][0]=\sum max(f[v][1],f[v][0])
记根节点为root
从root
开始dfs
一遍即可
最后输出max(f[root][1],f[root][0])
可以参阅它的姊妹题 AcWing 323
. 战略游戏
四、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 6010;
int happy[N]; // 快乐值
int in[N]; // 入度
int f[N][2]; // dp的状态结果数组
int n;
// 构建邻接表
int h[N], e[N], ne[N], idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 通过深度优先搜索,对树进行遍历
void dfs(int u) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
dfs(v); // 继续探索它的孩子,它的值是由它的孩子来决定的
f[u][1] += f[v][0]; // 它选择了,它的孩子就不能再选
f[u][0] += max(f[v][0], f[v][1]); // 它不选择,那么它的每一个孩子,都是可以选择或者不选择的
}
// 不管是不是叶子结点,都会产生happy[u]的价值
f[u][1] += happy[u];
}
int main() {
// 邻接表表头初始化
memset(h, -1, sizeof h);
cin >> n;
for (int i = 1; i <= n; i++) cin >> happy[i];
// 读入树
for (int i = 1; i < n; i++) { // n-1条边
int x, y;
cin >> x >> y;
add(y, x);
in[x]++; // 记录入度,因为需要找出大boss
}
// 从1开始找根结点
int root = 1;
while (in[root]) root++; // 找到根结点,入度为0
// 递归
dfs(root);
// 取两个
printf("%d\n", max(f[root][0], f[root][1]));
return 0;
}