Задача: Красота фейерверка
В лаборатории теоретической пиротехники изучают новые технологии организации
фейерверков. Фейерверк представляется как корневое дерево, а поскольку в мощном
фейерверке его элементы также взрываются, порождая новые фейерверки, то ученые вводят
операцию возведения корневого дерева в степень.
Корневое дерево содержит одну или несколько вершин. Одна из вершин выделена и
называется корнем дерева, для каждой из остальных вершин ровно одна другая вершина
является родителем. При этом от любой вершины можно добраться до корня,
последовательно переходя от вершины к ее родителю. Вершина, которая не является
родителем никакой другой вершины, называется листом. Если вершина x является
родителем вершины y, то вершина y является ребенком вершины x. Будем говорить, что
вершина и ее родитель соединены ребром.
На рис. 1 показан пример корневого дерева с корнем в вершине 1. Родителем вершин
2 и 3 является вершина 1, родителем вершины 4 является вершина 2. Вершины 2 и 3 — дети
вершины 1, а вершина 4 — ребенок вершины 2. Листьями являются вершины 3 и 4.
Рис. 1. Пример корневого дерева с корнем в вершине 1, листьями 3 и 4.
Фейерверк задается своим базовым деревом T и мощностью m. Фейерверк представляется деревом, которое получается в результате возведения дерева T в степень m. Операция возведения дерева в степень устроена следующим образом. Если m = 1, то результат T
1 — само дерево T. Для m > 1 рассмотрим дерево T
m – 1 . Выполним следующую операцию: для каждого листа x дерева T
m – 1 создадим копию дерева T и назначим лист x родителем корня соответствующей копии. Получившееся дерево будет деревом T
m .
На рис. 2 показано дерево, представленное на рис. 1, в степенях 1, 2 и 3.
Рис. 2. Пример возведения дерева в степени 1, 2 и 3
Путем в дереве называется последовательность вершин, в которой две соседние
вершины соединены ребром. Все вершины в пути должны быть различны.
Для того, чтобы оценить красоту фейерверка, необходимо определить, какое
максимальное количество вершин может содержать путь в дереве, которым представляется
фейерверк. На рис. 3 приведен путь в дереве T2, содержащий максимальное количество
вершин. Таким образом, красота фейерверка с базовым деревом T и мощностью 2 равна 10.
Рис. 3. Путь в дереве T
2 , содержащий максимальное количество вершин.
Требуется написать программу, которая по описанию дерева T и натуральному числу m определяет красоту фейерверка с базовым деревом T и мощностью m.
Формат входных данных
Первая строка входных данных содержит два натуральных числа n и m — количество
вершин в базовом дереве фейерверка T и его мощность (3 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000).
Вторая строка описывает дерево T и содержит (n – 1) целых чисел: p2, p3, …, pn —
номера родителей вершин 2, 3, …, n, соответственно (1 ≤ pi ≤ i – 1).
Формат выходных данных
Требуется вывести одно целое число — красоту фейерверка, представляемого
деревом Tm.
Ваш ответ: