Maximizing Expected Score in the Sequential Quiz Show

You are a contestant on a futuristic quiz show at the University of Electronic Science and Technology in the year 4202. The show consists of n questions drawn from a question bank. Each question i has a score value a_i reflecting its difficulty and you are given your probability p_i of answering it correctly. The twist is that, except for question 1 which is free to attempt, every other question has exactly one prerequisite question. In order to attempt question i (i ≥ 2), you must have answered its prerequisite question (whose index is less than i) correctly.

If you ever answer a question incorrectly, the floor opens up immediately, ending the game and you will keep the sum of scores from all previously correctly answered questions. If you answer all questions correctly the sum of all a_i is your final score.

Your task is to determine the optimal strategy (i.e. the order in which to attempt the unlocked questions) in order to maximize your expected score. Mathematically, if from a given question u you have a set of available next questions v with effective reward X_v = a_v + F(v) where F(v) is the maximum additional expected score obtainable from question v’s subtree, then attempting a sequence v₁, v₂, …, v_k yields an expected score of:

\[ F(u) = \sum_{i=1}^{k} \Big( \prod_{j=1}^{i} p_{v_j} \Big) \cdot X_{v_i} \]

The optimal ordering among available questions can be determined using the greedy rule: for two questions i and j, attempt i before j if and only if \[ p_i\,X_i\,(1-p_j) \ge p_j\,X_j\,(1-p_i). \]

Finally, the expected total score is given by a₁ + F(1), since question 1 is free to be attempted first. In addition to outputting this expected score, you must also output an English essay (of at least 120 words) describing your experience participating in this show.

inputFormat

The input consists of four lines:

• The first line contains a single integer n (the number of questions).
• The second line contains n space-separated integers representing the scores a₁, a₂, …, a_n.
• The third line contains n space-separated real numbers representing your probabilities p₁, p₂, …, p_n of answering each question correctly.
• The fourth line contains n-1 space-separated integers. The i-th integer (for i from 1 to n-1) represents the index of the prerequisite question for question i+1 (guaranteed to be less than i+1).

outputFormat

Output the maximum expected total score obtained with the optimal strategy followed by a newline and then an English essay (at least 120 words) describing your experience during the show.

sample

3
10 20 30
0.9 0.8 0.7
1 2

42.8
Participating in the quiz show was a life-changing experience that challenged both my intellect and my resolve. The futuristic setting of the show, held in the year 4202, was unlike anything I had ever encountered. I felt a rush of adrenaline as I navigated the complex rules, where each question not only tested my knowledge but also required careful strategy. The prerequisite system forced me to consider every move, balancing risk and reward. As I progressed, my anticipation grew with each correctly answered question, even though the fear of an unexpected mistake loomed. The possibility of the floor opening beneath me added dramatic tension that made every second count. Reflecting on the experience, I can say that the show taught me valuable lessons about decision-making under pressure and the importance of calculated risks. It remains one of the most memorable events of my academic career.