UOJ Logo Universal Online Judge

UOJ

#745. 【ZJOI2022】深搜

附件下载 统计

九条可怜是一个喜欢算法的女孩子,在众多算法中她尤其喜欢深度优先搜索(DFS)。

有一天,可怜得到了一棵有根树,树根为 $\mathit{root}$,树上每个节点 $x$ 有一个权值 $a_x$。

在一棵树上从 $x$ 出发,寻找 $y$ 节点,如果使用深度优先搜索,则可描述为以下演算过程:

  1. 将递归栈设置为空。
  2. 首先将节点 $x$ 放入递归栈中。
  3. 从递归栈中取出栈顶节点,如果该节点为 $y$,则结束演算过程;否则,如果存在未访问的直接子节点,则以均等概率随机选择一个子节点加入递归栈中。
  4. 重复步骤 3,直到不存在未访问的直接子节点。
  5. 将上一级节点加入递归栈中,重复步骤 3。
  6. 重复步骤 5,直至当前一级节点为 $x$,演算过程结束。

我们定义 $f(x, y)$ 合法当且仅当 $y$ 在 $x$ 的子树中。它的值为从 $x$ 出发,对 $x$ 的子树进行深度优先搜索寻找 $y$ 期间访问过的所有节点(包括 $x$ 和 $y$)权值最小值的期望。

九条可怜想知道对于所有合法的点对 $(x, y)$,$\sum f(x, y)$ 的值。你只需要输出答案对 $998244353$ 取模的结果。具体地,如果答案的最简分数表示为 $\frac{a}{b}$,输出 $a \times b^{-1} \bmod 998244353$。

输入格式

输入包含多组数据,第一行输入数据组数 $T$。

对于接下来的每组数据,第一行两个整数 $n, \mathit{root}$,分别表示树的大小,树根的编号。

接下来一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$,表示树上每个节点的权值。

接下来 $n - 1$ 行,每行包含两个整数 $u, v$,表示 $u$ 和 $v$ 之间有一条树边。

输出格式

对于每组数据,输出一行,包含一个整数,代表对于所有合法点对 $(x, y)$,$\sum f(x, y)$ 对 $998244353$ 取模的结果。

样例一

input

4
1 1
1
3 3
3 3 4
3 1
3 2
6 1
5 2 4 1 3 6
1 2
1 6
2 3
2 4
4 5
5 1
5 4 3 2 1
1 2
1 3
3 4
3 5

output

1
16
34
499122202

explanation

样例二

见附件下载。

限制与约定

对于所有测试点,满足 $1 \le T \le 100$,$\sum n \le 8 \times {10}^5$,$1 \le n \le 4 \times {10}^5$,$1 \le \mathit{root}, u, v \le n$,$1 \le a_i \le {10}^9$。

每个测试点的具体限制见下表:

测试点编号 $\sum n \le$ $n \le$ 特殊限制
$1$ $50$ $10$
$2 \sim 4$ $40000$ $5000$
$5 \sim 10$ $4 \times {10}^5$ ${10}^5$
$11$ $8 \times {10}^5$ $4 \times {10}^5$ 树的生成方式随机
$12$ $8 \times {10}^5$ $4 \times {10}^5$ 树是一条链
$13$ $8 \times {10}^5$ $4 \times {10}^5$ 根的度数为 $n - 1$
$14 \sim 20$ $8 \times {10}^5$ $4 \times {10}^5$

对于测试点 $11$,树的生成方式为:以 $1$ 为根,对于节点 $i \in [2, n]$,从 $[1, i - 1]$ 中等概率随机选择一个点作为父亲。之后将编号随机重排。

时间限制:$5\texttt{s}$

空间限制:$1024\texttt{MB}$