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

n = int(input())

import sys
sys.setrecursionlimit(100000)

value = list(map(int , input().split(' ')))

if len(value)==1:
    print(value[0])
    sys.exit()

father = list(map(int , input().split(' ')))

map  = [ [] for i in range(n+1)]

for i in range(n):
    if father[i]!=0:
        #map[i+1].append(father[i])
        map[father[i]].append(i+1)
value.insert(0,0)
dp = value[:]





def dfs(root):
    if father[root-1]:
        dp[root] = max(dp[root],dp[father[root-1]]+value[root])
    if len(map[father[root-1]])==2:
        dp[root] = max(dp[root],value[father[root-1]]+value[map[father[root-1]][0]]+value[map[father[root-1]][1]])
    for son in map[root]:
        dfs(son)
    
dfs(1)


print(max(dp))

因为一个节点最多连接两个其他的节点，没运行到一个节点判断为

dp[root] = max(dp[root],dp[root]+dp[father],value(father)+value(father's left son)+value(father's right son))