НачалоПодразделы
Другие разделы
| Тренировка 1 |
| Тренировка 2 |
| Тренировка 4 |
| Тренировка 5 |
Дата и время
20/12/2024 10:28:09
Тренировка 3
A. Average distance B. Bus Pass C. Cutting Banknotes D. Dice Password Security E. Lingo F. Splitting the Loot G. Pachinko H. Hiking I. Ranking J. Stock
A. 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
