给出一颗大小为n的有树,选择一个包含1节点的联通块或者为空,要求联通块内的点权值和最大
考虑树形dp,从根节点开始,往叶子节点进行递归,为了确保不选择负贡献的子树节点,我们会对每个子树的权值和进行最大化,对于目前的节点,只把儿子节点是正贡献加进来即可 由于是树结构,使用 DFS 进行一次遍历,每个节点仅被访问一次,时间复杂度为 O(n),其中 n 为节点数,能很好地应对题目给定的约束
#include<bits/stdc++.h>
using namespace std;
米小游正在玩《绝区零》。在《绝区零》中有一些关卡,这些关卡形成了一棵以1为根的有根树。具体来说,对于第 i 个关卡,必须通过它的前置关卡 fi,后才能通过第 i个关卡,其中第1个关卡没有前置关卡。
每个关卡都有一个解密值 ai 和一个操作值 bi。一个关卡的趣味程度就是解密值与操作值之和。
米小游想知道她通过若干个关卡可以获得的趣味程度之和的最大值是多少。
第一行输入一个整数n(1≤n≤105),表示关卡数量。
第二行输入n−1个整数 fi(1≤fi≤i),表示第 i个关卡的前置关卡。
第三行输入n个整数 ai(−109≤ai≤109),表示第i个关卡的解密值。
第四行输入n个整数bi(−109≤bi≤109),表示第 i个关卡的操作值。
输出一个整数,表示答案,即通过若干个关卡可以获得的趣味程度之和的最大值。
输入
5
1 1 2 2
1 -2 3 -4 5
-1 2 -3 4 -5
输出
0