| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
Всем привет! Недавно на, думаю, известном многим вам ресурсе habrahabr.ru была выложена статья про структуру данных, именуемую link-cut tree. Это первая известная мне русскоязычная статья на эту тему, ни на e-maxx'e, ни на вики-конспектах ИТМО, насколько мне известно, эта структура не описана, поэтому, считаю уместным сообщить о статье здесь.
Итак, собственно, статья.
Было бы круто, если кто-нибудь запилил бы (или нашел) учебную задачу, которую можно решить только с link-cut tree.
На летних сборах в Петрозаводске/Ижевске 2012 года (контест от ПетрГУ) была задача под названием "LCA Online", в которой link-cut trees были бы очень кстати. Задача примерно про то: есть корневое дерево, нужно уметь вырезать произвольное поддерево и подвешивать его под произвольную вершину, а также находить LCA для произвольных пар вершин.
Решить ее, конечно, можно и по-другому: Jokser написал там по моей идее очень жуткую гадость через сведение LCA к RMQ и поддержание "всего необходимого" с помощью дерамиды. Дебажили мы этот код потом весь вечер :).
Да ладно гадость. Это на контесте вдвоем спокойно пишется минут за 40.
Есть Лкшатская задача от Burunduk1. Правда кажется там запрос расстояния (если не вообще связности), поэтому оно тоже пробивается хранением эйлерова обхода. И оффлайн методы там не запрещены никак.
Нет, там был совсем не эйлеров обход дерева. Мы его тогда даже не вспомнили. А было вот это с динамическим поддержанием того самого массива, на котором делался RMQ — такое уже точно за 40 минут не пишется.
А насчет решения с эйлеровым обходом теперь уже согласен: совсем стандартная задача. Ну как: я это хорошо знаю теоретически, но никогда не писал и в ближайшее время не собираюсь.
"Тот самый массив, на котором делается RMQ" — это же и есть эйлеров обход, нет?
Какой же я тупой...
Да, это он и есть. Извиняюсь за то, что писал тут фигню.
У задачи J (про бинарное дерево поиска) с недавнего icl турнира одно из авторских решений было как раз через link-cut.
Появились такие за 6 лет?
https://www.e-olymp.com/ru/problems/2953