P5298 [PKUWC2018] Minimax

题目描述

小 $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$ 是个正整数。

输出答案。

1
2
3

3
0 1 1
5000 1 2

1	`748683266`

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

对于所有数据，满足 $0 < p_{i} \cdot 10000 < 10000$ ，所以易证明所有叶子的权值都有概率被根取到。

我们设 $f (i, j)$ 为 $i$ 节点出现 $j$ 的概率。

设 $l_{i}, r_{i}$ 是节点 $i$ 的两个子节点， $m$ 为叶子结点的个数。

显然， $i$ 出现 $j$ 的概率为

f (i, j) = f (l, j) (p_{i} \sum_{k = 1}^{j - 1} f (r, k) + (1 - p_{i}) \sum_{k = j + 1}^{m} f (r, k)) + f (r, j) (p_{i} \sum_{k = 1}^{j - 1} f (l, k) + (1 - p_{i}) \sum_{k = j + 1}^{m} f (l, k))

这个式子有关前缀和和后缀和，可以很容易用线段树合并的操作来进行转移。