Огни на склонах Чункурчака


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На склонах урочища Чункурчак стоят 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.


Комментарии

Еще нет ни одного комментария.