Блог пользователя AlexanderBolshakov

Автор AlexanderBolshakov, 12 лет назад, По-русски

Рассмотрим такую абстрактную задачу: дано корневое дерево, и у нас есть три вида запросов:

  1. Удалить какое-либо поддерево
  2. Добавить в дерево одиночную вершину, подвесив ее за произвольного предка
  3. Для двух вершин А и В сказать: является ли А предком В? (В оригинале нужно было искать LCA двух вершин)

Я слышал, что эта задача имеет простое и красивое решение (без дерамид и прочей мерзости). Может ли кто-нибудь им поделиться?

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Да, собственно, и оригинал достаточно просто делается без всякой мерзости.
Нужно всего лишь знать массив предков на глубинах 1, 2, 4, ..., и глубину каждой вершины.

Запрос 1. Забиваем на этот запрос.
Запрос 2. Сохраняем глубину только что добавленной вершины. Пересчитываем массив предков для только что добавленной вершины за логарифм.
Запрос 3. Выясняем, какая из вершин глубже. Поднимаем ее до той высоты, на которой лежит другая — за логарифм. Затем поднимаем обе вершины одновременно, находя их LCA — тоже за логарифм.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Мне кажется, вопрос был задан в связи с задачей K с этой тренировки. Там нужна была дерамида, потому что надо было поддерживать порядок вершин при обходе в глубину.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      И да, и нет. Как бы, писать дерамиду с целью определения порядкового номера не так мерзко, как реализовывать с помощью нее LCA, поэтому я и абстрагировался от оригинальной задачи.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Не нужна дерамида. Там совсем простое решение. Все, что нужно уметь, чтобы отвечать на запрос — искать лца и сортить вершины запроса по времени входа или выхода какого-нибудь дфса. Для первого, конечно, достаточно глубин и прыжков на степени двойки. Для второго, оказывается, тоже достаточно. Будем сортить со следующим компарером. Для двух вершин найдем их пре-лца — две вершины сразу под лца — и сравним их идентификаторы. Все. Ну и отдельно придется в компарере рассмотреть случай, когда одна вершина — предок другой.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Это решение за O(N*log^2(N)), мы это писали на контесте и получали TLE.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

          На самом деле это был RE.

          На разборе еще говорили, что решения за N*log^2(N) спокойно проходят.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо за инфу.

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

При добавлении вершины можно пересчитать ее предков как двоичном подъеме. При запросе для 2-х вершин, пусть B — более глубокая, тогда поднимем ее на разницу глубин. Если пришли в вершину A, значит A предок B.

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

В случае если удаляются ребра, а не вершины видимо все существенно хуже. Тогда задача тоже решается, но уже с использованием treap или еще чего-нибудь похуже (хотя лично я летом убедился, что Linking-Cutting Trees это просто, но мне почему-то не верят).

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Что значит удаляются ребра? Не значит ли это удалить поддерево вершины с нижнего конца ребра?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Это значит, что поддерево потом можно подвесить в другое место или за другую вершину.