解题思路

给定父数组描述的二叉树，我们要找一条“任意点出发、沿父↔子边走、节点不重复”的路径，使得节点权值之和最大。这是经典的“二叉树最大路径和”问题，可用一次后序遍历的树形动态规划解决。

相关算法：树形 DP + 一次后序遍历（Postorder）

对每个节点 $u$，维护两个量：

1. down[u]：从 $u$ 出发、向下走到某个子孙的单臂最佳路径和（允许不选子树，等价于与 0 取较大）。
2. ans：全局最大路径和，考虑“穿过 $u$”的两臂方案：

题目内容

二又树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。

注意：

1.同一个节点在一条二叉树路径里中最多出现一次

2.一条路径至少包含一个节点，且不一定经过根节点

给定一个二叉树，请你计算它的最大路径和例如：

给出以下的二叉树：

最优路径是：$2=>1=>3$，或者 $3=>1=>2$，最大路径和 $=2+1+3=6$

数据范围：节点数满足 $0≤n≤10^5$ ，节点上的值满足 $|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