走走跳跳

题目描述

有 $n$ 个位置排成一排，第 $i$ 个位置都有一个分数 $a_i$（分数可能是正数，也可能是负数）。小爱从 $1$ 号位置出发，最终要走到 $n$ 号位置。当小爱在第 $i$ 个位置时，有两种选择：

• 她可以直接走到下一个位置（也就是 $i+1$ 号位置）；
• 也可以选择跳到第 $t_i$ 号位置（保证 $i < t_i$）。

小爱的得分就是一路上经过的所有位置的分数之和，请问应该如何安排行动，才能使获得的分数之和达到最大？

输入格式

第一行：一个整数 $n$；

第二行：$n$ 个整数，表示 $a_1, a_2, \cdots, a_n$；

第三行：$n-1$ 个整数，表示 $t_1, t_2, \cdots, t_{n-1}$；

输出格式

单个整数：表示可能拿到的最高分数

数据范围

• 对于 $30\%$ 的数据，保证 $1 \leq n \leq 50$；
• 对于 $60\%$ 的数据，保证 $1 \leq n \leq 5000$；
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 100,000$；
• $-10^7 \leq a_i \leq 10^7$；
• $i < t_i \leq n$；

样例输入 #1

3
4 -2 6
3 3

样例输出 #1

10

样例输入 #2

5
0 -2 3 0 0
4 5 5 5

样例输出 #2

1

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐。

测试点分布