Рассмотрим такую абстрактную задачу: дано корневое дерево, и у нас есть три вида запросов:
- Удалить какое-либо поддерево
- Добавить в дерево одиночную вершину, подвесив ее за произвольного предка
- Для двух вершин А и В сказать: является ли А предком В? (В оригинале нужно было искать LCA двух вершин)
Я слышал, что эта задача имеет простое и красивое решение (без дерамид и прочей мерзости). Может ли кто-нибудь им поделиться?
Да, собственно, и оригинал достаточно просто делается без всякой мерзости.
Нужно всего лишь знать массив предков на глубинах 1, 2, 4, ..., и глубину каждой вершины.
Запрос 1. Забиваем на этот запрос.
Запрос 2. Сохраняем глубину только что добавленной вершины. Пересчитываем массив предков для только что добавленной вершины за логарифм.
Запрос 3. Выясняем, какая из вершин глубже. Поднимаем ее до той высоты, на которой лежит другая — за логарифм. Затем поднимаем обе вершины одновременно, находя их LCA — тоже за логарифм.
Мне кажется, вопрос был задан в связи с задачей K с этой тренировки. Там нужна была дерамида, потому что надо было поддерживать порядок вершин при обходе в глубину.
И да, и нет. Как бы, писать дерамиду с целью определения порядкового номера не так мерзко, как реализовывать с помощью нее LCA, поэтому я и абстрагировался от оригинальной задачи.
Не нужна дерамида. Там совсем простое решение. Все, что нужно уметь, чтобы отвечать на запрос — искать лца и сортить вершины запроса по времени входа или выхода какого-нибудь дфса. Для первого, конечно, достаточно глубин и прыжков на степени двойки. Для второго, оказывается, тоже достаточно. Будем сортить со следующим компарером. Для двух вершин найдем их пре-лца — две вершины сразу под лца — и сравним их идентификаторы. Все. Ну и отдельно придется в компарере рассмотреть случай, когда одна вершина — предок другой.
Это решение за O(N*log^2(N)), мы это писали на контесте и получали TLE.
На самом деле это был RE.
На разборе еще говорили, что решения за N*log^2(N) спокойно проходят.
Спасибо за инфу.
При добавлении вершины можно пересчитать ее предков как двоичном подъеме. При запросе для 2-х вершин, пусть B — более глубокая, тогда поднимем ее на разницу глубин. Если пришли в вершину A, значит A предок B.
И тебе.
В случае если удаляются ребра, а не вершины видимо все существенно хуже. Тогда задача тоже решается, но уже с использованием treap или еще чего-нибудь похуже (хотя лично я летом убедился, что Linking-Cutting Trees это просто, но мне почему-то не верят).
Что значит удаляются ребра? Не значит ли это удалить поддерево вершины с нижнего конца ребра?
Это значит, что поддерево потом можно подвесить в другое место или за другую вершину.