Level Ancestor, Heavy-Light декомпозиция

Задача поиска предка на уровне (Level Ancestor Problem)

• Двоичные подъемы: O(log n) на запрос + O(N log N) предпосчет
• Лесенки: O(log n) на запрос + O(N) предпосчет
• Двоичные подъемы + Лесенки: O(1) на запрос + O(N log N) предпосчет
• Идея уменьшить число прыжковых вершин до O(N / log N)
• Микро-макро эвристика

Heavy-Light декомпозиция

• Поиск минимума на пути в дереве
• Статическая задача: двоичные подъемы
• Тяжелые и легкие ребра
• Разбиение на тяжелые пути
• Оценка $log(n)$ на число легких ребер
• Финальная оценка $log^2(n)$