题解 | 二叉树中的最大路径和

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

const int N = 100010;
vector<int> children[N];
int values[N];
int ans;

int dfs(int u) {
    if(children[u].empty()) {  // 叶子节点
        ans = max(ans, values[u-1]);
        return values[u-1];
    }
    
    // 获取左右子节点的最大路径和
    int max_child = INT_MIN;
    int sum_child = values[u-1];  // 当前节点值
    
    for(int child : children[u]) {
        int child_sum = dfs(child);
        // 更新从当前节点出发的最大路径
        max_child = max(max_child, child_sum);
        // 尝试将子路径加入总路径（如果为正）
        if(child_sum > 0) {
            sum_child += child_sum;
        }
    }
    
    // 更新全局最大路径和
    ans = max(ans, sum_child);
    
    // 返回从当前节点出发的最大路径和（只能选择一个子树）
    return max(values[u-1], values[u-1] + max_child);
}

int main() {
    int n;
    cin >> n;
    
    // 读入节点值
    for(int i = 0; i < n; i++) {
        cin >> values[i];
    }
    
    // 读入父节点关系并构建子节点表
    for(int i = 0; i < n; i++) {
        int p;
        cin >> p;
        if(p > 0) {  // 非根节点
            children[p].push_back(i+1);
        }
    }
    
    ans = INT_MIN;
    dfs(1);  // 从根节点开始DFS
    
    cout << ans << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static int N = 100010;
    static ArrayList<Integer>[] children;
    static int[] values;
    static int ans;
    
    static int dfs(int u) {
        if(children[u].isEmpty()) {  // 叶子节点
            ans = Math.max(ans, values[u-1]);
            return values[u-1];
        }
        
        // 获取左右子节点的最大路径和
        int maxChild = Integer.MIN_VALUE;
        int sumChild = values[u-1];  // 当前节点值
        
        for(int child : children[u]) {
            int childSum = dfs(child);
            // 更新从当前节点出发的最大路径
            maxChild = Math.max(maxChild, childSum);
            // 尝试将子路径加入总路径（如果为正）
            if(childSum > 0) {
                sumChild += childSum;
            }
        }
        
        // 更新全局最大路径和
        ans = Math.max(ans, sumChild);
        
        // 返回从当前节点出发的最大路径和（只能选择一个子树）
        return Math.max(values[u-1], values[u-1] + maxChild);
    }
    
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 初始化
        values = new int[n];
        children = new ArrayList[N];
        for(int i = 0; i < N; i++) {
            children[i] = new ArrayList<>();
        }
        
        // 读入节点值
        for(int i = 0; i < n; i++) {
            values[i] = sc.nextInt();
        }
        
        // 读入父节点关系并构建子节点表
        for(int i = 0; i < n; i++) {
            int p = sc.nextInt();
            if(p > 0) {  // 非根节点
                children[p].add(i+1);
            }
        }
        
        ans = Integer.MIN_VALUE;
        dfs(1);  // 从根节点开始DFS
        
        System.out.println(ans);
        
        sc.close();
    }
}

import sys
sys.setrecursionlimit(100010)  # 扩大递归栈深度

def dfs(u, values, children, ans):
    """
    返回从节点u出发的最大路径和
    同时更新全局最大路径和ans[0]
    """
    if not children[u]:  # 叶子节点
        ans[0] = max(ans[0], values[u-1])
        return values[u-1]
    
    # 获取左右子节点的最大路径和
    max_child = float('-inf')
    sum_child = values[u-1]  # 当前节点值
    
    for child in children[u]:
        child_sum = dfs(child, values, children, ans)
        # 更新从当前节点出发的最大路径
        max_child = max(max_child, child_sum)
        # 尝试将子路径加入总路径（如果为正）
        if child_sum > 0:
            sum_child += child_sum
    
    # 更新全局最大路径和
    ans[0] = max(ans[0], sum_child)
    
    # 返回从当前节点出发的最大路径和（只能选择一个子树）
    return max(values[u-1], values[u-1] + max_child)

def main():
    # 输入
    n = int(input())
    values = list(map(int, input().split()))
    parents = list(map(int, input().split()))
    
    # 构建子节点表
    children = [[] for _ in range(n+1)]
    root = 1
    for i in range(n):
        if parents[i] > 0:  # 非根节点
            children[parents[i]].append(i+1)
    
    # 计算最大路径和
    ans = [float('-inf')]  # 使用列表存储全局最大值
    dfs(root, values, children, ans)
    
    print(ans[0])

if __name__ == "__main__":
    main()