Лабіринт#12949

Лабіринт (Editorial)

Використаємо метод динамічного програмування. Для кожного орієнтованого ребра , де — батько вершини , порахуємо математичне очікування часу, необхідного для переходу з вершини до вершини . Тоді відповідь на задачу для будь-якої вершини - це сума на вертикальному шляху від до 1.

dp[v, p] можна порахувати наступним чином. Нехай t_1, t_2, ..., t_k - сини вершини , посортовані за зростанням значення dp[t_i, v]. Тоді dp[(v, p)] = 1 + 2^{-k} + \sum_{i=1}^k (1 +dp[t_i, v]) \cdot 2^{-i}.