Распределение Дерева
Дерево — одна из самых популярных структур данных в информатике. Хотя оно элегантно, его структура не соответствует современной архитектуре компьютеров. В текущей архитектуре память представляется в виде одномерного массива. Поскольку дерево не является одномерной структурой, это может негативно сказаться на эффективности кэша при размещении дерева в памяти. Доступ к данным происходит быстрее, если они находятся в кэше. Рассмотрим способ размещения узлов дерева, который обеспечивает высокую производительность кэша.
Мы определяем стоимость размещения для дерева следующим образом. Для простоты предположим, что память разделена на блоки, каждый из которых может содержать не более B узлов дерева. Когда мы обращаемся к данным в блоке, все данные этого блока загружаются в кэш, и последующие обращения к данным в этом блоке происходят быстрее. Стоимость доступа к узлу u после узла v равна 0, если u и v находятся в одном блоке, и 1 в противном случае. Изначально в кэше нет данных, и стоимость доступа к первому узлу всегда равна 1. Стоимость пути v_1, v_2, ..., v_n равна сумме стоимости при последовательном обращении к узлам v_1, v_2, ..., v_n. Для дерева стоимость размещения определяется как максимальная стоимость путей от корневого узла до каждого конечного узла.
Ниже приведены примеры размещения, когда B = 4 и узел 1 является корневым узлом (это соответствует дереву из третьего примера ввода). Каждая рамка представляет блок. Левая фигура показывает пример размещения с общей стоимостью 3. Это не оптимально, так как правый пример достигает оптимальной стоимости размещения 2.
Дано дерево, для каждого узла i в дереве вычислите минимальную стоимость размещения, если узел i является корневым узлом.
Входные данные
Входные данные содержат несколько тестов. Каждый тест начинается с строки, содержащей два целых числа N (1 ≤ N ≤ 100000) и B (1 ≤ B ≤ N), разделенных пробелом. Каждая из следующих N−1 строк содержит одно целое число. i-е число p_i (1 ≤ p_i ≤ i) указывает, что узел i+1 соединен с узлом p_i. Узлы пронумерованы от 1 до N.
Последний тестовый случай завершается строкой, содержащей два нуля.
Выходные данные
Для каждого теста выведите его номер. Затем выведите N строк. i-я строка должна содержать целое число, обозначающее минимальную стоимость размещения данного дерева, если узел i является корневым узлом.
Следуйте формату примера вывода.