E. LeaFalltime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output You are given a tree$$$^{\text{∗}}$$$ with $$$n$$$ vertices. Over time, each vertex $$$i$$$ ($$$1 \le i \le n$$$) has a probability of $$$\frac{p_i}{q_i}$$$ of falling. Determine the expected value of the number of unordered pairs$$$^{\text{†}}$$$ of distinct vertices that become leaves$$$^{\text{‡}}$$$ in the resulting forest$$$^{\text{§}}$$$, modulo $$$998\,244\,353$$$.Note that when vertex $$$v$$$ falls, it is removed along with all edges connected to it. However, adjacent vertices remain unaffected by the fall of $$$v$$$.$$$^{\text{∗}}$$$A tree is a connected graph without cycles. $$$^{\text{†}}$$$An unordered pair is a collection of two elements where the order in which the elements appear does not matter. For example, the unordered pair $$$(1, 2)$$$ is considered the same as $$$(2, 1)$$$.$$$^{\text{‡}}$$$A leaf is a vertex that is connected to exactly one edge.$$$^{\text{§}}$$$A forest is a graph without cyclesInputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).The $$$i$$$-th line of the following $$$n$$$ lines contains two integers $$$p_i$$$ and $$$q_i$$$ ($$$1 \le p_i < q_i < 998\,244\,353$$$).Each of the following $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the indices of the vertices connected by an edge.It is guaranteed that the given edges form a tree.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$. OutputFor each test case, output a single integer — the expected value of the number of unordered pairs of distinct vertices that become leaves in the resulting forest modulo $$$998\,244\,353$$$.Formally, let $$$M = 998\,244\,353$$$. It can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$. ExamplesInput511 231 21 21 21 22 331 31 51 31 22 31998244351 998244352610 177 136 112 1010 195 134 33 61 43 53 2Output0
623902721
244015287
0
799215919
Input110282508078 551568452894311255 989959022893400641 913415297460925436 80190898594460427 171411253997964895 998217862770266391 885105593591419316 976424827606447024 863339056940224886 9942445539 59 69 88 73 61 57 48 104 2Output486341067
NoteIn the first test case, only one vertex is in the tree, which is not a leaf, so the answer is $$$0$$$.In the second test case, the tree is shown below. Vertices that have not fallen are denoted in bold. Let us examine the following three cases: We arrive at this configuration with a probability of $$$\left( \frac{1}{2} \right) ^3$$$, where the only unordered pair of distinct leaf vertices is $$$(2, 3)$$$. We arrive at this configuration with a probability of $$$\left( \frac{1}{2} \right) ^3$$$, where the only unordered pair of distinct leaf vertices is $$$(2, 1)$$$. We arrive at this configuration with a probability of $$$\left( \frac{1}{2} \right) ^3$$$, where the only unordered pair of distinct leaf vertices is $$$(1, 3)$$$. All remaining cases contain no unordered pairs of distinct leaf vertices. Hence, the answer is $$$\frac{1 + 1 + 1}{8} = \frac{3}{8}$$$, which is equal to $$$623\,902\,721$$$ modulo $$$998\,244\,353$$$.