Найти несколько LCA в некорневом дереве

Я пытаюсь реализовать LCA для некорневого дерева. Я дал дерево (связный неориентированный граф без циклов) и последовательность запросов о LCA для некоторого корня и двух вершин. Каждый конкретный запрос может иметь различный корень, поэтому я не могу использовать алгоритмы, которые предварительно обрабатывают дерево для произвольного корня в начале.

До сих пор я пытался найти пути от обеих вершин до корня с помощью DFS, а затем проверить, где он расходится, но его несколько медленный (O(nq), где q количество запросов).

Есть предложения, как предварительно обработать дерево, чтобы иметь сублинейную сложность запроса?

2 3
algorithm least-common-ancestor

2 ответа:

Пусть LCA (u, v, w) - LCA из v и w относительно корня u. чтобы вычислить LCA (u, v, w), мы можем вычислить для любого фиксированного r, 

LCA(r, u, v)
LCA(r, u, w)
LCA(r, v, w)

И возьмем "нечетного человека", то есть, если два равны, а третий отличается, то возьмем третьего, иначе они все равны, поэтому возьмем этот узел.

5

Возьмите произвольную вершину в качестве корня и предварительно обработайте дерево для LCA. Для каждого запроса (u,v) и r в качестве корня пусть w-LCA u и v в дереве.

  • Если w находится в поддереве r, то W-ответ.
  • Если r находится в поддереве w, то R-ответ.
  • Если r находится в поддереве u или v, то ответом является соответствующая вершина.
0