Как найти самого низкого предка с нисходящим листовым узлом с некоторой меткой?

Question

Эта проблема

Дано корневое дерево с n узлами, где все листья помечены из набора меток. Создайте структуру данных, которая, учитывая листовой узел, a и метку l, может найти самого младшего предка u, a, где u имеет хотя бы одного потомка с меткой l.

Подход линейного пространства / линейного времени

• Начните с листа
• Изучите всех братьев и сестер
  • Если у брата есть метка, я найду наименьшего общего предка между а и этим братом.
  • В противном случае продолжайте к родителям
• Если все нисходящие от родителей листовые узлы не помечены буквой l, перейдите к бабушке и дедушке и проверьте их потомков.
• Продолжайте рекурсивную проверку бабушек и дедушек и их потомков, пока не будет найден потомок с меткой l.

Это имеет временную сложность O(n) и пространственную сложность O(n).

---

Есть ли более быстрый способ сделать это с линейной пространственной сложностью? Возможно, предварительно обработав дерево как-нибудь? l и a не зафиксированы, поэтому предварительная обработка должна быть гибкой.

Самый низкий общий предок может быть найден в постоянном времени, используя RMQ через Eulerian-Tour.

Имейте в виду, что дерево не сбалансировано и не отсортировано каким-либо образом.

Answer 1

Итак, теперь я нашел лучшее решение:

Идея заключается в следующем: чем больше двух узлов появляется на пути Эйлера, тем выше их LCA. Т.е. index(a) < index(b) < index(c) => dist_to_root(LCA(a, b)) >= dist_to_root(LCA(a, c)),

Это означает, что вам нужно только вычислить LCA a и первого узла после a с меткой l в пути, а LCA a и последнего узла перед a с меткой l в пути.

Один из них даст оптимальное решение проблемы.

Чтобы эффективно найти эти два индекса, создайте список индексов для каждой метки и выполните двоичный поиск в O (log n).

Сложность памяти O (n).

Answer 2

Вот решение с O(log(n)^3) временной сложностью и O(n log(n)) пространственной сложностью.

Позволять L быть списком меток, которые вы встретите на пути Эйлера. Вы строите дерево сегментов с этим списком и сохраняете в каждом узле дерева набор меток, появляющихся в соответствующем сегменте. Затем вы можете проверить время O(log(n)^2), появляется ли метка в поддереве с помощью запроса диапазона в дереве сегментов.

Чтобы найти правильного родителя, вы можете выполнить бинарный поиск. Например, что-то похожее на бинарный лифтинг. Который добавит еще один фактор log (n).