C. Окрашивание красно-чёрного дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$n$$$ вершин, пронумерованных от 1 до $$$n$$$, и бинарная строка $$$s$$$ длины $$$n$$$, где $$$s_i = 1$$$ означает, что $$$i$$$-я вершина окрашена в красный цвет, а $$$s_i = 0$$$ означает, что $$$i$$$-я вершина окрашена в чёрный цвет. Разрешается выполнять следующую операцию:

  • Выбрать вершину $$$a$$$ ($$$1 \le a \le n$$$).
  • Сосед $$$b$$$ вершины $$$a$$$ выбирается равновероятно случайным образом.
  • Перекрасить вершину $$$a$$$ в цвет вершины $$$b$$$. Обратите внимание, что это изменяет цвет вершины, которую выбрали вы, а не той, которая была выбрана случайно и равномерно.

Требуется окрасить все вершины дерева в красный цвет, выполнив операцию любое количество раз (возможно, ноль). Вычислите минимальное ожидаемое число операций, необходимое для этого, если действовать оптимально. Изначально в дереве есть хотя бы одна красная вершина.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Вторая строка содержит бинарную строку $$$s$$$ длины $$$n$$$.

Следующие $$$n-1$$$ строк содержат по два целых числа, $$$i$$$-я из них содержит $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$), что означает наличие ребра между вершинами $$$u_i$$$ и $$$v_i$$$.

Гарантируется, что заданный граф является деревом, что в нём есть хотя бы одна красная вершина, и что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно вещественное число, представляющее минимальное ожидаемое число операций.

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

Формально, пусть ваш ответ равен $$$x$$$, а ответ жюри равен $$$y$$$. Ваш ответ будет зачтен, если и только если $$$\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$$$.

Пример
Входные данные
3
3
101
1 2
2 3
5
10010
1 2
2 3
3 4
2 5
3
010
1 2
2 3
Выходные данные
1.00000000000000000000
4.50000000000000000000
2.00000000000000000000
Примечание

В первом наборе входных данных только одна вершина окрашена в чёрный цвет, и у неё есть только два красных соседа, поэтому, если сначала применить операцию к второй вершине, то красное дерево получится всего за одну операцию.