Задача №112587. Паша и тропинки
Как Вы уже поняли, дядя Паша любит гулять. Сегодня на улице стоит очень хорошая погода, поэтому, недолго думая, Паша оделся, взял ноутбук и пошел в парк поблизости.
Посмотрев на карту, расположенную около входа, Паша понял, что парк представляет собой дерево, где тропинки — рёбра, а их пересечения — вершины дерева. Прикинув свою среднюю скорость, Паша посчитал для каждой тропинки, сколько ему нужно времени для её прохождения.
Однако не все так просто. Некоторые тропинки в парке ещё не высохли после дождей, поэтому они грязные. Но Пашу это не останавливает, он решил посчитать среднее время, которое он потратит на прохождение простого пути, в котором есть хотя бы одна чистая тропинка. Более формально, Пашу интересует среднее время прохождения пути между двумя вершинами по всем таким парам вершин, что на пути между ними есть хотя бы одна чистая дорожка.
Тут к нему подошел друг Филя, с которым Паша договорился встретиться. Паша достал ноутбук, дал его Филе и попросил посчитать его ответ на этот непростой вопрос. Филя — так себе программист, поэтому он скорее всего не справится с этой задачей. Помогите ему!
В первой строке входного файла содержится число n ( 1 ≤ n ≤ 10 5 ) — количество пересечений тропинок в парке.
В следующих n - 1 строке входного файла дана информация о тропинках. В каждой строке записано четыре числа a , b , c , d ( 1 ≤ a , b ≤ n , 0 ≤ c ≤ 10 4 , 0 ≤ d ≤ 1 ) — номера вершин, между которыми проведена i -ая тропинка, время, за которое Паша пройдет эту тропинку, и число, описывающее состояние тропинки (0 — грязная тропинка, 1 — чистая).
В единственной строке выходного файла выведите ответ на задачу.
Ответ будет считаться верным, если относительная погрешность не будет превосходить 10 - 6 .
Тесты к этой задаче состоят из трех групп:
-
Первая группа тестов состоит из тестов, для которых выполняется ограничение
n
≤ 100
. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет
20
баллов.
-
Вторая группа тестов состоит из тестов, для которых выполняется ограничение
n
≤ 3000
. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет
40
баллов.
- Третья группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 10 5 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.
3 1 2 1 1 1 3 1 1
1.3333333333
3 1 2 1 1 1 3 2 0
2.0000000000