题目内容

米小游正在玩《绝区零》。在《绝区零》中有一些关卡，这些关卡形成了一棵以$1$为根的有根树。具体来说，对于第 $i$ 个关卡，必须通过它的前置关卡 $f_i$，后才能通过第 $i$个关卡，其中第$1$个关卡没有前置关卡。

每个关卡都有一个解密值 $a_i$ 和一个操作值 $b_i$。一个关卡的趣味程度就是解密值与操作值之和。

题目大意

给出一颗大小为n的有树，选择一个包含1节点的联通块或者为空，要求联通块内的点权值和最大

思路

考虑树形dp,从根节点开始，往叶子节点进行递归，为了确保不选择负贡献的子树节点，我们会对每个子树的权值和进行最大化,对于目前的节点，只把儿子节点是正贡献加进来即可$\\$ 由于是树结构，使用 DFS 进行一次遍历，每个节点仅被访问一次，时间复杂度为 O(n)，其中 n 为节点数，能很好地应对题目给定的约束

代码如下

cpp

#include<bits/stdc++.h>
using namespace std;