题意整理

• 有根树（根 1），每个节点最多两个子节点（二叉树）。
• 叶节点：权值给定，互不相同。
• 非叶节点 (x)：有子节点，权值以概率 (p_x) 取子节点权值的 最大值，以概率 (1-p_x) 取 最小值。
• 根节点的权值是一个随机变量，有 (m) 种可能取值，第 (i) 小的是 (V_i)，概率为 (D_i)（(D_i > 0)）。
• 求： [ \sum_{i=1}^m i \cdot V_i \cdot D_i^2 \mod 998244353 ]

注意：(m) 是根节点可能取值的种数，不是给定的，需要从树结构推出来。

---

第一步：分析根节点权值的分布

从叶节点权值（给定、互异）出发，每个非叶节点是子节点权值的随机函数（以概率 (p) 取 max，否则取 min），因此根节点的权值就是一些叶节点权值的随机函数。

由于叶节点权值互不相同，且运算只有 min/max，所以根节点可能的取值一定是某些叶节点的权值（不会出现新值）。

因此 (m) 不超过叶节点数，且每个可能值是某个叶节点的权值。

---

第二步：概率与排序权重的计算

设根节点权值的可能值为 (V_1 < V_2 < \dots < V_m)，对应概率 (D_1, \dots, D_m)。

我们要求的是： [ S = \sum_{i=1}^m i \cdot V_i \cdot D_i^2 ]

这与权值排序后的加权和有关，但权重是 (i \cdot D_i^2)。

如果我们知道根节点权值的分布函数（即概率质量函数），我们可以排序后计算。

---

第三步：树形 DP 状态设计

因为权值很大（1e9），但种类不多（≤ 叶节点数），我们可以考虑对权值离散化（按叶节点权值排序），然后 DP 计算概率。

设所有叶节点权值排序后为 (w_1 < w_2 < \dots < w_L)（(L) 为叶节点数）。

定义：

• (f_u(x)) = 节点 (u) 的权值 ≤ (w_x) 的概率。
• (g_u(x)) = 节点 (u) 的权值 = (w_x) 的概率（离散概率）。

那么对于叶节点 (u)，若其权值是 (w_t)，则 [ g_u(t) = 1, \quad g_u(\text{其他}) = 0 ] [ f_u(x) = [x \ge t] \quad (\text{即 } x < t \text{ 时为 0, } x \ge t \text{ 时为 1}) ]

---

第四步：非叶节点的转移

设节点 (u) 有两个子节点 (l, r)（可能只有一个，先考虑两个）。

权值 ≤ (w_x) 的概率： [ P(\text{val}_u \le w_x) = \begin{cases} \text{以 } p_u \text{ 取 max: 要求两个子节点权值都 } \le w_x \ \text{以 } 1-p_u \text{ 取 min: 要求至少一个子节点权值 } \le w_x \end{cases} ] 更直接：

• 取 max 时：(\max(v_l, v_r) \le w_x \iff v_l \le w_x \text{ and } v_r \le w_x)。
• 取 min 时：(\min(v_l, v_r) \le w_x \iff \text{not}(v_l > w_x \text{ and } v_r > w_x))。

所以： [ f_u(x) = p_u \cdot [f_l(x) \cdot f_r(x)] + (1-p_u) \cdot [1 - (1 - f_l(x))(1 - f_r(x))] ] 化简： [ f_u(x) = p_u f_l(x) f_r(x) + (1-p_u)(f_l(x) + f_r(x) - f_l(x) f_r(x)) ] [ = p_u f_l(x) f_r(x) + (1-p_u)(f_l(x) + f_r(x) - f_l(x) f_r(x)) ] [ = (1-p_u)(f_l(x) + f_r(x)) + (2p_u - 1) f_l(x) f_r(x) ]

若只有一个子节点 (l)，那么 (u) 的权值就是子节点的权值（因为 min 或 max 同一个值），所以 (f_u(x) = f_l(x))。

---

第五步：得到概率质量 (g_u(x))

由 (g_u(x) = f_u(x) - f_u(x-1))（约定 (f_u(0)=0)）。

那么对于根节点 (1)，(D_i = g_1(t_i))，其中 (t_i) 是权值 (V_i) 在排序后叶节点权值列表中的下标。

---

第六步：计算目标式

[ S = \sum_{i=1}^m i \cdot V_i \cdot D_i^2 ] 其中 (i) 是按 (V_i) 从小到大排序后的秩（从 1 开始）。

我们可以这样想：对每个叶节点权值 (w_k)，设它是根节点权值的概率为 (p_k = g_1(k))。
排序后，第 (i) 小的权值对应的 (k) 是排序后的第 (i) 个叶节点权值，但这里 (m) 可能小于 (L)（因为有些叶节点权值根节点概率为 0）。

所以 (m) 是那些 (p_k > 0) 的 (k) 的个数，(V_i) 是对应的 (w_k)，且 (i) 是 (p_k > 0) 的权值按从小到大排序的序号。

那么 (S = \sum_{k: p_k>0} (\text{rank}(k)) \cdot w_k \cdot p_k^2)，其中 (\text{rank}(k)) 是 (w_k) 在 ({w_j \mid p_j>0}) 中的升序排名。

---

第七步：高效计算

我们需要：

1. 对所有叶节点权值排序得到 (w_1 < \dots < w_L)。
2. 对每个 (k=1..L)，计算 (g_1(k))（即根节点权值等于 (w_k) 的概率）。
3. 收集所有 (p_k > 0) 的 ((w_k, p_k))，按 (w_k) 排序，得到 rank，计算目标式。

---

计算 (g_1(k)) 需要先算 (f_1(x))，对 (x=1..L)。
直接对每个 (x) 做一次树形 DP？ (O(nL)) 太大（(L) 可达 (n)）。

但注意到 (f_u(x)) 关于 (x) 是非递减的（从 0 到 1），且它是分段常数吗？
实际上，因为叶节点的 (f) 是阶梯函数（从某个 (t) 开始为 1），经过上述多项式组合后，(f_u(x)) 是分段多项式（关于 (p_u) 的线性组合），但 (x) 是离散下标。

我们可以在所有叶节点权值排序后，递归时传递分段函数（即在不同 (x) 区间上 (f_u(x)) 的表达式）。

---

然而，更聪明的做法：
因为运算只有线性组合和乘法，而 (f_l(x), f_r(x)) 取值在 0 到 1 之间，我们可以用线段树合并来维护 (f_u) 的区间值，但这涉及实数的区间运算，模 998244353 下，概率用模数表示即可。

---

模数下的概率表示

题目给 (p_i \cdot 10000) 是正整数，所以 (p_i = \frac{\text{给定值}}{10000})，模 (998244353) 下，用逆元表示即可。

所以概率在模 (M = 998244353) 下运算。

那么 (f_u(x)) 是模 (M) 下的有理数，取值在 ([0,1]) 模意义下。

---

第八步：离散化权值与 DP

我们可以用权值线段树合并来维护每个节点 (u) 的分布函数 (f_u)（在离散化后的权值点上）。

具体：

• 对每个叶节点 (u)，在其权值对应位置 (t) 处，概率为 1（即 (g_u(t)=1)）。
• 对非叶节点，合并两棵子树权值线段树时，在每个权值点上按公式更新 (f) 值。

但注意：我们需要对每个权值点 (k) 存储 (f_u(k))（即权值 ≤ (w_k) 的概率）。
合并时，若我们在线段树节点上存储的是这个区间上所有值的概率分布的某些信息，合并需要区间操作，但公式是点对点的。

所以可以在线段树合并时，对每个叶节点（对应一个权值点 (k)）进行合并计算： [ f_u(k) = (1-p_u)(f_l(k) + f_r(k)) + (2p_u - 1) f_l(k) f_r(k) ] 模 (M) 运算。

这样我们可以在 (O(n \log L)) 时间内（(L) 是叶节点数）完成对所有 (k) 的 (f_1(k)) 计算。

---

第九步：得到 (g_1(k)) 并计算答案

由 (g_1(k) = f_1(k) - f_1(k-1))（模 (M)，注意负数加 (M)）。

然后收集所有 (g_1(k) > 0) 的权值 (w_k)，按 (w_k) 排序，得到 rank (i)，计算： [ S = \sum_{k: g_1(k) > 0} i(k) \cdot w_k \cdot (g_1(k))^2 \mod M ]

这里 (i(k)) 是 (w_k) 在正概率权值中的升序排名。

---

第十步：复杂度

• 离散化权值：(O(n \log n))。
• 线段树合并：(O(n \log L) \approx O(n \log n))。
• 最后收集答案：(O(L \log L))。

可行。

---

最终算法框架：

1. 读入 (n)，父亲数组，权值/概率数组。
2. 建树。
3. 收集所有叶节点权值，排序去重得到 (w[1..L])。
4. 对每个叶节点，记录其权值在 (w) 中的位置 (t)。
5. 递归 DFS，对每个节点 (u)：
   • 如果是叶子：创建线段树，在位置 (t) 处 (f=1)。
   • 如果有两个子节点：递归后，合并两棵线段树，在合并过程中对每个叶节点位置 (k) 按公式更新 (f) 值。
   • 如果只有一个子节点：直接复制子节点的线段树。
6. 从根节点的线段树中提取所有 (f_1(k))，计算 (g_1(k) = f_1(k) - f_1(k-1))。
7. 找出所有 (g_1(k) > 0) 的 (k)，按 (w_k) 排序得到 rank，计算目标式。
8. 输出答案模 (998244353)。

---

最终答案： [ \boxed{S = \sum_{i=1}^m i \cdot V_i \cdot D_i^2 \ (\mathrm{mod}\ M)} ] 通过上述线段树合并 DP 实现。