P10305 [THUWC 2020] Reverse Bubble Sort

> 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.

**Bubble sort** is a well-known sorting algorithm. Its idea is to repeatedly swap two adjacent elements that are in the wrong order. Since the total number of inversions keeps decreasing, bubble sort must terminate. The bubble sort algorithm that sorts $a[0], a[1], \dots, a[n-1]$ **in nondecreasing order** can be described by the following pseudocode. ```cpp for (int i = 1; i a[j+1]) { tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } ``` Here, $k$ is called the number of passes of bubble sort. When $k = n$, it is guaranteed that the sequence is sorted in nondecreasing order. **Reverse Bubble Sort** is a lesser-known algorithm. Given a sequence $a$ of length $n$ and a parameter $k$, it outputs all possible sequences $b$ such that after applying $k$ passes of bubble sort to $b$, the result becomes $a$. You are given a tree $T$ with nodes numbered $1,2,\dots,n$. Each node $u$ has a weight $p(u)$, and it is guaranteed that $p(1), p(2), \dots, p(n)$ form a permutation of $\{1,2,\dots,n\}$. In other words: 1. For $u \ne v$, we have $p(u) \ne p(v)$. 2. For any $i \in \{1, 2, \dots, n\}$, there exists a node $u$ such that $p(u)=i$. There are $m$ queries. Each query gives two nodes $u, v$ and a parameter $k$. Let $t_1, t_2, \dots, t_l$ be the sequence consisting of the **node weights of all nodes on the unique simple path from $u$ to $v$ in order**. Clearly, $t_1$ is $p(u)$ and $t_l$ is $p(v)$. You need to compute, after performing Reverse Bubble Sort on sequence $t$ with parameter $k$, how many permutation sequences will be output. In other words, compute how many sequences satisfy that **after $k$ passes of bubble sort, they become sequence $t$**. Since the answer can be very large, output it modulo $998,244,353$ (that is, output the remainder when the answer is divided by $998,244,353$).

The first line contains two natural numbers $n, m$ separated by spaces, denoting the number of nodes and the number of queries. The next line contains $n$ integers $p(1), p(2), \dots, p(n)$ separated by spaces, denoting the weight of each node. The next $n-1$ lines each contain two numbers $x_i, y_i$, indicating that there is an edge connecting $x_i$ and $y_i$ in the tree. The input guarantees that all edges form a tree. The next $m$ lines each contain a query $u_i, v_i, k_i$, whose meaning has been explained in the description.

Output $m$ lines. The $i$-th line contains one integer, denoting the answer to the $i$-th query modulo $998,244,353$.

**[Sample Explanation #1]** In this sample, the tree is a chain of length $4$. 1. For the first query, the visited node sequence is $[1]$, the weight sequence is $[1]$, and Reverse Bubble Sort outputs $\{[1]\}$. 2. For the second query, the visited node sequence is $[1,2]$, the weight sequence is $[1,3]$, and Reverse Bubble Sort outputs $\{[1,3], [3,1]\}$. 3. For the third query, the visited node sequence is $[1,2,3]$, the weight sequence is $[1,3,2]$, and Reverse Bubble Sort outputs $\{\}$. 4. For the fourth query, the visited node sequence is $[1,2,3,4]$, the weight sequence is $[1,3,2,4]$, and Reverse Bubble Sort outputs $\{[1,3,4,2], [3,1,4,2], [1,4,3,2], [4,1,3,2]\}$. **[Subtasks]** |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$| **For all testdata,** $1\le n,m\le 5\times 10^5, 0\le k\le n$. **Meaning of data types:** - $\mathrm{Type}=1$: The tree is a chain, i.e. $x_i = i, y_i=i+1$, and all queries satisfy $u_1=1, v_i=n$. - $\mathrm{Type}=2$: The tree is a chain, i.e. $x_i = i, y_i=i+1$, and all queries satisfy $u_i < v_i$. - $\mathrm{Type}=3$: No special restrictions. **[Hint]** > 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. Translated by ChatGPT 5