F. Кучи
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево на n вершинах с корнем в вершине 1.

Скажем, что в вершине u содержится k-ичная куча глубины m, если выполняется следующее:

  • При m = 1 вершина u сама является k-ичной кучей глубины 1.
  • При m > 1 вершина u является k-ичной кучей глубины m, если хотя бы k из ее детей являются k-ичными кучами глубины не менее m - 1.

Определим dpk(u) как максимальную глубину k-ичной кучи по всем вершинам в поддереве u (включая u). Требуется посчитать значение .

Входные данные

В первой строке задано число вершин n (2 ≤ n ≤ 3·105).

Следующие n - 1 строк содержат по два числа u, v, описывающие вершины, соединенные i-м ребром.

Гарантируется, что заданная конфигурация образует дерево.

Выходные данные

В единственной строке выведите одно число — ответ на задачу.

Примеры
Входные данные
4
1 3
2 3
4 3
Выходные данные
21
Входные данные
4
1 2
2 3
3 4
Выходные данные
22
Примечание

Рассмотрим первый пример.

Для k ≥ 3 все значения dpk будут равны 1.

При k = 2 dpk равняется 2 при и 1 в противном случае.

При k = 1 значения dpk равны (3, 1, 2, 1).

Таким образом, сумма равняется 4·1 + 4·1 + 2·2 + 2·1 + 3 + 1 + 2 + 1 = 21.