Кто-нибудь знает, что такое алгоритм Хью? Первый и единственный раз встретил его в этом комментарии: http://codeforces.net/blog/entry/1797#comment-34432. Там говорится, что он умеет находить количества различных цветов во всех поддеревьях за линейное от размера дерева время. Очень интересно узнать как, ибо умею только за сложность DSU.
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 7 | cnnfls_csy | 3569 |
| 9 | ecnerwala | 3494 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 158 |
| 4 | cry | 158 |
| 4 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | maroonrk | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 02.10.2024 17:32:57 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Насколько я понимаю, под алгоритмом за сложность DSU подразумевается:
Если искать LCA за линию, получится алгоритм за линию.
А как можно это искать кроме Ф.К.Б.?
Оффлайн — алгоритм Тарьяна, http://e-maxx.ru/algo/lca_linear_offline
если я правильно понял, человек хочет именно O(n), а не О(α(n) * n).
Его можно реализовать за линию, если использовать специализированное DSU (Gabow, Tarjan "A linear-time algorithm for a special case of disjoint set union").
забавно, никогда не слышал.