Karen is a girl who loves algorithms, and among many, she particularly enjoys Depth First Search (DFS).
One day, Karen obtained a rooted tree with root $root$, where each node $x$ has a weight $a_x$.
Starting from node $x$ in the tree to find node $y$, the DFS process can be described as follows:
- Initialize the recursion stack to be empty.
- Push node $x$ onto the recursion stack.
- Pop the top node from the recursion stack. If this node is $y$, terminate the process. Otherwise, if there exist unvisited direct children, choose one child uniformly at random and push it onto the recursion stack.
- Repeat step 3 until there are no unvisited direct children.
- Push the parent node back onto the recursion stack and repeat step 3.
- Repeat step 5 until the current node is $x$, at which point the process terminates.
We define $f(x, y)$ to be valid if and only if $y$ is in the subtree of $x$. Its value is the expected minimum weight among all nodes (including $x$ and $y$) visited during the DFS from $x$ to find $y$.
Karen wants to know the sum of $f(x, y)$ for all valid pairs $(x, y)$. You only need to output the result modulo $998\,244\,353$. Specifically, if the answer is represented as an irreducible fraction $\frac{a}{b}$, output $a \times b^{-1} \pmod{998\,244\,353}$.
Input
The input contains multiple test cases. The first line contains the number of test cases $T$.
For each test case, the first line contains two integers $n$ and $root$, representing the size of the tree and the index of the root, respectively.
The next line contains $n$ integers $a_1, a_2, \dots, a_n$, representing the weight of each node in the tree.
The next $n-1$ lines each contain two integers $u$ and $v$, representing an edge between $u$ and $v$.
Output
For each test case, output a single line containing one integer, representing the sum of $f(x, y)$ for all valid pairs $(x, y)$ modulo $998\,244\,353$.
Constraints
For all test cases, $1 \le T \le 100$, $\sum n \le 800\,000$, $1 \le n \le 400\,000$, $1 \le root, u, v \le n$, and $1 \le a_i \le 10^9$.
The specific constraints for each test case are as follows:
| Test Case ID | $\sum n \le$ | $n \le$ | Special Constraints |
|---|---|---|---|
| 1 | 50 | 10 | None |
| 2 ~ 4 | 40\,000 | 5\,000 | None |
| 5 ~ 10 | 400\,000 | 100\,000 | None |
| 11 | 800\,000 | 400\,000 | Randomly generated tree |
| 12 | 800\,000 | 400\,000 | Tree is a chain |
| 13 | 800\,000 | 400\,000 | Degree of root is $n-1$ |
| 14 ~ 20 | 800\,000 | 400\,000 | None |
For test case 11, the tree is generated as follows: with 1 as the root, for each node $i \in [2, n]$, choose a parent uniformly at random from $[1, i-1]$. Then, randomly permute the node labels.
Examples
Input 1
See the provided files dfs_ex1.in and dfs_ex2.in.
Output 1
See the provided files dfs_ex1.ans and dfs_ex2.ans.