Вам дано дерево$$$^{\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$$$).
$$$i$$$-я строка из следующих $$$n$$$ строк содержит два целых числа $$$p_i$$$ и $$$q_i$$$ ($$$1 \le p_i < q_i < 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 < 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$$$.
| Codeforces Round 1007 (Div. 2) |
|---|
| Закончено |
