В информатике есть метод под названием «Разделяй и властвуй по вершине», используемый для решения тяжелых задач про пути на дереве. Опишем принцип работы этого метода функцией:
solve(t) (t — дерево):
- Выберите вершину x (обычно выбирается взвешенный центр) в дереве t. Назовем этот шаг алгоритма «строка A».
- Проделайте нужную работу с путями, проходящими через вершину x.
- Затем удалите x из дерева t.
- После этого t превращается в некоторое количество поддеревьев.
- Примените solve к каждому поддереву.
Этот процесс завершается, когда у t есть только одна вершина, потому что после ее удаления не остается ничего.
WJMZBMR ошибочно подумал, что можно выбрать любую вершину в «строке A». То есть, он выбирает вершину в «строке A» наугад. Ситуацию осложняет то, что по мнению юноши, у «дерева» должно быть одинаковое количество ребер и вершин! Таким образом, функция меняется следующим образом.
Определим переменную totalCost. Изначально значение totalCost равняется 0. Итак, solve(t) (теперь t — граф) выглядит так:
- totalCost = totalCost + (size of t). Операция «=» означает присвоение. (Size of t) означает количество вершин в t.
- Выберите наугад (равновероятно среди всех вершин t) вершину x в графе t.
- Затем удалите x из графа t.
- После этого t превратится в некоторое количество связных компонент.
- Примените solve к каждой компоненте.
Юноша применит solve к связному графу с n вершинами и n ребрами. Он думает, что функция будет работать быстро, но она очень медленная. Теперь юноша хочет узнать матожидание значения totalCost после выполнения этой процедуры. Можете ли Вы помочь ему?