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

import sys

sys.setrecursionlimit(1 << 25)
# for line in sys.stdin:
#     a = line.split()
#     print(int(a[0]) + int(a[1]))

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(n, values, parents):
    nodes = [None] * (n + 1)  # 节点编号从1到n
    for i in range(1, n+1):
        nodes[i] = TreeNode(values[i-1])
    
    root = None
    for i in range(1, n+1):
        parent = parents[i-1]
        if parent == 0:
            root = nodes[i]
            continue
        parent_node = nodes[parent]
        if parent_node.left is None:
            parent_node.left = nodes[i]
        else:
            parent_node.right = nodes[i]
    return root

class Solution:
    def maxPathSum(self, root):
        self.max_sum = float('-inf')
        def dfs(node):
            if not node:
                return 0
            left_gain = max(dfs(node.left), 0)
            right_gain = max(dfs(node.right), 0)
            current_sum = node.val + left_gain + right_gain
            self.max_sum = max(self.max_sum, current_sum)
            return node.val + max(left_gain, right_gain)
        dfs(root)
        return self.max_sum

# 读取输入并执行
n = int(input())
values = list(map(int, input().split()))
parents = list(map(int, input().split()))
root = build_tree(n, values, parents)
solution = Solution()
print(solution.maxPathSum(root))