P5298 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)\)，求：

你需要输出答案对 \(998244353\) 取模的值。

\(n\le 3\times 10^5\)。

这个式子实在太奇怪了，考虑直接求每一种的概率而不是变形式子。
首先对权值离散化一下。

记 \(f_x[i]\) 表示 \(x\) 取值为 \(i\) 的概率。

1. 若 \(x\) 是叶子，\(f_x[a[i]]=1\)，其余 \(0\)。

2. 若 \(x\) 仅有一个儿子，直接继承那个儿子的答案。

3. 若 \(x\) 有两个儿子，记为 \(c_1,c_2\)。对于 \(f_x[i]\)：

   1. \(i\) 在 \(c_1\) 子树内，概率：
   \[f_{c_1}[i]\cdot (p_x\sum_{j=1}^{i-1}f_{c_2}[j]+(1-p_x)\sum_{j=i+1}^{m}f_{c_2}[j]) \]
   2. \(i\) 在 \(c_2\) 子树内，概率：
   \[f_{c_2}[i]\cdot (p_x\sum_{j=1}^{i-1}f_{c_1}[j]+(1-p_x)\sum_{j=i+1}^{m}f_{c_1}[j]) \]

转移方程写出来了，如何优化两个儿子的转移？

发现这是可以用线段树合并优化的。
具体而言，当位于结点 \(u\) 合并完时，让第 \(i\) 个叶子结点保存 \(f_u[i]\)。

如何合并两个儿子的线段树得到 \(u\) 的？设当前合并到两棵线段树的根位于 \(L,R\)，当前对应的区间是 \([lx,rx]\)。

1. 若 \(L,R\) 均非 \(0\)，递归进入 \(L,R\) 的左儿子和右儿子合并，然后 pushup。

2. 若 \(L\neq 0,R=0\)，相当于 \(f_{c_1}[lx\sim rx]=0\)，所以第一条转移方程没用了（\(f_{c_1}[i]=0\)），而对于第二条转移方程，我们需要知道对每个 \(i\in [lx,rx]\) 都知道 \(p_x\sum_{j=1}^{i-1}f_{c_1}[j]+(1-p_x)\sum_{j=i+1}^{m}f_{c_1}[j]\)。

   因为 \(f_{c_1}[lx\sim rx]=0\)，且 \(i\in [lx,rx]\) 所以这个东西等于 \(p_x\sum_{j=1}^{lx-1}f_{c_1}[j]+(1-p_x)\sum_{j=rx+1}^{m}f_{c_1}[j]\)。我们惊奇地发现这个东西对所有 \(i\in [lx,rx]\) 是相等的，而且可以在线段树合并下传参数时维护：额外记录两个参数 \(L1,R1\)，\(L1=\sum_{j=1}^{lx-1}f_{c_1}[j]\)，\(R1=\sum_{j=rx+1}^{m}f_{c_1}\)。

3. 若 \(L=0,R\neq 0\)，是对称的，记录参数 \(L2,R2\) 即可。

总复杂度 \(O(n\log n)\)。