ZOJ Problem Set - 3937
Recently, Bright Luna is playing a massively multiplayer online role-playing game (MMORPG) called Legendary Age. Designers of this game prepared many mini-games during daily operations. Players can ignore these games without any loss. If you spend some time in them, you can always obtain some bonuses. This is one of the fascinating features of Legendary Age.
One day, Bright Luna had a fight with other players. After that he came back to the city to recover his Health Points (HP). Surprisingly, the NPC gave him a special choice. The NPC can teleport Bright Luna to a colorful fantasy world with N dungeons. These dungeons are identified from 1 through N. Each dungeon has exactly a one-way exit leading to another dungeon which has a smaller identifier except for the dungeon 1, which has no exit.
There is a buff or debuff in each dungeon which can be described by an integer Bi. Bright Luna will get the i-th buff/debuff when he enters the i-th dungeon. When he leaves a dungeon or leaves the world, the buffs/debuffs he has obtained will change his HP by Bi. For example, If he already visited the dungeons 6 -> 4 -> 3, when he leaves the dungeon 3, his HP will be changed by (B6 + B4 + B3). The buffs/debuffs will not expire until he completes the adventure.
The NPC had shown the world map to Bright Luna. Bright Luna can choose the dungeon he enters at the beginning and he can leave the world at any dungeon. Of course, he can refuse to take this adventure. Can you help Bright Luna to gain as many health points as possible?
There are multiple test cases. The first line of input is an integer T indicating the number of test cases. For each test case:
The first line contains an integer N (1 ≤ N ≤ 105).
The second line contains N integers Bi (|Bi| ≤ 108).
The third line contains N - 1 integers Fi (2 ≤ i ≤ N, Fi < i) indicating the dungeons which the exit of dungeon i lead to.
For each case, please output the maximum health points Bright Luna can gain.
4 4 1 4 3 2 1 1 1 4 1 2 -3 4 1 2 3 4 -4 2 -3 4 1 2 3 3 -1 -2 -3 1 1
9 12 8 0
In the first example, we can start from dungeon 2 and end at dungeon 1.
In the second example, we can start from dungeon 4 and end at dungeon 1.
In the third example, we can start from dungeon 4 and end at dungeon 2.
Author: ZHAO, Yueqi
Source: The 13th Zhejiang Provincial Collegiate Programming Contest