F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5461. -- [PKUWC2018]Minimax

5461: [PKUWC2018]Minimax

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 208  Solved: 103
[Submit][Status][Discuss]

Description

小 C 有一棵 n 个结点的有根树,根是 1 号结点,且每个结点最多有两个子结点。
定义结点 x 的权值为:
1.若 x 没有子结点,那么它的权值会在输入里给出,保证这类点中每个结点的权值互不相同。
2.若 x 有子结点,那么它的权值有 px的概率是它的子结点的权值的最大值,有 1?px的概率是它的子结点的权值的最小值。
现在小 C 想知道,假设 1 号结点的权值有 m 种可能性,权值第 i 小的可能性的权值是 Vi,它的概率为 Di,求:
 

Input

输入
第一行一个正整数 n;
第二行 n 个整数,第 i个整数表示第 i 个结点的父亲的编号,其中第 1 个结点的父亲为 0;
第三行 n 个整数,若第 i 个结点没有子结点,则第 i 个数为它的权值,否则第 i 个数为 pi×10000,保证 pi×10000是个正整数。
0<pi<1,1<=N<=3*10^5,1<wi<=10^9

Output

输出答案

Sample Input

3
0 1 1
5000 1 2

Sample Output

748683266

HINT

Source

[Submit][Status][Discuss]

HOME Back