Задано корневое дерево, состоящее из $$$n$$$ вершин. Вершины пронумерованы от $$$1$$$ до $$$n$$$, корень — это вершина $$$1$$$.
Вы можете совершить следующую операцию не более $$$k$$$ раз:
Высотой дерева называют максимальную глубину среди всех его вершин, а глубина вершины — это количество ребер на пути от корня до нее. Например, глубина вершины $$$1$$$ равна $$$0$$$, так как она — корень, а глубина всех ее детей равна $$$1$$$.
Какую минимальную высоту дерева можно получить?
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le n - 1$$$) — количество вершин в дереве и наибольшее количество операций, которые вы можете совершить.
Во второй строке записаны $$$n-1$$$ целых чисел $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i < i$$$) — родитель $$$i$$$-й вершины. Вершина $$$1$$$ — корень.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
На каждый набор входных данных выведите одно число — наименьшая высота дерева, которую можно получить, совершив не более $$$k$$$ операций.
55 11 1 2 25 21 1 2 26 01 2 3 4 56 11 2 3 4 54 31 1 1
2 1 5 3 1
Название |
---|