题目大意

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

思路

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

代码如下

cpp

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005

int n;            // 关卡数量
int f[N];         // 每个关卡的前置关卡编号数组
int a[N], b[N];   // 每个关卡的解密值数组 a 和操作值数组 b
vector<int> g[N]; // 邻接表存储树结构，g[u]表示 u 节点的子节点

// 深度优先搜索函数，计算以节点 u 为根的子树的最大趣味程度和
int dfs(int u) {
    int res = 0; // 初始化当前节点的趣味程度和
    for(int v : g[u]) {
        res += dfs(v); // 递归计算子节点的趣味程度和，并累加
    }
    // 返回该节点的趣味程度和，取决于累加值与趣味程度之和是否大于 0
    return max(0ll, res + a[u] + b[u]);
}

signed main() {
    cin >> n; // 读取关卡数量

    // 读取前置关卡信息，并构建树结构
    for(int i = 2; i <= n; i++) {
        cin >> f[i];            // 读取第 i 个关卡的前置关卡编号
        g[f[i]].push_back(i);   // 将当前关卡添加到前置关卡的子节点列表中
    }

    // 读取每个关卡的解密值 a_i
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 读取每个关卡的操作值 b_i
    for(int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    // 从根节点 1 开始进行深度优先搜索，计算并输出最大趣味程度和
    cout << dfs(1);
    return 0;
}

python

import sys
from collections import defaultdict

# 增加递归深度限制，适应较大的输入规模
sys.setrecursionlimit(100000)

# 定义全局变量
N = 100005
a = [0] * N        # 解密值数组
b = [0] * N        # 操作值数组
g = defaultdict(list)  # 用于存储树结构，使用 defaultdict 可以避免手动初始化每个节点的子节点列表

# 深度优先搜索函数，计算以节点 u 为根的子树的最大趣味程度和
def dfs(u):
    res = 0  # 初始化当前节点的趣味程度和
    for v in g[u]:
        res += dfs(v)  # 递归计算子节点的趣味程度和，并累加
    # 返回该节点的趣味程度和，取决于累加值与趣味程度之和是否大于 0
    return max(0, res + a[u] + b[u])

# 主函数
if __name__ == '__main__':
    # 读取输入
    n = int(input().strip())  # 读取关卡数量
    
    # 读取前置关卡信息并构建树结构
    f = list(map(int, input().strip().split()))
    for i in range(2, n + 1):
        g[f[i - 2]].append(i)  # 将当前关卡 i 添加到前置关卡的子节点列表中

    # 读取每个关卡的解密值 a_i 和操作值 b_i
    a_values = list(map(int, input().strip().split()))
    b_values = list(map(int, input().strip().split()))
    
    # 将输入的解密值和操作值赋值到对应的数组中
    for i in range(1, n + 1):
        a[i] = a_values[i - 1]
        b[i] = b_values[i - 1]

    # 从根节点 1 开始进行深度优先搜索，计算并输出最大趣味程度和
    print(dfs(1))

java

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N = 100005;
    static long[] a = new long[N];         // 解密值数组
    static long[] b = new long[N];         // 操作值数组
    static ArrayList<Integer>[] g = new ArrayList[N]; // 邻接表存储树结构

    // 深度优先搜索函数，计算以节点 u 为根的子树的最大趣味程度和
    static long dfs(int u) {
        long res = 0; // 初始化当前节点的趣味程度和
        for (int v : g[u]) {
            res += dfs(v); // 递归计算子节点的趣味程度和，并累加
        }
        // 返回该节点的趣味程度和，取决于累加值与趣味程度之和是否大于 0
        return Math.max(0, res + a[u] + b[u]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 读取关卡数量

        // 初始化邻接表
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }

        // 读取前置关卡信息并构建树结构
        for (int i = 2; i <= n; i++) {
            int f = sc.nextInt(); // 读取前置关卡编号
            g[f].add(i); // 将当前关卡添加到前置关卡的子节点列表中
        }

        // 读取每个关卡的解密值 a_i
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextLong();
        }

        // 读取每个关卡的操作值 b_i
        for (int i = 1; i <= n; i++) {
            b[i] = sc.nextLong();
        }

        // 从根节点 1 开始进行深度优先搜索，计算并输出最大趣味程度和
        System.out.println(dfs(1));
        sc.close();
    }
}

题目内容

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

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

米小游想知道她通过若干个关卡可以获得的趣味程度之和的最大值是多少。

输入描述

第一行输入一个整数$n$($1 ≤ n ≤ 10^5$)，表示关卡数量。

第二行输入$n-1$个整数 $f_i$($1 ≤ f_i ≤ i$)，表示第 $i$个关卡的前置关卡。

第三行输入$n$个整数 $a_i$($-10^9 ≤ a_i ≤ 10^9$)，表示第$i$个关卡的解密值。

第四行输入$n$个整数$b_i$($-10^9 ≤ b_i ≤ 10^9$)，表示第 $i$个关卡的操作值。

输出描述

输出一个整数，表示答案，即通过若干个关卡可以获得的趣味程度之和的最大值。

样例1

输入

5
1 1 2 2
1 -2 3 -4 5
-1 2 -3 4 -5

输出

0