[AdditionalFile2537.zip](file://AdditionalFile2537.zip?type=additional_file)

#2537. 「PKUWC2018」Minimax

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

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

定义结点 $x$ 的权值为：

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

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

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

你需要输出答案对 $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$，所以易证明所有叶子的权值都有概率被根取到。