{"problem":{"name":"[UESTCPC 2024] 一站到底","description":{"content":"假设你是电子科技大学的学生李华，在 4202 年的某一期一站到底中，你作为选手参加了节目的录制。不同于 2000 多年前的规则，节目中不会进行选手两两对战并抢答或轮答题目的环节，每位选手的答题以单人赛的方式进行，具体规则如下： 在选手的答题环节开始前，系统会从题库中抽取 $n$ 道题，每道题根据难度系数有 $a_i$ 的分值。主持人会在一开始公布所有的题目内容和分值，之后进入选手的答题环节。 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10332"},"statements":[{"statement_type":"Markdown","content":"假设你是电子科技大学的学生李华，在 4202 年的某一期一站到底中，你作为选手参加了节目的录制。不同于 2000 多年前的规则，节目中不会进行选手两两对战并抢答或轮答题目的环节，每位选手的答题以单人赛的方式进行，具体规则如下：\n\n在选手的答题环节开始前，系统会从题库中抽取 $n$ 道题，每道题根据难度系数有 $a_i$ 的分值。主持人会在一开始公布所有的题目内容和分值，之后进入选手的答题环节。\n\n为了增加节目的趣味性，在答题环节中，选手并不能随意选择作答题目的顺序。具体的，除 $1$ 号题目外所有题目**有且仅有**一道前置题目，在选手正确作答出某道题的前置题目后才可以进行作答这道题。节目组保证编号为 $i$ 的题目的前置题目编号必然小于 $i$。\n\n此外，如果选手作答题目时提交了错误答案，那么其脚下的地板将立刻打开，选手掉落并结束作答，此前答对的所有题目的分值之和就是该选手的得分。如果选手答对了所有的题目，那么所有题目的分值之和就是该选手的得分。\n\n现在你已经看完了所有的题目，根据你的知识储备，你判断出了每道题你做对的概率 $p_i$。你需要在最短时间内制定出最优的做题策略去最大化你的期望得分，请输出这个得分，~~并以参加这次节目的过程为主题写一篇不少于 120 词的英语作文~~。\n\n## Input\n\n第一行一个正整数 $n$ $(2\\le n\\le 10^5)$，代表题目的数量。\n\n接下来一行 $n$ 个正整数 $a_1,a_2,\\ldots,a_n$ $(1\\leq a_i\\leq 10^6)$，$a_i$ 代表编号为 $i$ 的题目的分值。\n\n接下来一行 $n$ 个实数 $p_1,p_2,\\ldots,p_n$ $(0<p_i<1)$，$p_i$ 代表你答对编号为 $i$ 的题目的概率。\n\n接下来一行 $n-1$ 个正整数 $t_1,t_2,\\ldots,t_{n-1}$ $(1\\leq t_i\\leq i)$，$t_i$ 代表编号为 $i+1$ 的题目的前置题目的编号。\n\n## Output\n\n输出一行一个实数，代表在最优做题策略下的期望得分。\n\n假设你的输出是 $a$，答案是 $b$，当且仅当 $\\frac{|a-b|}{\\max(1,b)}\\le 10^{-9}$ 时，你的答案会被认为是正确的。\n\n[samples]\n\n## Note\n\n在样例中，分值越高的题目你也有越大的概率答对，显然按照 $1,2,3,4,5$ 的顺序去答题最优。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10332","tags":["2024","Special Judge","O2优化","高校校赛"],"sample_group":[["5\n5 4 3 2 1\n0.9 0.89 0.88 0.87 0.86\n1 1 2 2","11.572522416"]],"created_at":"2026-03-03 11:09:25"}}