EagleBear2002 的博客

这里必须根绝一切犹豫,这里任何怯懦都无济于事

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

输入 #1

1
2
3
3
0 1 1
5000 1 2

输出 #1

1
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$,所以易证明所有叶子的权值都有概率被根取到。

题解

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

设 $l_i, r_i$ 是节点 $i$ 的两个子节点, $m$ 为叶子结点的个数。

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

$$ f(i,j) = f(l,j) \left( p_i \sum_{k=1}^{j-1} f(r,k) + (1-p_i) \sum_{k=j+1}^{m} f(r,k) \right) + f(r,j) \left( p_i \sum_{k=1}^{j-1} f(l,k) + (1-p_i) \sum_{k=j+1}^{m} f(l,k) \right) $$

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