← 返回题目列表

AtCoder · arc195_e

E. 随机树距离

中文机器翻译题面 查看原题

分数: 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.