解题思路
给定父数组描述的二叉树，我们要找一条“任意点出发、沿父↔子边走、节点不重复”的路径，使得节点权值之和最大。这是经典的“二叉树最大路径和”问题，可用一次后序遍历的树形动态规划解决。
相关算法：树形 DP + 一次后序遍历（Postorder）
对每个节点 u，维护两个量：
down[u]：从 u 出发、向下走到某个子孙的单臂最佳路径和（允许不选子树，等价于与 0 取较大）。
P3855.第3题-二叉树路径
题目内容
二又树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。
注意：
1.同一个节点在一条二叉树路径里中最多出现一次
2.一条路径至少包含一个节点，且不一定经过根节点
给定一个二叉树，请你计算它的最大路径和例如：
给出以下的二叉树：
最优路径是：2=>1=>3，或者 3=>1=>2，最大路径和 =2+1+3=6
数据范围：节点数满足 0≤n≤105 ，节点上的值满足 ∣val≤1000
要求：空间复杂度 O(1) ，时间复杂度 O(n)
输入描述
第一行输入一个正整数 n 表示二叉树的节点数
第二行输入 n 个整数表示二叉树上第 i 个节点的值
第三行输入 n 个整数表示二叉树上第 i 个节点的父节点是第几个节点，(其中第一个节点是根节点，其父节点表示为第零个节点 0 )。
输出描述
输出最大路径和
样例1
输入
3
1 2 3
0 1 1
输出
6
样例2
输入
5
-20 8 20 15 6
0 1 1 3 3
输出
41
