|
|
##[$AcWing$ $285$. 没有上司的舞会](https://www.acwing.com/problem/content/287/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
$Ural$ 大学有 $N$ 名职员，编号为 $1$∼$N$。
|
|
|
<b>他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。</b>
|
|
|
|
|
|
每个职员有一个快乐指数，用整数 $H_i$ 给出，其中 $1≤i≤N$。
|
|
|
|
|
|
现在要召开一场周年庆宴会，不过，**没有职员愿意和直接上司一起参会**。
|
|
|
|
|
|
在满足这个条件的前提下，主办方希望邀请一部分职员参会，<b>使得所有参会职员的快乐指数总和最大，求这个最大值</b>。
|
|
|
|
|
|
**输入格式**
|
|
|
|
|
|
第一行一个整数 $N$。
|
|
|
|
|
|
接下来 $N$ 行，第 $i$ 行表示 $i$ 号职员的快乐指数 $Hi$。
|
|
|
|
|
|
接下来 $N−1$ 行，每行输入一对整数 $L,K$，表示 $K$ 是 $L$ 的直接上司。
|
|
|
|
|
|
**输出格式**
|
|
|
输出最大的快乐指数。
|
|
|
|
|
|
**输入样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
7
|
|
|
1
|
|
|
1
|
|
|
1
|
|
|
1
|
|
|
1
|
|
|
1
|
|
|
1
|
|
|
1 3
|
|
|
2 3
|
|
|
6 4
|
|
|
7 4
|
|
|
4 5
|
|
|
3 5
|
|
|
```
|
|
|
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
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$的情况
|
|
|
|
|
|
* 上面都想明白后，再考虑一些细节
|
|
|
* 如何建树呢？谁向谁建边呢？树一般就是树向分枝建边，也就是 <font color='red' size=4><b>一对多正确，多对一错误</b></font>
|
|
|
* $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$ . 战略游戏](https://www.cnblogs.com/littlehb/p/15788291.html)**
|
|
|
|
|
|
### 四、实现代码
|
|
|
```cpp {.line-numbers}
|
|
|
#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;
|
|
|
}
|
|
|
```
|
