P5298 [PKUWC2018] Minimax

Little C has a rooted tree with $n$ nodes. The root is node $1$, and each node has at most two children. Define the value of a node $x$ as follows: 1. If $x$ has no children, then its value is given in the input. It is **guaranteed that all such nodes have pairwise distinct values**. 2. If $x$ has children, then its value equals the maximum of its children’s values with probability $p_x$, and equals the minimum of its children’s values with probability $1-p_x$. Now Little C wants to know the following. Suppose the value of node $1$ has $m$ possible outcomes. Let the value of the $i$-th smallest outcome be $V_i$, and its probability be $D_i$ $(D_i>0)$. Compute: $$\sum_{i=1}^{m}i\cdot V_i\cdot D_i^2$$ You need to output the answer modulo $998244353$.

The first line contains a positive integer $n$. The second line contains $n$ integers. The $i$-th integer is the index of the parent of node $i$. The parent of node $1$ is $0$. The third line contains $n$ integers. If node $i$ has no children, then the $i$-th number is its value; otherwise, the $i$-th number is $p_i\cdot 10000$. It is guaranteed that $p_i\cdot 10000$ is a positive integer.

Output the answer.

#### Sample Explanation The value of node $1$ is $1$ with probability $\frac{1}{2}$, and $2$ with probability $\frac{1}{2}$, so the answer is $\frac{5}{4}$. #### Constraints - For $10\%$ of the testdata, $1\leq n\leq 20$. - For $20\%$ of the testdata, $1\leq n\leq 400$. - For $40\%$ of the testdata, $1\leq n\leq 5000$. - For $60\%$ of the testdata, $1\leq n\leq 10^5$. - Another $10\%$ of the testdata guarantees that the shape of the tree is random. - For $100\%$ of the testdata, $1\leq n\leq 3\times 10^5$, $1\leq w_i\leq 10^9$. For all testdata, $0 < p_i \cdot 10000 < 10000$, so it is easy to prove that every leaf value has a positive probability of being chosen by the root. Translated by ChatGPT 5