Задачник Базовый курс EN

Описанный родственник

дерево разделяй и властвуй граф наука и физика

Каталог языков устроен как лес: у каждой семьи есть вершина, под ней подгруппы, под ними языки. Лингвисты одну за другой выпускают грамматики, и каждая отмечает вершину каталога. Между выпусками коллеги спрашивают: на каком расстоянии по дереву от данной вершины ближайшая отмеченная? Расстояние — число рёбер на пути по дереву; в другой семье искать нельзя.

Третий тест — дерево языков Glottolog 5.3: 12 208 вершин; отметки — 1937 языков с грамматикой больше 300 страниц, в случайном порядке, а между ними вопросы о случайных языках.

Вход

В первой строке n (1 ≤ n ≤ 5 · 10⁴). Во второй — n чисел p₁, …, p_n: родитель вершины v, или 0, если v — вершина семьи. Затем число сообщений q (1 ≤ q ≤ 5 · 10⁴) и q строк: 1 v — вершина v отмечена (повторная отметка ничего не меняет) или 2 v — вопрос.

Выход

На каждый вопрос — расстояние от v до ближайшей отмеченной вершины её дерева, 0 если отмечена сама v, или -1, если в её дереве отмеченных нет.

Примеры

Пример 1

Вход

7
0 1 1 2 2 3 3
7
2 4
1 7
2 4
2 6
1 5
2 4
2 1

Выход

Пример 2

Вход

6
0 1 1 0 4 0
6
1 2
2 3
2 5
1 5
2 4
2 6

Выход

2
-1
1
-1

Ограничения

Время · Python: 9500 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 9 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Один вопрос — обход в ширину от вершины до первой отметки. Сколько он стоит, если отметок пока мало и все далеко, как в четвёртом тесте, где отметка одна на конце цепочки из 50 000 вершин? А вопросов десятки тысяч.

2Подсказка 2

Возьмите вершину, после удаления которой все части дерева не больше половины. Любой путь из одной части в другую проходит через неё. Что, если запомнить в ней расстояние до ближайшей отмеченной и сделать то же в каждой части?

3Идея

Центроидная декомпозиция. У каждой вершины не больше log₂ n + 1 центроидов над ней, и для каждого записано расстояние. Каждый центроид c помнит best(c) — расстояние до ближайшей отмеченной вершины своего куска. Отметка v уменьшает best у центроидов v, вопрос берёт наименьшее dist(v, c) + best(c). Почему этого хватает, доказано в статье: ближайшая отмеченная вершина учитывается в первом центроиде, взятом на пути к ней.

4Разбор

Строим куски уровень за уровнем, без рекурсии: для каждого куска — обход, размеры поддеревьев, спуск в часть больше половины, пока такая есть, и обход в ширину от найденного центроида, который дописывает каждой вершине куска пару «центроид, расстояние». Центроид удаляется, его соседи начинают куски следующего уровня. У леса куски первого уровня — семьи. Пары удобно хранить двумя параллельными списками: так быстрее и в Python, и в Go.

4+Решение

5Сложность

Подготовка O(n log n): на каждом уровне обходы кусков вместе проходят каждую вершину не больше раза. Отметка и вопрос — O(log n). Памяти — O(n log n) пар, на деле на дереве языков около пяти на вершину.

6Типичные ошибки

Обход от вопроса. Это wrong.py. Ответы верные, но в четвёртом тесте отметка одна, на конце цепочки, а вопросы — о вершинах второй половины: каждый обходит десятки тысяч вершин, и времени не хватает.
Обход из отмеченных после каждой отметки. Тогда вопросы мгновенны, но отметок тысячи, и каждая стоит O(n).
Центр вместо центроида. Середина самого длинного пути делит дерево по длине, а не по числу вершин. У метлы из шестого теста центр — середина ручки, и после его удаления пучок с половиной ручки, три четверти вершин, остаётся в одной части: оценка log₂ n уровней больше не гарантирована.
Рекурсия в обходах и в самой декомпозиции упадёт на цепочке из 50 000 вершин.

Алгоритмы задачи

GRA Алгоритм Центроидная декомпозиция Делим дерево центроидами: log₂ n уровней, и ближайшая отмеченная вершина — за O(log n) после каждой отметки. O(log n) на отметку и на вопрос 1 задача GRA Алгоритм Поиск в ширину Обходит граф слоями и находит пути с наименьшим числом рёбер за O(V + E). O(V + E) 2 задачи