Задача №114056. Мозговая сеть (сложная)
Срочные новости из неврологии зомби! Оказывается — в отличие от того как считалось ранее — что каждый зомби рождён с одним мозгом, и только потом мозг развивается в сложную структуру. На деле, каждый раз когда зомби съедает один мозг, новый мозг появляется в его нервной систему и сразу соединяется с одним из уже существующих мозгов единственной мозговой связью. Было замечено, что интеллектуальные способности зомби сильно зависят от топологии нервной системы. Точнее, определим как расстояние между двумя мозгами \(u\) и \(v (1 ≤ u, v ≤ n)\) как минимальное количество мозговых соединений, которые потребуется использовать, чтобы передать мысль между этими двумя мозгами. Мозговая задержка зомби определяется как максимальное расстояние между какой-нибудь парой мозгов. Исследователи хотели бы отслеживать мозговую задержку после каждого такого изменения. Вам поставлена задача написать программу, которая по истории эволюции нервной системы конкретного зомби вычислит мозговую задержку на каждом шаге.
В первой строке входных данных записано число \(n\) — количество мозгов в финальной версии нервной системы зомби \(( 2 ≤ n ≤ 200 000 )\). Во второй строке дана история развития нервной системы зомби. Для удобства, мы пронумеруем мозги \(1, 2, ... n\) в порядке их добавления в нервную систему (зомби рождается с единственным мозгом с номером \(1\) , а добавляются мозги \(2, 3, ..., n\) ). Во второй строке записано \(n - 1\) целое число \(p_2 , p_3 , ..., p_n\) , означающее что после добавления мозга с номером \(k\) в нервную систему, он был соединён с родительским мозгом 
.
Выведите \(n - 1\) число — мозговую задержку после добавления мозга с номером \(k\) для \(k = 2, 3, ..., n\) .
Подзадача 1. \(n \le 150\) - 40 баллов
Подзадача 2. \(n \le 11000\) - 30 баллов
Подзадача 3. Нет дополнительных ограничений - 30 баллов.
2 1
1