| Codeforces Round 471 (Div. 2) |
|---|
| Закончено |
Дано дерево на 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.
