P10305 [THUWC 2020] 序排泡冒

> You are given a peach tree $T$. > > You don't need to think of the peach. > > Because I'm going to talk about the tree.

**冒泡排序算法**是一种广为人知的排序算法，其思路在于不断地交换相邻且逆序的两个元素，由于总的逆序对个数不断减少，冒泡排序算法一定可以终止。给 $a[0], a[1], \dots, a[n-1]$ **从小到大排序**的冒泡排序算法可以用下面的伪代码描述。 ```cpp for (int i = 1; i a[j+1]) { tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } ``` 其中 $k$ 称为冒泡排序进行的轮数，当 $k$ 取 $n$ 时，便可以保证序列被从小到大排序。 **序排泡冒算法**是一种鲜为人知的序排算法，其作用是给定一个长度为 $n$ 的序列 $a$ 和参数 $k$，输出所有可能的序列 $b$，满足其经过 $k$ 轮冒泡排序之后成为序列 $a$。 给定一棵树 $T$，结点用 $1,2, \dots, n$ 编号。每一个结点 $u$ 有一个点权 $p(u)$，保证 $p(1), p(2), \dots, p(n)$ 构成了 $\{1,2,\dots,n\}$ 的一个排列。换言之，满足 1. 对于 $u\ne v$，均有 $p(u)\ne p(v)$； 2. 对于任意的 $i\in \{1, 2, \dots, n\}$，均存在一个 $u$ 满足 $p(u)=i$。 对于这棵树，我们将进行 $m$ 次询问，每次询问给出两个结点 $u, v$ 和一个参数 $k$。用 $t_1, t_2, \dots, t_l$ 表示从 $u$ 到 $v$ 的唯一简单路径上**依次经过的所有结点的点权**组成的序列，可以看出 $t_1$ 就是 $p(u)$，$t_l$ 就是 $p(v)$，你需要计算序列 $t$ 和参数 $k$ 进行序排泡冒后，输出的排列序列个数。换言之，求有多少个序列满足其**经过 $k$ 轮冒泡排序后得到序列 $t$**。 由于答案很大，你只需要输出其对 $998,244,353$ 取模的结果（也就是说，输出答案除以 $998,244,353$ 的余数）。

第一行包含两个用空格分隔的自然数 $n, m$，表示结点个数和询问个数。 接下来的一行包含 $n$ 用空格分隔的整数 $p(1), p(2), \dots, p(n)$，表示每个点的点权。 接下来 $n-1$ 行每行包含两个数 $x_i, y_i$，表示树上存在一条连接 $x_i$ 和 $y_i$ 上的边。输入的数据保证所有的边构成一棵树。 接下来 $m$ 行每行包含一个询问 $u_i, v_i, k_i$，其意义在题目描述中已经说明。

输出包含 $m$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个询问的答案对 $998,244,353$ 取模的结果。

**【样例解释 #1】** 在这组样例中，树构成了一个长度为 $4$ 的链。 1. 对于第一次询问，经过的结点序列为 $[1]$，点权序列为 $[1]$，序排泡冒输出 $\{[1]\}$。 2. 对于第二次询问，经过的结点序列为 $[1,2]$，点权序列为 $[1,3]$，序排泡冒输出 $\{[1,3], [3,1]\}$。 3. 对于第三次询问，经过的结点序列为 $[1,2,3]$，点权序列为 $[1,3,2]$，序排泡冒输出 $\{\}$。 4. 对于第四次询问，经过的结点序列为 $[1,2,3,4]$，点权序列为 $[1,3,2,4]$，序排泡冒输出 $\{[1,3,4,2], [3,1,4,2], [1,4,3,2], [4,1,3,2]\}$。 **【子任务】** |Subtask|$n$|$m$|$k$|Type|Score| |:--:|:--:|:--:|:--:|:--:|:--:| |$1$|$\le 5 \times 10^{5}$|$\le 5 \times 10^{5}$|$= 0$|$3$|$1$| |$2$|$\le 10$|$\le 1$|$\le n$|$1$|$4$| |$3$|$\le 10$|$\le 5 \times 10^{5}$|$\le n$|$3$|$3$| |$4$|$\le 10^{3}$|$\le 10^{3}$|$\le n$|$1$|$10$| |$5$|$\le 5 \times 10^{5}$|$\le 5 \times 10^{5}$|$\le n$|$1$|$12$| |$6$|$\le 5 \times 10^{5}$|$\le 5 \times 10^{5}$|$\le n$|$2$|$13$| |$7$|$\le 10^{3}$|$\le 10^{3}$|$\le n$|$3$|$5$| |$8$|$\le 10^{5}$|$\le 10^{5}$|$\le n$|$3$|$25$| |$9$|$\le 5 \times 10^{5}$|$\le 5 \times 10^{5}$|$\le n$|$3$|$27$| **对于所有数据，**$1\le n,m\le 5\times 10^5, 0\le k\le n$。 **数据类型含义：** - $\mathrm{Type}=1$：树构成一条链，即 $x_i = i,y_i=i+1$，并且所有的询问都满足 $u_1=1, v_i=n$。 - $\mathrm{Type}=2$：树构成一条链，即 $x_i = i,y_i=i+1$，并且所有的询问都满足 $u_i < v_i$。 - $\mathrm{Type} = 3$：无特殊限制。 **【提示】** > Don't be afraid of the pain in climbing. > > Your tough journey is just beginning. > > But the fruit you will gain is not only peaches. > > Keep counting on the tree! Young gentlemen and ladies. > > Hope in your heart will lead you to the destiny.