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

Question

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

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

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

Answer 1

Пусть 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)

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

Answer 2

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

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