В информатике есть метод под названием «Разделяй и властвуй по вершине», используемый для решения тяжелых задач про пути на дереве. Опишем принцип работы этого метода функцией:

solve(t) (t — дерево):

1. Выберите вершину x (обычно выбирается взвешенный центр) в дереве t. Назовем этот шаг алгоритма «строка A».
2. Проделайте нужную работу с путями, проходящими через вершину x.
3. Затем удалите x из дерева t.
4. После этого t превращается в некоторое количество поддеревьев.
5. Примените solve к каждому поддереву.

Этот процесс завершается, когда у t есть только одна вершина, потому что после ее удаления не остается ничего.

WJMZBMR ошибочно подумал, что можно выбрать любую вершину в «строке A». То есть, он выбирает вершину в «строке A» наугад. Ситуацию осложняет то, что по мнению юноши, у «дерева» должно быть одинаковое количество ребер и вершин! Таким образом, функция меняется следующим образом.

Определим переменную totalCost. Изначально значение totalCost равняется 0. Итак, solve(t) (теперь t — граф) выглядит так:

1. totalCost = totalCost + (size of t). Операция «=» означает присвоение. (Size of t) означает количество вершин в t.
2. Выберите наугад (равновероятно среди всех вершин t) вершину x в графе t.
3. Затем удалите x из графа t.
4. После этого t превратится в некоторое количество связных компонент.
5. Примените solve к каждой компоненте.

Юноша применит solve к связному графу с n вершинами и n ребрами. Он думает, что функция будет работать быстро, но она очень медленная. Теперь юноша хочет узнать матожидание значения totalCost после выполнения этой процедуры. Можете ли Вы помочь ему?