题目描述

小 E 有 $n$ 个 AI 构成树形结构（编号 $1 \sim n$，第 $i$ 个 AI 的父节点 $c_i < i$），每个 AI 初始存有一道难度为 $d_i$ 的最大权独立集问题。通过以下操作整合问题，最终需将 $n-1$ 个 AI 的难度变为 $0$，保留最后一个 AI 的难度，目标是使该最终难度最大化：

1. 选择一个存有问题（难度非 $0$）的 AI $u$；
2. 整合规则：新难度 =（$u$ 所有直接通信 AI 中的问题难度和）-（$u$ 原本的问题难度）；
3. 结果：$u$ 的直接通信 AI 难度变为 $0$，$u$ 的难度更新为上述新难度。

输入格式

1. 第一行：一个正整数 $n$（AI 数量）；
2. 第二行：$n$ 个整数 $d_1, d_2, \dots, d_n$（每个 AI 初始问题难度）；
3. 第三行：$n-1$ 个正整数 $c_2, c_3, \dots, c_n$（第 $i$ 个 AI 的父节点，$c_i < i$）。

输出格式

输出一行一个整数，表示最终可获得的最大问题难度。

样例

样例 1

输入

4
-1 2 3 4
1 1 1

输出

10

样例解释

AI 构成以 $1$ 为根的星形树（$2、3、4$ 的父节点均为 $1$），最优整合路径如下：

1. 选择 AI $2$：其直接通信 AI 仅 $1$（难度 $-1$），新难度 = $-1 - 2 = -3$；此时 $1$ 的难度变为 $0$，$2$ 的难度变为 $-3$。
2. 选择 AI $3$：其直接通信 AI 仅 $1$（难度 $0$），新难度 = $0 - 3 = -3$；此时 $1$ 的难度保持 $0$，$3$ 的难度变为 $-3$。
3. 选择 AI $4$：其直接通信 AI 为 $1（0）、2（-3）、3（-3）$，新难度 = $(0 + (-3) + (-3)) - 4 = -10$？（实际最优路径需调整选择顺序，最终通过树形 DP 计算得最大难度 $10$）。

数据范围与提示

• 核心约束：$1 \le n \le 351493$，$|d_i| \le 10^9$，$1 \le c_i < i$（树形结构）。
• 子任务划分： | 子任务 | 分值 | 附加限制 | | ---- | ---- | ---- | | 1 | 13 | $c_i = i-1$（链状结构） | | 2 | 6 | $d_i > 0$（所有初始难度为正） | | 3 | 11 | $n \le 7$ | | 4 | 13 | $n \le 16$ | | 5 | 22 | $n \le 100$ | | 6 | 35 | 无特殊性质 |