Олимпиадный тренинг

Задача . E. Деревья Пенчика и Хлои

Задача

Темы: Деревья дп жадные алгоритмы математика поиск в глубину и подобное реализация сортировки Структуры данных *2100

До отъезда Пенчика и Хлои в Сингапур оставалось всего несколько часов, и им не терпелось увидеть высоченные деревья в Сингапурском ботаническом саду! Пытаясь сдержать свое волнение, Пенчик смастерил дерево с корнями, чтобы занять Хлою и себя.

У Пенчика есть корневое дерево$^{\text{∗}}$, состоящее из $n$ вершин, пронумерованных от $1$ до $n$, с вершиной $1$ в качестве корня. Хлоя может выбрать целое неотрицательное число $d$, чтобы создать совершенное бинарное дерево$^{\text{†}}$ глубины $d$.

Поскольку Пенчик и Хлоя — хорошие друзья, Хлоя хочет, чтобы ее дерево было изоморфно$^{\text{‡}}$ дереву Пенчика. Чтобы достичь этого, Хлоя может выполнить следующую операцию над своим деревом любое количество раз:

Выбрать ребро $(u,v)$, где $u$ является родителем $v$.
Удалить вершину $v$ и все ребра, связанные с $v$, а затем соединить всех бывших детей $v$ непосредственно с $u$.

В частности, операция над ребром $(u, v)$, где $v$ — лист, удалит вершину $v$ без добавления новых ребер.

Поскольку построение совершенного бинарного дерева может занять много времени, Хлоя хочет выбрать минимальное $d$, такое, чтобы совершенное бинарное дерево глубины $d$ можно было сделать изоморфным дереву Пенчика с помощью вышеописанной операции. Обратите внимание, что Хлоя не может менять корни деревьев.

$^{\text{∗}}$Деревом называется связный граф без циклов. Корневым деревом называется дерево, в котором одна из вершин специальная и называется корнем. Родителем вершины $v$ называется первая вершина на простом пути от $v$ до корня. У корня нет родителя. Ребенком вершины $v$ называется любая вершина $u$, для которой $v$ является родителем. Листом называется любая вершина, у которой нет детей.

$^{\text{†}}$Полным бинарным деревом называется корневое дерево, в котором у каждой вершины $0$ или $2$ детей. Совершенное бинарное дерево — это полное бинарное дерево, в котором каждый лист находится на одинаковом расстоянии от корня. Глубина такого дерева равна расстоянию от корня до листа.

$^{\text{‡}}$Два дерева с корнями, равными $r_1$ и $r_2$ соответственно, считаются изоморфными, если существует такая перестановка вершин $p$, что ребро $(u, v)$ существует в первом дереве тогда и только тогда, когда ребро $(p_u, p_v)$ существует во втором дереве, и $p_{r_1} = r_2$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $t$ ($1 \le t \le 10^5$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $n$ ($2 \le n \le 10^6$) — количество вершин в дереве Пенчика.

Вторая строка каждого набора входных данных содержит $n-1$ целых чисел $p_2, p_3, \ldots, p_n$ ($1 \leq p_i \leq i-1$) — родитель вершины $i$.

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $10^6$.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке одно целое число: минимальную глубину совершенного бинарного дерева Хлои.

Примечание

В первом наборе входных данных можно создать совершенное бинарное дерево глубины $2$.

$\text{[math]}$

Рассмотрим выполнение операции на ребре $AC$. Рёбра $AC$, $CF$ и $CG$ удаляются, а рёбра $AF$ и $AG$ добавляются.

$\text{[math]}$

Полученное дерево изоморфно дереву, заданному на входе. Можно доказать, что никакая последовательность операций над бинарным деревом глубины менее $2$ не может привести к дереву, изоморфному дереву, заданному на входе.

Во втором наборе входных данных дерево уже изоморфно совершенному бинарному дереву глубины $3$.

Примеры

№	Входные данные	Выходные данные
1	5 6 1 2 2 1 1 15 1 1 2 2 3 3 4 4 5 5 6 6 7 7 5 1 2 2 2 7 1 1 2 1 1 2 10 1 1 1 2 2 2 4 3 3	2 3 3 3 3

time 3500 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет