You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

无主之地有 $n$ 个褪色者，除了艾尔登之王 1 没有导师，其余每位褪色者都有一位导师。这样的师徒关系构成以 1 为根的有根树。定义一个褪色者的直接徒弟，指以他为导师的所有徒弟。一个褪色者的徒弟，指他子树内除他以外的所有褪色者。

有些褪色者渴望得到战力提升，不过佛系的褪色者可能就不这么想。记 $s[u]$ 为褪色者 $u$ 是否希望提升战力，“是”为 1，“否”为 0。因为每个褪色者都把想法暗藏于心，所以序列 $s[1 \ldots n]$ 是未知的。

艾尔登之王在黄金树下吹响了集合的号角，不过并不是所有褪色者都必须响应号召，他们是否前往黄金树会以自己的直接徒弟们的参加情况为参考。每个褪色者 $u$ 都会等待自己所有徒弟都决定完，然后：

• 若不存在直接徒弟决定前往黄金树，则 $u$ 以 $p[u]$ 的概率前往
• 否则，$u$ 一定不会前往黄金树。

注意在这样的规则下，有可能艾尔登之王自己都不去黄金树，序列 $p[1 \ldots n]$ 是已知的。

每位褪色者都有权力和义务给自己的徒弟提升战力。每位前往黄金树的褪色者 $u$ 会对每个要求提升战力并且到达黄金树的徒弟 $v$ 提升战力 $a[u]$。这个值当然可以是负的，因为有些褪色者心怀鬼胎。序列 $a[1 \ldots n]$ 是已知的。

求使所有褪色者增加战力之和期望最大的序列 $s[1 \ldots n]$。不用输出序列 $s$，只用输出期望的大小。保证答案在 $10^{11}$ 以内。

输入格式

第一行一个整数 $n$ 表示褪色者数目。

第二行 $n-1$ 个整数 $f a[u]$，表示褪色者 $2-n$ 的导师。导师编号一定小于自己的编号。

第三行 $n$ 个小数 $p[u]$，表示每位褪色者前往黄金树的概率，$0 < p[u] < 1$。

第四行 $n$ 个整数 $a[u]$，表示每位褪色者对于自己每个有战力提升要求的徒弟的战力提升幅度。

输出格式

一行 1 个小数 ans 表示答案，输出到小数点后第 6 位。

5
1 1 3 3
0.20 0.60 0.60 0.40 0.40
3 2 0 4 -3

0.192000

10
1 2 1 4 2 4 7 4 4
0.60 0.80 0.10 0.20 0.60 0.40 0.80 0.30 0.70 0.70
0 10 8 4 -5 4 8 4 -5 9

0.008640

附加样例

b.in
b.out

数据范围与提示

• 对于测试点 1，$n \leq 20$
• 对于测试点 2-4，$n \leq 10^3$
• 对于测试点 5，$n \leq 10^5$，树是以 1 为根的完全二叉树
• 对于测试点 6-7，$n \leq 10^5$
• 对于测试点 8-10，$n \leq 5 \times 10^5$

对于 $100 \%$ 的数据，$1 \leq n \leq 5 \times 10^5, 0 \lt p[u] \lt 1,\lvert a[u]\rvert \leq 10^4$，保证答案 $0\leq ans \leq 10^{11}$。