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