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

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

Кто-нибудь знает, что такое алгоритм Хью? Первый и единственный раз встретил его в этом комментарии: http://codeforces.me/blog/entry/1797#comment-34432. Там говорится, что он умеет находить количества различных цветов во всех поддеревьях за линейное от размера дерева время. Очень интересно узнать как, ибо умею только за сложность DSU.

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

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

Насколько я понимаю, под алгоритмом за сложность DSU подразумевается:

  1. Отсортировать вершины в порядке обхода, для каждой вершины найти предыдущую и следующую того же цвета
  2. Найти LCA для найденных пар соседних вершин одного цвета
  3. Поставить +1 в каждую вершину и -1 в найденные LCA
  4. Сумма в поддереве = количество различных цветов

Если искать LCA за линию, получится алгоритм за линию.