| Codeforces Beta Round 79 (Div. 1 Only) |
|---|
| Закончено |
Геральд находится в старинном замке из n залов, соединенных n - 1 переходами. Из любого зала можно добраться до любого другого единственным способом, то есть граф представляет собой дерево. Изначально, в момент времени 0, Геральд находится в зале номер 1. Также в некотором другом зале этого замка находится клад, который Геральд хочет найти. Где именно находится клад неизвестно, он может быть с одинаковой вероятностью в любом из остальных n - 1 залов. Узнать о местонахождении клада Геральд может только тогда, когда придет непосредственно в тот зал. Тогда Геральд сразу же видит клад, и этот момент считается моментом достижения его цели.
Переходы между залами имеют различные длины. При этом, переходы считаются длинными, а залы — маленькими и хорошо освещенными, так что временем, которое Геральд находится в залах, можно пренебречь. Замок очень старый, поэтому переходы обваливаются сразу после того, как по ним пройдут два раза, неважно в какую сторону.
Геральд может ходить по замку, пользуясь переходами, и будет ходить до тех пор, пока не найдет клад. Естественно, Геральд хочет найти его как можно быстрее. Иными словами, он хочет действовать так, чтобы среднее время нахождения клада было как можно меньше. Каждый переход можно использовать не более двух раз. Поэтому Геральд заранее выбирает такую стратегию, которая позволяет обойти все залы.
Более формально, если клад окажется во втором зале, то Геральд найдет его в тот момент, когда первый раз окажется во втором зале — пусть это будет в момент t2. Если в третьем, то Геральд найдет его тогда, когда первый раз окажется в третьем зале. Пусть это произойдет в момент времени t3. И так далее. Таким образом, среднее время нахождения клада окажется равным 
.
В первой строке дано единственное целое число n (2 ≤ n ≤ 105) — количество залов в замке. В следующих n - 1 строках даны по три целых числа. В i-ой из этих строк расположены числа ai, bi и ti (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ti ≤ 1000) — номера залов, которые соединяет i-ый переход и время, которое требуется, чтобы пройти по этому переходу. Геральд изначально находится в зале номер 1. Гарантируется, что из любого зала можно дойти по переходам до любого другого зала.
Выведите одно вещественное число: искомое матожидание времени поиска клада. Ответ должен отличаться от правильного не более чем на 10 - 6.
2
1 2 1
1.0
4
1 3 2
4 2 1
3 2 3
4.333333333333334
5
1 2 1
1 3 1
1 4 1
1 5 1
4.0
В первой тесте в замке всего два зала, значит, клад находится во втором зале. Геральду потребуется одна минута, чтобы перейти из первого зала во второй.
Во втором тесте из первого зала Геральд может перейти только в третий. Из третьего он может перейти в первый или второй, но в первом он уже был, и из него он не может никуда попасть. Значит, ему нужно пойти во второй зал. Оттуда ему надо идти в 4 зал, потому что остальные залы уже посещены. Если клад окажется в третьем зале, Геральд найдет его через минуту, если во втором — через две, если в четвертом — через три. Среднее время — 2 минуты.
В третьем тесте Геральду нужно посетить 4 зала: второй, третий, четвертый и пятый. В них всех можно попасть только из первого зала. Значит, ему нужно поочередно заходить в эти 4 зала в один за другим и возвращаться обратно. В первом из этих залов Геральд окажется через минуту, во втором — через три, в третьем — через 5, в четвертом — через 7. Среднее время — 4 минуты.
