QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 4889. 愚蠢的在线法官

统计

你发现 SOJ,即 Stupid Online Judge,变得越来越愚蠢了,比如 SOJ 并不会做饭而你的狗勾会自己跑到厨房里做四菜一汤。

经过一番探索,你发现 SOJ 愚蠢的原因竟是它内置的在线线性代数求解系统!管理员们由于沉迷于线性代数,整天在研究如何快速计算 $2048$ 阶行列式,从而使得 SOJ 无人维护,甚至还占用了 SOJ 大量的性能。

这个系统里内置了(能在一秒内求解((阶为 $114514$ 秩为 $114513$ 的方阵)的行列式)的程序),本着吃饱了撑着的心理,你决定喂给这个系统若干行列式,但是你并不知道它啥时被你喂撑。为了更好地知道这个系统有没有被搞坏,你决定先自己计算出你提供的问题的答案。

当然管理员们认为他们自己的智商是在线的,所以他们写了一套规则防止这个系统被搞坏,于是你只能以如下的形式上传这个行列式:

  • 给系统一棵 $n$ 个点的有根树和每个点的点权 $v_i$,且令根为节点 $1$,同时传给系统一个长度为 $k$ 的数组 $A$,构造阶为 $k$ 的方阵 $B$ 其中 $b_{i,j} = v_{\mathrm{LCA}(A_i, A_j)}$,即:

$$ B = \begin{bmatrix} v_{\mathrm{LCA}(A_1, A_1)} & v_{\mathrm{LCA}(A_1, A_2)} & \cdots & v_{\mathrm{LCA}(A_1, A_k)} \\ v_{\mathrm{LCA}(A_2, A_1)} & v_{\mathrm{LCA}(A_2, A_2)} & \cdots & v_{\mathrm{LCA}(A_2, A_k)} \\ \vdots & \vdots & \ddots & \vdots \\ v_{\mathrm{LCA}(A_k, A_1)} & v_{\mathrm{LCA}(A_k, A_2)} & \cdots & v_{\mathrm{LCA}(A_k, A_k)} \\ \end{bmatrix} $$

  • 其中 $\mathrm{LCA}(x, y)$ 为节点 $x$ 和 $y$ 的最近公共祖先,当你传入数组 $A$ 后,将计算构造出来的这个方阵的行列式。

有了这样一套规则,SOJ 显得更蠢了。由于担心过大的数字会吓坏没见过世面的管理员们,你决定将方阵的值模 $998244353$ 后再给管理员们好好康康。

输入格式

第一行两个正整数 $n, k$,分别表示树的节点数和 $A$ 的长度。

第二行 $n$ 个非负整数 $v_i$ 表示每个点的点权。

第三行 $k$ 个正整数 $A_i$ 表示传给系统的数组。

下面 $n - 1$ 行,每行两个正整数 $u, v$,表示树上的一条无向边 $(u, v)$。

保证给出的边构成一棵树。

输出格式

一行一个范围在 $[0, 998244353)$ 的非负整数,表示答案。

样例一

input

3 2
1 2 3
2 3
1 2
1 3


output

5


explanation

得到的方阵的行列式是

$$ \begin{vmatrix} 2 & 1 \\ 1 & 3 \end{vmatrix} = 2 \times 3 - 1 \times 1 = 5 $$

样例二

input

5 1
225348648 810032443 884606707 501975769 428153443
4
1 5
3 5
2 1
4 1


output

501975769


样例三

input

10 5
948691377 65381930 199744893 359204892 47703053 527403959 682504024 581643492 374119650 567695458
5 7 3 8 2
6 3
8 6
10 3
9 3
2 6
1 2
5 3
7 9
4 1


output

141670859


样例四

见下发文件中的 ex_online4.inex_online4.ans

该样例满足子任务 $3$ 的性质。

样例五

见下发文件中的 ex_online5.inex_online5.ans

该样例满足子任务 $4$ 的性质。

样例六

见下发文件中的 ex_online6.inex_online6.ans

该样例满足子任务 $6$ 的性质。

限制与约定

对于所有数据,满足 $1 \leq n, k \leq 5 \times 10^5$,$v_i \in [0, 998244353)$,$A_i \in [1, n]$。

子任务编号 子任务分值 子任务依赖 特殊条件
$1$ $3$ $k > n$
$2$ $6$ $n \leq 10$
$3$ $11$ $k \leq 600$
$4$ $29$ $2$ $n \leq 3000$
$5$ $16$ $A$ 是 $1 \dots n$ 的排列
$6$ $35$ $1,3,4,5$

时间限制:$2 \texttt s$

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