Dado un árbol con n nodos enraizado en el nodo 1, responde q consultas: ¿cuál es el ancestro común más bajo (LCA) de los nodos u y v?

El LCA de dos nodos u y v es el nodo más profundo que es ancestro de ambos simultáneamente.

Implementa la técnica de elevación binaria (binary lifting) para preprocesar el árbol en O(n log n) y responder cada consulta en O(log n).

Idea del algoritmo

1. Preprocesamiento: usando BFS desde la raíz, calcula la profundidad de cada nodo y su 2^k-ésimo ancestro para k = 0, 1, ..., ⌊log₂ n⌋.
2. Consulta LCA(u, v): iguala las profundidades subiendo el nodo más profundo con potencias de 2; luego sube ambos nodos simultáneamente hasta que coincidan justo por debajo del LCA.

Parámetros

• n — número de nodos (numerados del 1 al n)
• edges — aristas no dirigidas [u, v] que forman el árbol
• queries — pares [u, v] a consultar

Retorno

Array con el LCA de cada consulta, en el mismo orden.

Ejemplo

lca(7, [[1,2],[1,3],[2,4],[2,5],[3,6],[3,7]], [[4,5],[4,6],[5,7]])
// Árbol:        1
//              / \
//             2   3
//            / \ / \
//           4  5 6  7
//
// LCA(4,5) = 2, LCA(4,6) = 1, LCA(5,7) = 1
// → [2, 1, 1]

Restricciones

• 1 ≤ n ≤ 10⁵
• |edges| = n − 1
• 1 ≤ |queries| ≤ 10⁵
• 1 ≤ u, v ≤ n