Funcia
Lv.4binary-liftinglcatree

Lowest Common Ancestor Queries

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A tree rooted at node 0 is given by parent (parent[0] = -1, and 0 <= parent[i] < i otherwise). For each query [u, v], return the lowest common ancestor of u and v (a node counts as its own ancestor).

Examples

parentqueriesresult
[-1, 0, 0, 1, 1, 2, 4][[3, 6], [5, 6], [4, 6], [2, 2]][1, 0, 4, 2]
[-1, 0, 1, 2][[3, 1], [0, 3]][1, 0]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(parent: int[], queries: int[][]) → int[]

Constraints

  • 1≤N=1 \le N = parent.length ≤200,000\le 200{,}000; parent[0] = -1, 0≤0 \le parent[i] <i< i
  • 1≤1 \le queries.length ≤200,000\le 200{,}000, 0≤u,v<N0 \le u, v < N

Expected complexity

Time
O((N + Q) log N)
Space
O(N log N)

Examples

parentqueriesExpected
[-1,0,0,1,1,2,4][[3,6],[5,6],[4,6],[2,2]][1,0,4,2]
[-1,0,1,2][[3,1],[0,3]][1,0]

Hint

Hint

Binary lifting: depths in index order (parents have smaller indices), up[k][v] = up[k-1][up[k-1][v]], lift the deeper node by the depth difference, then jump both while up[k][u] != up[k][v]. Climbing one step at a time is O(NQ)O(NQ) on deep trees.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)306 msestimated
C++ (GCC, gnu++23)306 msderived
Python 3.131318 msderived
Java 252140 msderived
Kotlin 2.4 (JVM)1612 msestimated
C# 14 (.NET 10)1612 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness408verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.