D. Межзвездная битва
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В межгалактической империи Баблдом $$$N$$$ планет, некоторые пары которых напрямую соединены двусторонними кротовыми норами. Всего есть $$$N-1$$$ кротовых нор. Кротовые норы имеют чрезвычайно важное значение в Баблдоме: множество планет в Баблдоме считается межгалактическим королевством, если и только если между любыми двумя планетами в этом множестве есть путь, использующий только кротовые норы. Известно, что весь Баблдом является королевством. Другими словами, сеть планет и кротовых нор является деревом.

На Баблдом напал мощный противник, владеющий технологией телепортации. Враг атакует каждую ночь, а правительство Баблдома возвращает все планеты под свой контроль днем. В течение одной ночи враг атакует каждую планету Баблдома один раз, но некоторые планеты более стойкие, чем другие. Планеты пронумерованы $$$0,1,…,N-1$$$, и планета номер $$$i$$$ будет захвачена врагом в вероятностью $$$p_i$$$. Перед каждой атакой (в том числе перед первой) правительство меняет вероятность захвата одной планеты (возможно как в большую, так и в меньшую сторону).

Правительство Баблдома заинтересовано в следующем вопросе: каково математическое ожидание межгалактических королевств, на которые Баблдом распадется после каждой из атак врага (и до того, как правительство вернет планеты под свой контроль)? Другими словами, найдите математическое ожидание количества компонент связности после каждой атаки.

Входные данные

Первая строка содержит одно целое число $$$N$$$ ($$$1 \le N \le 10^5$$$), обозначающее число планет в Баблдоме (они пронумерованы от $$$0$$$ до $$$N-1$$$).

Следующая строка содержит $$$N$$$ различных вещественных чисел в интервале $$$[0,1]$$$, записанных с ровно двумя знаками после десятичной точки, определяющие начальные вероятности, с которыми каждая из планет будет захвачена.

Следующая $$$N-1$$$ строка содержит все кротовые норы Баблдома, каждая описывается двумя планетами, которые она соединяет.

Следующая строка содержит одно целое положительное число $$$Q$$$ ($$$1 \le Q \le 10^5$$$), обозначающее количество атак противника.

Каждая из следующих $$$Q$$$ строк содержит одно целое неотрицательное число и одно вещественное число в интервале $$$[0,1]$$$, обозначающее планету, вероятность захвата которой меняет правительство, и эту новую вероятность.

Выходные данные

Выведите $$$Q$$$ чисел, каждое из которых означает математическое ожидание числа королевств, которые могут получиться после каждой из атак противника. Ваш ответ будет зачтен, если его абсолютная или относительная ошибка не превосходит $$$10^{-4}$$$.

Пример
Входные данные
5
0.50 0.29 0.49 0.95 0.83
2 3
0 3
3 4
2 1
3
4 0.66
1 0.69
0 0.36
Выходные данные
1.68040
1.48440
1.61740