Codeforces Round 253 (Div. 1) |
---|
Закончено |
Когда у Адама появляется корневое дерево (связный неориентированный граф без циклов), он сразу начинает его раскрашивать. Более формально, каждому ребру он сопоставляет некоторый цвет таким образом, чтобы выполнялись два условия:
Не все раскраски дерева нравятся Адаму одинаково. Рассмотрим путь от некоторой вершины до корня. Количество различных цветов на этом пути назовем стоимостью вершины. Стоимостью раскраски дерева будем называть максимальную стоимость среди всех вершин дерева. Помогите Адаму определить минимальную стоимость раскраски дерева.
Изначально дерево Адама состоит из одной вершины, которая имеет номер один и является корнем. За один ход Адам подвешивает к уже существующей вершине новую, которая получает номер, равный наименьшему положительному целому не занятому числу. После каждой операции вам нужно сообщать минимальную стоимость раскраски получившегося дерева.
В первой строке задано целое число n (1 ≤ n ≤ 106) — количество добавлений новых вершин. Во второй строке записано n чисел pi (1 ≤ pi ≤ i) — номера вершин, к которым подвешивают очередную вершину.
Выведите n целых чисел — минимальные стоимости раскраски дерева после каждого добавления.
11
1 1 1 3 4 4 7 3 7 6 6
1 1 1 1 1 2 2 2 2 2 3
На картинке изображен один из возможных вариантов раскраски дерева из примера в самый последний момент. Стоимость вершин с номерами 11 и 12 равна трем.
Название |
---|