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

Статья про link-cut tree на Хабрахабре
Автор adamant, 11 лет назад, По-русски

Всем привет! Недавно на, думаю, известном многим вам ресурсе habrahabr.ru была выложена статья про структуру данных, именуемую link-cut tree. Это первая известная мне русскоязычная статья на эту тему, ни на e-maxx'e, ни на вики-конспектах ИТМО, насколько мне известно, эта структура не описана, поэтому, считаю уместным сообщить о статье здесь.

Итак, собственно, статья.

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

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

Было бы круто, если кто-нибудь запилил бы (или нашел) учебную задачу, которую можно решить только с link-cut tree.

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

    На летних сборах в Петрозаводске/Ижевске 2012 года (контест от ПетрГУ) была задача под названием "LCA Online", в которой link-cut trees были бы очень кстати. Задача примерно про то: есть корневое дерево, нужно уметь вырезать произвольное поддерево и подвешивать его под произвольную вершину, а также находить LCA для произвольных пар вершин.

    Решить ее, конечно, можно и по-другому: Jokser написал там по моей идее очень жуткую гадость через сведение LCA к RMQ и поддержание "всего необходимого" с помощью дерамиды. Дебажили мы этот код потом весь вечер :).

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

      Да ладно гадость. Это на контесте вдвоем спокойно пишется минут за 40.

      Есть Лкшатская задача от Burunduk1. Правда кажется там запрос расстояния (если не вообще связности), поэтому оно тоже пробивается хранением эйлерова обхода. И оффлайн методы там не запрещены никак.

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

        Нет, там был совсем не эйлеров обход дерева. Мы его тогда даже не вспомнили. А было вот это с динамическим поддержанием того самого массива, на котором делался RMQ — такое уже точно за 40 минут не пишется.

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

        → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +30 Проголосовать: не нравится

          "Тот самый массив, на котором делается RMQ" — это же и есть эйлеров обход, нет?

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

            Какой же я тупой...

            Да, это он и есть. Извиняюсь за то, что писал тут фигню.

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

    У задачи J (про бинарное дерево поиска) с недавнего icl турнира одно из авторских решений было как раз через link-cut.

    → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    Появились такие за 6 лет?

    → Ответить