← 返回题目列表

Codeforces · 2071/E

E. 叶落

中文机器翻译题面 查看原题

给你一棵树$$$^{\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}$$$ 。

示例

输入
复制

5
1
1 2
3
1 2
1 2
1 2
1 2
2 3
3
1 3
1 5
1 3
1 2
2 3
1
998244351 998244352
6
10 17
7 13
6 11
2 10
10 19
5 13
4 3
3 6
1 4
3 5
3 2

输出
复制

0
623902721
244015287
0
799215919

输入
复制

1
10
282508078 551568452
894311255 989959022
893400641 913415297
460925436 801908985
94460427 171411253
997964895 998217862
770266391 885105593
591419316 976424827
606447024 863339056
940224886 994244553
9 5
9 6
9 8
8 7
3 6
1 5
7 4
8 10
4 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$$$。