AT_arc195_e [ARC195E] Random Tree Distance

给定一个整数列 $A = (A_2, A_3, \ldots, A_N)$。对于每个满足 $1 \leq P_i \leq i-1$（$2 \leq i \leq N$）的整数序列 $P = (P_2, P_3, \ldots, P_N)$，定义以顶点 $1$ 为根的 $N$ 顶点带权树 $T(P)$ 如下： - 对于每个 $i$（$2 \leq i \leq N$），顶点 $i$ 的父节点为 $P_i$，且连接 $i$ 与 $P_i$ 的边权值为 $A_i$。 现需处理 $Q$ 个查询。第 $i$ 个查询形式如下： - 给定两个整数 $u_i, v_i$（$1 \leq u_i < v_i \leq N$），求所有可能的 $(N-1)!$ 种 $P$ 序列对应的树 $T(P)$ 中，顶点 $u_i$ 与 $v_i$ 之间距离的总和对 $998244353$ 取模后的结果。其中，顶点 $u_i$ 与 $v_i$ 的距离定义为连接它们的唯一简单路径上的边权总和。

输入通过标准输入给出，格式如下： > $N$ $Q$ > $A_2$ $A_3$ $\ldots$ $A_N$ > $u_1$ $v_1$ > $u_2$ $v_2$ > $\vdots$ > $u_Q$ $v_Q$

输出 $Q$ 行，每行对应一个查询的答案。

### 约束条件 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq Q \leq 2 \times 10^5$ - $1 \leq A_i \leq 10^9$ - $1 \leq u_i < v_i \leq N$ - 输入中的所有值均为整数 ### 样例解释 1 - 当 $P = (1, 1)$ 时，树 $T(P)$ 中顶点 $1$ 与 $2$ 的距离为 $1$，顶点 $1$ 与 $3$ 的距离为 $1$。 - 当 $P = (1, 2)$ 时，树 $T(P)$ 中顶点 $1$ 与 $2$ 的距离为 $1$，顶点 $1$ 与 $3$ 的距离为 $2$。 因此，所有 $P$ 对应的顶点 $1$ 与 $2$ 的距离总和为 $2$，顶点 $1$ 与 $3$ 的距离总和为 $3$。 ### 样例解释 3 注意最终需输出总和对 $998244353$ 取模后的结果。 翻译由 DeepSeek R1 完成