Условие
Подземелье — дерево из n пещер с n − 1 проходом. В каждом проходе сидит монстр с уровнем опасности w. Если герой проходит через этот проход, вероятность победить монстра равна p = 1/exp(w).
Герой стартует в пещере s, принцесса — в t. По дереву существует ровно один путь между s и t. Итоговая вероятность дойти равна произведению вероятностей побед, что можно записать в виде:
P = 1 / exp(W)
Найти целое W — суммарную опасность по пути.
Формат
n s t, затем n − 1 строк aᵢ bᵢ wᵢ.
Пример
2 1 2
1 2 1 → W = 1
5 3 2
1 2 6
3 5 2
1 4 5
1 3 1 → W = 7
(Путь 3 → 1 → 2: веса 1 + 6 = 7.)