Самая далёкая страница
По сайту можно ходить только по хлебным крошкам: со страницы — вверх, в её раздел, или вниз, в один из её подразделов. Страницы и разделы образуют дерево с корнем на главной. Для каждой страницы узнайте, сколько кликов от неё до самой далёкой страницы сайта.
Один из тестов — настоящее дерево адресов этого сайта: 8986 узлов, от главной до страниц разборов экзаменов.
Вход
В первой строке — n (1 ≤ n ≤ 100 000), страницы пронумерованы от 1 до n, главная — 1. Во второй — n − 1 чисел p2, …, pn: раздел, к которому относится страница i. Номер раздела не обязательно меньше номера страницы.
Выход
n чисел через пробел: для каждой страницы по порядку — число кликов до самой далёкой от неё страницы.
Примеры
Пример 1
7 1 1 2 2 3 6
3 4 3 5 5 4 5
Пример 2
5 1 2 3 4
4 3 2 3 4
Ограничения
- Время · Python
- 2000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Обход в ширину из каждой страницы даёт ответ, но это n обходов по n шагов — на дереве сайта уже восемьдесят миллионов. Можно ли получить ответ для ребёнка из ответа для родителя?
2Подсказка 2
Самый длинный путь из страницы v либо уходит вниз, в её раздел, либо сначала поднимается к родителю. Первое считается снизу вверх. Что нужно знать о родителе, чтобы посчитать второе?
3Подсказка 3
Поднявшись из c к родителю v, путь может пойти выше или вниз — в любую ветку v, кроме ветки самой c. Поэтому у v нужно помнить не одну самую глубокую ветку, а две.
4Идея
Перерасчёт с корня в два прохода. Снизу вверх для каждой страницы v считаем d1[v] и d2[v] — глубины двух самых глубоких веток через разных детей — и запоминаем, через какого ребёнка идёт первая. Сверху вниз считаем up[c] — самый длинный путь из c, который начинается шагом вверх: up[c] = 1 + max(up[v], лучшая ветка v не через c), где лучшая ветка — d1[v], а если она идёт через c, то d2[v]. Ответ для страницы — max(d1, up).
5Разбор
Порядок обхода в ширину от главной даёт родителей раньше детей: проход снизу вверх идёт по нему задом наперёд, проход сверху вниз — вперёд. Номера разделов во входе не обязательно меньше номеров страниц, поэтому полагаться на порядок номеров нельзя — порядок нужно построить. Рекурсии нет, и цепочка из ста тысяч страниц не страшна.
Почему двух веток достаточно: путь из c через родителя не может вернуться в ветку c — в дереве нет циклов, и он прошёл бы по ребру c–v дважды. Значит, из всех веток v ему доступны все, кроме одной, и лучшая из доступных — либо первая, либо вторая по глубине.
На дереве этого сайта у главной ответ 6 — столько кликов до самых глубоких английских страниц. У самых глубоких страниц — разборов экзаменов — ответ 11: самые далёкие от них — такие же разборы на другом языке.
5+Решение
6Сложность
O(n) времени и памяти: два прохода по списку, на каждую страницу — константа действий.
7Типичные ошибки
- Обход из каждой страницы. Верно, но квадратично: не успевает уже на дереве сайта.
- Только одна лучшая ветка у родителя. Если она идёт через саму c, путь «вверх и обратно вниз» посчитается по ребру дважды, и ответ получится больше настоящего.
- Только вниз. d1[v] — ответ лишь для главной; у остальных самая далёкая страница часто лежит в чужом разделе.