Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
771. Average distance
Динамическое программирование и запоминающие функцииПоиск в глубину (DFS)
Олимпиадные задачи на английском языке
| 04/02/2008 | Зима 2008 дорешивание (3A) |
| 07/02/2008 | Тренировка (задачи Benelux APC 2007) (A) |
Ограничения: время – 3s/6s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Given a tree, calculate the average distance between two vertices in the tree. For example,
the average distance between two vertices in the following tree is
`(d_01\ +\ d_02\ +\ d_03\ +d_04\ +\ d_12\ +\ d_13\ +\ d_14\ +\ d_23\ +\ d_24\ +\ d_34)/10\ =\ (6+3+7+9+9+13+15+10+12+2)/10\ =\ 8.6`.
Figure 1: The first sample case
Input
On the first line an integer `t` `(1\ ≤\ t\ ≤\ 100)`: the number of test cases. Then for each test
case:
One line with an integer `n` `(2\ ≤\ n\ ≤\ 10000)`: the number of nodes in the tree. The
nodes are numbered from 0 to n 1.
`n-1` lines, each with three integers `a` `(0\ ≤\ a\ <\ n)`, `b` `(0\ ≤\ b\ <\ n)` and `d` `(1\ ≤\ d\ ≤\ 1000)`. There is an edge between the nodes with numbers `a` and `b` of length `d`. The
resulting graph will be a tree.
Output
For each testcase:
One line with the average distance between two vertices. This value should have
an absolute error of at most `10^{-3}`.
Sample Input
1 5 0 1 6 0 2 3 0 3 7 3 4 2
Sample Output
8.600
