分数: 900 点
问题陈述
有一个整数序列 A = (A_2,A_3,\ldots,A_N)。另外,对于整数序列 P=(P_2, P_3, \ldots ,P_N) 其中 1 \leq P_i \leq i-1 对于每个 i (2 \leq i \leq N),定义加权树 T(P) 与 N 顶点,以顶点为根 1,如下:
- 一棵有根树,其中,对于每个 i (2 \leq i \leq N),父级 i is P_i,以及之间的边的权重 i 和 P_i is A_i.
你被给予 Q 查询。按顺序处理它们。的 i第查询如下:
- 给你整数 u_i 和 v_i,每个之间 1 和 N。对于每一个可能的 (N-1)! 序列 P,拿树 T(P) 并考虑顶点之间的距离 u_i 和 v_i 在这棵树中。输出总和,模数 998244353,这些距离中的所有距离 T(P)。这里,两个顶点之间的距离 u_i 和 v_i 是连接它们的唯一路径(不多次访问同一顶点)上的边的权重之和。
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q A_2 A_3 \ldots A_N u_1 v_1 u_2 v_2 \vdots u_Q v_Q
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i第一个查询。
样本输入 1
3 2 1 1 1 2 1 3
示例输出 1
2 3
- If P = (1,1),然后在树中 T(P),顶点之间的距离 1 和 2 is 1,以及顶点之间的距离 1 和 3 is 1.
- If P = (1,2),然后在树中 T(P),顶点之间的距离 1 和 2 is 1,以及顶点之间的距离 1 和 3 is 2.
因此,顶点之间的总距离 1 和 2 总的来说 T(P) is 2,以及顶点之间的总距离 1 和 3 总的来说 T(P) is 3.
示例输入 2
2 1 100 1 2
示例输出 2
100
示例输入 3
9 6 765689282 93267307 563699854 951829154 801512848 389123318 924504746 596035433 3 8 2 5 5 8 2 9 8 9 5 7
示例输出 3
55973424 496202632 903509579 343265517 550981449 68482696
记得对总和取模 998244353.