{"problem":{"name":"[THUWC 2020] 序排泡冒","description":{"content":"**冒泡排序算法**是一种广为人知的排序算法，其思路在于不断地交换相邻且逆序的两个元素，由于总的逆序对个数不断减少，冒泡排序算法一定可以终止。给 $a[0], a[1], \\dots, a[n-1]$ **从小到大排序**的冒泡排序算法可以用下面的伪代码描述。 ```cpp for (int i = 1; i <= k; i++)     for (int j = 0; j < n-1; j++","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10305"},"statements":[{"statement_type":"Markdown","content":"**冒泡排序算法**是一种广为人知的排序算法，其思路在于不断地交换相邻且逆序的两个元素，由于总的逆序对个数不断减少，冒泡排序算法一定可以终止。给 $a[0], a[1], \\dots, a[n-1]$ **从小到大排序**的冒泡排序算法可以用下面的伪代码描述。\n\n```cpp\nfor (int i = 1; i <= k; i++)\n    for (int j = 0; j < n-1; j++)\n        if (a[j] > a[j+1]) {\n            tmp = a[j];\n            a[j] = a[j+1];\n            a[j+1] = tmp;\n        }\n```\n\n其中 $k$ 称为冒泡排序进行的轮数，当 $k$ 取 $n$ 时，便可以保证序列被从小到大排序。\n\n**序排泡冒算法**是一种鲜为人知的序排算法，其作用是给定一个长度为 $n$ 的序列 $a$ 和参数 $k$，输出所有可能的序列 $b$，满足其经过 $k$ 轮冒泡排序之后成为序列 $a$。\n\n给定一棵树 $T$，结点用 $1,2, \\dots, n$ 编号。每一个结点 $u$ 有一个点权 $p(u)$，保证 $p(1), p(2), \\dots, p(n)$ 构成了 $\\{1,2,\\dots,n\\}$ 的一个排列。换言之，满足\n\n1. 对于 $u\\ne v$，均有 $p(u)\\ne p(v)$；\n2. 对于任意的 $i\\in \\{1, 2, \\dots, n\\}$，均存在一个 $u$ 满足 $p(u)=i$。\n\n对于这棵树，我们将进行 $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$**。\n\n由于答案很大，你只需要输出其对 $998,244,353$ 取模的结果（也就是说，输出答案除以 $998,244,353$ 的余数）。\n\n## Input\n\n第一行包含两个用空格分隔的自然数 $n, m$，表示结点个数和询问个数。\n\n接下来的一行包含 $n$ 用空格分隔的整数 $p(1), p(2), \\dots, p(n)$，表示每个点的点权。\n\n接下来 $n-1$ 行每行包含两个数 $x_i, y_i$，表示树上存在一条连接 $x_i$ 和 $y_i$ 上的边。输入的数据保证所有的边构成一棵树。\n\n接下来 $m$ 行每行包含一个询问 $u_i, v_i, k_i$，其意义在题目描述中已经说明。\n\n## Output\n\n输出包含 $m$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个询问的答案对 $998,244,353$ 取模的结果。\n\n[samples]\n\n## Background\n\n> You are given a peach tree $T$. \n>\n> You don't need to think of the peach.\n>\n> Because I'm going to talk about the tree.\n\n## Note\n\n**【样例解释 #1】**\n\n在这组样例中，树构成了一个长度为 $4$ 的链。\n\n1. 对于第一次询问，经过的结点序列为 $[1]$，点权序列为 $[1]$，序排泡冒输出 $\\{[1]\\}$。\n2. 对于第二次询问，经过的结点序列为 $[1,2]$，点权序列为 $[1,3]$，序排泡冒输出 $\\{[1,3], [3,1]\\}$。\n3. 对于第三次询问，经过的结点序列为 $[1,2,3]$，点权序列为 $[1,3,2]$，序排泡冒输出 $\\{\\}$。\n4. 对于第四次询问，经过的结点序列为 $[1,2,3,4]$，点权序列为 $[1,3,2,4]$，序排泡冒输出 $\\{[1,3,4,2], [3,1,4,2], [1,4,3,2], [4,1,3,2]\\}$。\n\n**【子任务】**\n\n|Subtask|$n$|$m$|$k$|Type|Score|\n|:--:|:--:|:--:|:--:|:--:|:--:|\n|$1$|$\\le 5 \\times 10^{5}$|$\\le 5 \\times 10^{5}$|$= 0$|$3$|$1$|\n|$2$|$\\le 10$|$\\le 1$|$\\le n$|$1$|$4$|\n|$3$|$\\le 10$|$\\le 5 \\times 10^{5}$|$\\le n$|$3$|$3$|\n|$4$|$\\le 10^{3}$|$\\le 10^{3}$|$\\le n$|$1$|$10$|\n|$5$|$\\le 5 \\times 10^{5}$|$\\le 5 \\times 10^{5}$|$\\le n$|$1$|$12$|\n|$6$|$\\le 5 \\times 10^{5}$|$\\le 5 \\times 10^{5}$|$\\le n$|$2$|$13$|\n|$7$|$\\le 10^{3}$|$\\le 10^{3}$|$\\le n$|$3$|$5$|\n|$8$|$\\le 10^{5}$|$\\le 10^{5}$|$\\le n$|$3$|$25$|\n|$9$|$\\le 5 \\times 10^{5}$|$\\le 5 \\times 10^{5}$|$\\le n$|$3$|$27$|\n \n\n**对于所有数据，**$1\\le n,m\\le 5\\times 10^5, 0\\le k\\le n$。\n\n**数据类型含义：**\n\n- $\\mathrm{Type}=1$：树构成一条链，即 $x_i = i,y_i=i+1$，并且所有的询问都满足 $u_1=1, v_i=n$。\n- $\\mathrm{Type}=2$：树构成一条链，即 $x_i = i,y_i=i+1$，并且所有的询问都满足 $u_i < v_i$。\n- $\\mathrm{Type} = 3$：无特殊限制。\n\n**【提示】**\n\n> Don't be afraid of the pain in climbing.\n>\n> Your tough journey is just beginning.\n>\n> But the fruit you will gain is not only peaches.\n>\n> Keep counting on the tree! Young gentlemen and ladies.\n>\n> Hope in your heart will lead you to the destiny.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10305","tags":["2020","O2优化","THUWC"],"sample_group":[["4 4\n1 3 2 4\n1 2\n2 3\n3 4\n1 1 1\n1 2 1\n1 3 1\n1 4 1\n","1\n2\n0\n4\n"],["见附件中的 2.in。","见附件中的 2.ans。"]],"created_at":"2026-03-03 11:09:25"}}