题解：B4275 [蓝桥杯青少年组省赛 2023] 活动人数
lym2022
·
·
题解
树形 dp 的板子题。
双倍经验
题目大意
给定一棵树的每条边和每个点的点权，规定如果点 u 选了，那么点 u 的儿子 v 就不能选,问可以选出的方案中点权和最大是多少。当 u 为 0 时，点 v 为根节点。
思路
典型的树形 dp。
$f[u][1]$ 表示以 $u$ 为根节点的子树，节点 $u$ 选时的最大值，初始化时因为只有 $u$ 一个节点，所以 $f[u][0]$ 初始化为 $u$ 的点权；
转移时从下向上转移：
当 $u$ 不选时儿子 $v$ 可选可不选，所以 $f[u][0]$ 就加上 $f[v][0]$ 和 $f[v][1]$ 较大的那个（~~不写函数是因为不会用格式~~）;
当 $u$ 选时儿子 $v$ 就不能选，所以 $f[u][1]$ 就加上 $f[v][0]$。
最后就输出根节点选或不选的最大值就好了。
### Code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,a[N],f[N][2],root; //a数组就是点权，root存根节点
vector<int> e[N];
void dfs(int u) { //树形dp
f[u][0] = 0; //不选时，初始化为 0
f[u][1] = a[u]; //选时，初始化为 u 的点权
for(auto v : e[u]) { //便利每个儿子 v
dfs(v); //先搜下去，等到儿子的答案确定了再转移
f[u][1] += f[v][0]; //如果 u 选，v 就不能选
f[u][0] += max(f[v][0],f[v][1]); //否则 v 就可选可不选
}
}
int main() {
cin >> n;
for(int i = 1;i<=n;i++) {
int u,v,w;
cin >> u >> v >> w;
a[v] = w;
if(u == 0) { //如果 u 为 0,那么 v 就是根节点
root = v; //记录根节点
continue;
}
e[u].push_back(v); //邻接表存图
}
dfs(root); //从根节点开始搜
cout << max(f[root][0],f[root][1]); //输出根节点选或不选时答案较大的情况
return 0;
}
```
有兴趣的话可以浏览一下蒟蒻写的前两篇题解：
[P1032 子串变换](https://www.luogu.com.cn/article/h31491m5) [P10687 True Liars](https://www.luogu.com.cn/article/6qetz03f)