Problem - LCA Queries

Given a tree and $q$ queries, each asking for the LCA of two nodes $u$ and $v$.

Using Euler tour + Sparse Table:

• Preprocess: $O(n \log n)$
• Each query: $O(1)$

Alternative: Binary lifting gives $O(n \log n)$ preprocess, $O(\log n)$ query.

Better for smaller $q$, worse for large $q$. Constraints: $n$ up to $10^5$, $q$ up to $10^6$.