#2537. 「PKUWC2018」Minimax

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

C 有一棵 n 个结点的有根树,根是 1 号结点,且每个结点最多有两个子结点。

定义结点 x 的权值为:

1.若 x 没有子结点,那么它的权值会在输入里给出,保证这类点中每个结点的权值互不相同

2.若 x 有子结点,那么它的权值有 p_x 的概率是它的子结点的权值的最大值,有 1-p_x 的概率是它的子结点的权值的最小值。

现在小 C 想知道,假设 1 号结点的权值有 m 种可能性,权值第 i 的可能性的权值是 V_i ,它的概率为 D_i(D_i>0) ,求:

\sum_{i=1}^{m}i\cdot V_i\cdot D_i^2

你需要输出答案对 998244353 取模的值。

输入格式

第一行一个正整数 n
第二行 n 个整数,第 i 个整数表示第 i 个结点的父亲的编号,其中第 1 个结点的父亲为 0
第三行 n 个整数,若第 i 个结点没有子结点,则第 i 个数为它的权值,否则第 i 个数为 p_i\cdot 10000 ,保证 p_i\cdot 10000 是个正整数。

输出格式

输出答案。

样例

输入样例

3
0 1 1
5000 1 2

输出样例

748683266

样例解释

1号结点的权值有 \frac{1}{2} 的概率是 1 ,有 \frac{1}{2} 的概率是 2 ,所以答案是 \frac{5}{4}

数据范围与提示

对于 10\% 的数据,有 1\leq n\leq 20
对于 20\% 的数据,有 1\leq n\leq 400
对于 40\% 的数据,有 1\leq n\leq 5000
对于 60\% 的数据,有 1\leq n\leq 10^5
另有 10\% 的数据保证树的形态随机。
对于 100\% 的数据,有 1\leq n\leq 3\times 10^5 1\leq w_i\leq 10^9

对于所有数据,满足 0 < p_i \cdot 10000 < 10000 ,所以易证明所有叶子的权值都有概率被根取到。