Огни на склонах Чункурчака
На склонах урочища Чункурчак стоят n фонарей, соединённых n − 1 дорожками так, что получается дерево. Вечером фонарь i зажигается с вероятностью p[i] / 100, независимо от остальных.
Горящие фонари вместе с дорожками между двумя горящими фонарями распадаются на «островки света» — компоненты связности. Пусть C — количество островков. Найдите математическое ожидание величины C².
Можно доказать, что ответ — рациональное число P / Q, где Q не делится на 998244353. Выведите P · Q⁻¹ по модулю 998244353.
Входные данные
В первой строке — число n (1 ≤ n ≤ 2 · 10⁵). Во второй строке — n целых чисел p[1], …, p[n] (0 ≤ p[i] ≤ 100). В каждой из следующих n − 1 строк — два числа u v: дорожка между фонарями u и v.
Выходные данные
Выведите E[C²] по модулю 998244353.
Пример 1
Вход:
3
50 50 50
1 2
2 3
Выход:
748683266
Пояснение
В первом примере три фонаря на одной линии 1 – 2 – 3 горят с вероятностью 1/2 каждый. Восемь вариантов равновероятны: при всех погашенных C = 0, при одном горящем C = 1, при горящих 1 и 3 C = 2, в остальных случаях C = 1. Получаем E[C²] = (0 + 1 + 1 + 1 + 4 + 1 + 1 + 1) / 8 = 10 / 8 = 5 / 4.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 12.
Комментарии