Красота фейрверка
В лаборатории теоретической пиротехники изучают новые технологии организации фейерверков. Фейерверк представляется как корневое дерево, а поскольку в мощном фейерверке его элементы также взрываются, порождая новые фейерверки, то ученые вводят операцию возведения корневого дерева в степень.
Корневое дерево содержит одну или несколько вершин. Одна из вершин выделена и называется корнем дерева, для каждой из остальных вершин ровно одна другая вершина является родителем . При этом от любой вершины можно добраться до корня, последовательно переходя от вершины к ее родителю. Вершина, которая не является родителем никакой другой вершины, называется листом . Если вершина x является родителем вершины y , то вершина y является ребенком вершины x . Будем говорить, что вершина и ее родитель соединены ребром .
На рис. 1 показан пример корневого дерева с корнем в вершине 1 . Родителем вершин 2 и 3 является вершина 1 , родителем вершины 4 является вершина 2 . Вершины 2 и 3 — дети вершины 1 , а вершина 4 — ребенок вершины 2 . Листьями являются вершины 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 .
Путем в дереве называется последовательность вершин, в которой две соседние вершины соединены ребром. Все вершины в пути должны быть различны. Для того, чтобы оценить красоту фейерверка, необходимо определить, какое максимальное количество вершин может содержать путь в дереве, которым представляется фейерверк. На рис. 3 приведен путь в дереве T 2 , содержащий максимальное количество вершин. Таким образом, красота фейерверка с базовым деревом T и мощностью 2 равна 10 .
Требуется написать программу, которая по описанию дерева T и натуральному числу m определяет красоту фейерверка с базовым деревом T и мощностью m .
Первая строка входных данных содержит два натуральных числа n и m — количество вершин в базовом дереве фейерверка T и его мощность ( 3 ≤ n ≤ 200000 , 1 ≤ m ≤ 200000 ). Вторая строка описывает дерево T и содержит ( n – 1 ) целых чисел: p 2 , p 3 , ..., p n — номера родителей вершин 2 , 3 , ..., n , соответственно ( 1 ≤ p i ≤ i – 1 ).
Требуется вывести одно целое число — красоту фейерверка, представляемого деревом T^m.
4 2 1 1 2
10