| Codeforces Beta Round 92 (Div. 1 Only) |
|---|
| Закончено |
Лабиринт представляет из себя дерево (неориентированный граф, в котором между любой парой вершин существует ровно один путь). В лабиринте с определенной вероятностью выбираются вершины входа и выхода. Выход из лабиринта ищется при помощи обхода в глубину, в случае нескольких возможных ходов, ход выбирается равновероятно. Рассмотрим псевдокод:
DFS(x)
if x == вершина выхода then
завершить обход дерева
flag[x] <- TRUE
перемешать порядок вершин в V(x) // здесь каждая перестановка V(x) равновероятна
for i <- 1 to length[V] do
if flag[V[i]] = FALSE then
count++;
DFS(V[i]);
count++;
V(x) — список вершин смежных с x. Массив flag изначально заполнен FALSE. Изначально DFS запускается с параметром вершины входа. По завершению обхода в переменной count будет находится количество ходов.
Требуется посчитать математическое ожидание количества ходов для нахождения выхода из лабиринта.
В первой строке задается число вершин в графе n (1 ≤ n ≤ 105). В следующих n - 1 строках задаются пары чисел ai и bi, которые показывают существования ребра между ai и bi вершинами (1 ≤ ai, bi ≤ n). Гарантируется, что заданный граф является деревом.
В следующих n строках задаются пары неотрицательных чисел xi и yi, которые характеризуют вероятность выбора i-ой вершины в качества входа и выхода соответственно. Вероятности выбрать вершину i в качестве входа и выхода равны 
и 
соответственно. Сумма по всем xi и сумма по всем yi положительны и не превосходят 106.
Выведите матожидание количества ходов. Абсолютная или относительная погрешность не должна превосходить 10 - 9.
2
1 2
0 1
1 0
1.00000000000000000000
3
1 2
1 3
1 0
0 2
0 3
2.00000000000000000000
7
1 2
1 3
2 4
2 5
3 6
3 7
1 1
1 1
1 1
1 1
1 1
1 1
1 1
4.04081632653
В первом примере вершина входа всегда 1 и вершина выхода всегда 2.
Во втором примере вершина входа всегда 1, вершина выхода с вероятностью 2/5 будет 2 или с вероятность 3/5 будет 3. Матожидания для вершин выхода 2 и 3 будут равны (симметричные случаи). На первом ходе с вероятностью 0.5 можно пойти в вершину выхода или с вероятностью 0.5 не в вершину выхода. В первом случаи количество ходов равно 1, во втором оно будет равно 3. Итоговое матожидание считается как 2 / 5 × (1 × 0.5 + 3 × 0.5) + 3 / 5 × (1 × 0.5 + 3 × 0.5)
