#2537. 「PKUWC2018」Minimax

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

题目描述

CC 有一棵 nn 个结点的有根树,根是 11 号结点,且每个结点最多有两个子结点。

定义结点 xx 的权值为:

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

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

现在小 CC 想知道,假设 11 号结点的权值有 mm 种可能性,权值第 ii的可能性的权值是 ViV_i,它的概率为 Di(Di>0)D_i(D_i>0),求:

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

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

输入格式

第一行一个正整数 nn
第二行 nn 个整数,第 ii 个整数表示第 ii 个结点的父亲的编号,其中第 11 个结点的父亲为 00
第三行 nn 个整数,若第 ii 个结点没有子结点,则第 ii 个数为它的权值,否则第 ii 个数为 pi10000p_i\cdot 10000,保证 pi10000p_i\cdot 10000 是个正整数。

输出格式

输出答案。

样例

输入样例

3
0 1 1
5000 1 2

输出样例

748683266

样例解释

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

数据范围与提示

对于 10%10\% 的数据,有1n201\leq n\leq 20
对于 20%20\% 的数据,有1n4001\leq n\leq 400
对于 40%40\% 的数据,有1n50001\leq n\leq 5000
对于 60%60\% 的数据,有1n1051\leq n\leq 10^5
另有 10%10\% 的数据保证树的形态随机。
对于 100%100\% 的数据,有 1n3×1051\leq n\leq 3\times 10^51wi1091\leq w_i\leq 10^9

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