给你一棵树$$$^{\text{*}}$$$,有$$$n$$$个顶点。随着时间的推移,每个顶点 $$$i$$$ ($$$1 \le i \le n$$$) 掉落的概率为 $$$\frac{p_i}{q_i}$$$。确定无序对的数量$$$^{\text{†}}$$$的期望值 不同 顶点在生成的森林中成为叶子$$$^{\text{‡}}$$$$$$^{\text{§}}$$$,模 $$$998\,244\,353$$$。
请注意,当顶点 $$$v$$$ 掉落时,它会连同与其连接的所有边一起被删除。然而,相邻顶点仍然不受 $$$v$$$ 下降的影响。
$$$^{\text{*}}$$$树是没有环的连通图。
$$$^{\text{†}}$$$无序对是两个元素的集合,其中元素出现的顺序并不重要。例如,无序对 $$$(1, 2)$$$ 被视为与 $$$(2, 1)$$$ 相同。
$$$^{\text{‡}}$$$叶子是仅连接到一条边的顶点。
$$$^{\text{§}}$$$森林是没有循环的图
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。
以下 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$p_i$$$ 和 $$$q_i$$$ ($$$1 \le p_i \lt q_i \lt 998\,244\,353$$$)。
以下 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — 由边连接的顶点的索引。
保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数 - 成为结果森林中叶子的无序不同顶点对的数量的预期值,模 $$$998\,244\,353$$$。
正式地,令 $$$M = 998\,244\,353$$$。可以证明,精确答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出这样一个整数 $$$x$$$ 使得 $$$0 \le x \lt M$$$ 和 $$$x \cdot q \equiv p \pmod{M}$$$ 。
示例
输入复制
511 231 21 21 21 22 331 31 51 31 22 31998244351 998244352610 177 136 112 1010 195 134 33 61 43 53 2
输出复制
0 623902721 244015287 0 799215919
输入复制
110282508078 551568452894311255 989959022893400641 913415297460925436 80190898594460427 171411253997964895 998217862770266391 885105593591419316 976424827606447024 863339056940224886 9942445539 59 69 88 73 61 57 48 104 2
输出复制
486341067
注意
在第一个测试用例中,树中只有一个顶点,它不是叶子,所以答案是 $$$0$$$。
在第二个测试用例中,树如下所示。
未掉落的顶点以粗体表示。让我们看看以下三种情况:
我们以 $$$\left( \frac{1}{2} \right) ^3$$$ 的概率到达此配置,其中唯一无序的不同叶顶点对是 $$$(2, 3)$$$。
我们以 $$$\left( \frac{1}{2} \right) ^3$$$ 的概率到达此配置,其中唯一无序的不同叶顶点对是 $$$(2, 1)$$$。
我们以 $$$\left( \frac{1}{2} \right) ^3$$$ 的概率到达此配置,其中唯一无序的不同叶顶点对是 $$$(1, 3)$$$。 所有剩余的情况都不包含无序的不同叶顶点对。因此,答案是 $$$\frac{1 + 1 + 1}{8} = \frac{3}{8}$$$,它等于 $$$623\,902\,721$$$ 模 $$$998\,244\,353$$$。