8953: DP55 二叉树中的最大路径和
[Creator : ]
Description
二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。
注意:
1.同一个节点在一条二叉树路径里中最多出现一次
2.一条路径至少包含一个节点，且不一定经过根节点
给定一个二叉树，请你计算它的最大路径和
例如：给出以下的二叉树，
最优路径是 2=>1=>3，或者 3=>1=>2，最大路径和 2+1+3=6
Input
第一行输入一个正整数 n 表示二叉树的节点数
第二行输入 n 个整数表示二叉树上第 i 个节点的值
第三行输入 n 个整数表示二叉树上第 i 个节点的父节点是第几个节点，（其中第一个节点是根节点，其父节点表示为第零个节点0）。
Output
输出最大路径和
Constraints
$0 \leq n \leq 10^5$
$-1,000 \leq val \leq 1,000$
$-1,000 \leq val \leq 1,000$
Sample 1 Input
3
1 2 3
0 1 1
Sample 1 Output
6
Sample 2 Input
5
-20 8 20 15 6
0 1 1 3 3
Sample 2 Output
41
其中一条最大路径为 15=>20=>6，路径和为15+20+6=41
Sample 3 Input
2
-2 -3
0 1
Sample 3 Output
-2
HINT
相同问题：牛客网。