Лабіринт
Limits: 4 sec., 1024 MiB
Зеник знаходиться в лабіринті, який можна представити як дерево з \(n\) вершинами та \(n - 1\) ребрами, де вершини — це кімнати, а ребра — проходи між ними. З кожної кімнати можливо добратися в кожну іншу використовуючи переходи між кімнатами. Вершина \(1\) є виходом з лабіринту, до якого Зеник прагне потрапити якомога швидше.
Кожну секунду всі ребра незалежно та рівноймовірно отримують нову орієнтацію. Для кожного ребра між двома суміжними вершинами \(u\) та \(v\) ребро стає орієнтованим або з \(u\) в \(v\), або з \(v\) в \(u\), з ймовірністю \(\frac{1}{2}\) кожне. Ребра ніколи не бувають двонаправленими; вони завжди орієнтовані лише в один бік.
Після зміни орієнтації ребер Зеник знає поточну орієнтацію всіх ребер і приймає рішення про свій наступний крок з метою мінімізувати очікуваний час досягнення вершини \(1\).
Зеник діє наступним чином:
Якщо з його поточної вершини \(v\) існує принаймні одне ребро, орієнтоване з \(v\) в сусідню вершину \(u\), він повинен обрати одну з таких вершин та переміститися до неї. Переміщення займає \(1\) секунду.
Якщо з вершини \(v\) немає жодних вихідних ребер, Зеник змушений чекати \(1\) секунду до наступної переорієнтації ребер.
Орієнтація ребер змінюється щосекунди, одразу перед тим, як Зеник приймає рішення про свій наступний крок.
Ваша задача — допомогти Зенику визначити для кожної вершини \(v\) (\(2 \leq v \leq n\)) математичне очікування часу (у секундах), необхідного для досягнення вершини \(1\), починаючи з вершини \(v\), за умови, що він діє оптимально, щоб мінімізувати цей час.
Input
Перший рядок містить одне ціле число \(n\) — кількість вершин у дереві.
\(i\)-ий з наступних \(n-1\) рядків містить два цілих числа \(u_i\) та \(v_i\), що означає, що між вершинами з цими індексами є ребро.
Output
Виведіть \(n - 1\) чисел. \(k\)-те число у рядку має означати математичне очікування для вершнини \(k\) + 1.
Відповідь буде зарахована, якщо її абсолютна чи відносна похибка не буде більшою ніж \(10^{-7}\).
Constraints
\(2 \le n \le 2 \cdot 10^5\),
\(1 \le u_i, v_i \le n\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 1 2 2 3 2 4 | 3.5000000000 5.5000000000 5.5000000000 |
| Input (stdin) | Output (stdout) |
|---|---|
| 2 1 2 | 2.0000000 |
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|