N. Save the Timeline!
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Rin knows that the universe can still be saved using a set of extremely powerful artifacts scattered through time across the entire multiverse. The entire multiverse and all of its states through time can be represented as a tree of size n, with nodes each representing a multiverse(at its own exact point in time), originating from a single point, the root, or Akasha. Rin starts at Akasha. The artifacts are located at certain nodes in this tree. As time moves forwards, depending on random events within the world, the state of the universe will begin to change. When the universe changes, it will move away from the root and towards one of its children states - the children on the tree. It will slowly move away until it reaches the ends of time - the leaves of the tree. With the power of Kaleidoscope, Rin is able to dictate the result of these tiny random fluctuations, thus letting her choose which path the current universe moves down. Unfortunately, she is unable to reverse time, and as a result is unable to move upwards in the tree - she must wait for the natural flow of time to take her down the tree. However, it is obvious that not all required artifacts can be reached if she can only move forward in time and away from the root. There is a solution to this though, and Rin realizes that the end of time is the same as the beginning - by reaching any of the leaves of the tree, she can return to Akasha, the beginning of time and the root. Since she is very impatient and doesn't want to get bored, Rin wants to know, given the set of universes she must reach to retrieve all the artifacts, the minimum number of epochs she must spend to collect all the artifacts. When Rin waits to descend one edge down the tree of time, she spends one epoch. However, it costs her no epochs to return to the root.

However, there is a special twist to make Rin's (and your) life harder. Rin doesn't actually know if each of the artifacts will appear. She does not even know the number that must appear - but she knows that no matter how many there are, she must retrieve each one. The probability an artifact occurs at node $$$i$$$ on the tree is $$$p_i$$$. She now wants you to calculate the expected value of the minimum number of epochs she must spend collecting the artifacts that do appear and return to Akasha at the end to Save The Timeline.

However, there is a second special twist to make everyone's lives even harder! Rin actually does have some information about what artifacts appear - but she is unsure of whether each piece of information is true. As a result, she asks you to compute the expected value of the minimum time she must spend in the case that each piece of information is true(the pieces of information are independent of each other). Each piece of information is made up of an integer $$$k$$$ and a set $$$S$$$ of size $$$k$$$, where Rin knows that all the nodes in set $$$S$$$ will have an artifact. The probabilities of any other artifacts appearing at nodes outside of that set remain the same. For each of $$$q$$$ queries, each consisting of a piece of information, calculate the expected value of the minimum number of epochs Rin will spend to collect all the artifacts that appear. All probabilities and expected values are computed under modulo $$$998244353$$$.

Here is a TLDR for all the people who don't care about saving the world:

You are given a tree of size $$$n$$$ rooted at node $$$1$$$. A node is active with probability $$$p_i$$$. The "cost" of a set of active nodes is the minimum number of epochs it takes to reach each node in the active set moving along the edges of the tree according to the following rules:

  • You will start, and must end at, the root.
  • It costs $$$1$$$ epoch to travel from a parent to child on the tree (again, rooted at node $$$1$$$).
  • It costs $$$0$$$ epochs to move from any leaf of the tree to the root.

Answer $$$q$$$ queries about the expected value of the cost of the set of active nodes. Each query contains an additional set of nodes $$$S$$$, where it is guaranteed that every node in that set will be active(the probabilities of other nodes not in $$$S$$$ being active remains unchanged, and each query is independent of the other queries). All probabilities and expected values are computed under modulo $$$998244353$$$. For more details, refer to the sample explanation.

Input

The first line of the input contains one integer $$$t$$$ $$$(1\leq t\leq 200)$$$, which is the number of multitests in the input.

Each individual multitest starts with one line containing two integers, $$$n$$$ $$$(1\leq n\leq 10^6)$$$ and $$$q$$$ $$$(1\leq q\leq 10^6)$$$, the size of the tree and the number of queries respectively.

The second line contains $$$n$$$ integers separated by spaces, representing $$$p_i$$$ $$$(0\leq p_i\leq 998244353)$$$ for each node.

The third to $$$n+1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ $$$(1\leq u,v\leq n)$$$ separated by spaces representing the edges of the tree.

The $$$n+2$$$ to $$$n+q+1$$$ lines each begin with one integer $$$k$$$ $$$(0\leq k\leq n)$$$. Following that(in the same line) are $$$k$$$ distinct integers separated by spaces, each in the range $$$[1,n]$$$, representing the set of nodes in the corresponding query.

It is guaranteed that the $$$0\leq \sum n , \sum k , \sum q \leq 10^6$$$ over all multitests in one test case.

 —

Test cases are enumerated from $$$1$$$ to $$$20$$$. Note that the data will not include samples.

Tests $$$1$$$-$$$5$$$: ($$$1\leq t\leq 100$$$, $$$1\leq n\leq 10$$$)

Tests $$$6$$$-$$$10$$$: ($$$1\leq \sum n\leq 5\cdot 10^3$$$,$$$1\leq\sum q,\sum k\leq 10^4$$$)

Tests $$$11$$$-$$$15$$$: ($$$1\leq \sum n\leq 2.5 \cdot 10^5$$$,$$$1\leq\sum q,\sum k\leq 2.5\cdot 10^5$$$))

Tests $$$16$$$-$$$20$$$: No additional constraints

Output

For each multitest, output $$$q$$$ lines, each containing one integer representing the answer to the queries made in order.

Examples
Input
1
3 2
1 665496236 499122177
1 2
2 3
0
1 2
Output
665496237
2
Input
2
4 4
460452453 858229637 612540950 778705078
2 1
3 4
4 1
4 3 2 4 1
2 3 1
1 4
3 1 3 2
4 4
531941972 134585184 7809514 711761406
2 1
3 2
4 1
4 1 2 4 3
3 1 2 3
4 1 4 2 3
3 4 2 1
Output
3
858229639
858229639
3
3
711761408
3
3
Note

In the first sample, there is a tree of size $$$3$$$, rooted at $$$1$$$ with an edge to $$$2$$$ then to $$$3$$$. The probabilities of node $$$1$$$, node $$$2$$$, and node $$$3$$$ being active respectively are $$$1$$$, $$$\frac{2}{3}\equiv 2(3^{-1})\equiv 665496236 \mod 998244353$$$, and $$$\frac{1}{2}\equiv 1(2^{-1})\equiv 499122177\mod 998244353$$$.

In the first query, there are no forced active nodes. However, since $$$p_1=1$$$, it is always active. There are $$$4$$$ cases: if node $$$2$$$ and node $$$3$$$ are both active (probability $$$\left(\frac{2}{3}\right)\left(\frac{1}{2}\right)$$$), if node $$$2$$$ is active but node $$$3$$$ is not (probability $$$\left(\frac{2}{3}\right)\left(1-\frac{1}{2}\right)$$$), if node $$$3$$$ is active but node $$$2$$$ is not (probability $$$\left(1-\frac{2}{3}\right)\left(\frac{1}{2}\right)$$$), and if neither node $$$2$$$ nor $$$3$$$ are active (probability $$$\left(1-\frac{2}{3}\right)\left(1-\frac{1}{2}\right)$$$). If no node is active, the minimum cost is $$$0$$$, as by not moving from the root all the active nodes are reached. If either node $$$2$$$ or $$$3$$$ is active, the minimum cost is $$$2$$$, as you must move from node $$$1$$$ downwards and then, to reach the root once again, reach node $$$3$$$ and teleport back to node $$$1$$$. As a result, the answer to this query is $$$\left(1-\left(1-\frac{2}{3}\right)\left(1-\frac{1}{2}\right)\right) (2)+\left(1-\frac{2}{3}\right)\left(1-\frac{1}{2}\right)(0)=\frac{5}{3}\equiv 5(3^{-1})\equiv 665496237 \mod 998244353$$$.

In the second query, node $$$2$$$ is forced to be active. Note that this query is completely independent of the previous one. Again, $$$p_1=1$$$ so node $$$1$$$ is active as well. In this case, no matter whether node $$$3$$$ is active or not, the minimum cost is $$$2$$$ with the path $$$1\rightarrow 2\rightarrow 3\rightarrow 1$$$, so the answer is simply $$$2$$$.

 —

Problem Idea: hyforces

Problem Preparation: hyforces

Occurrences: Advanced $$$7$$$