Lv.4binary-liftinglcatree
Lowest Common Ancestor Queries
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 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
| parent | queries | result |
|---|---|---|
[-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
-
parent.length;parent[0] = -1,parent[i] -
queries.length,
Expected complexity
- Time
- O((N + Q) log N)
- Space
- O(N log N)
Examples
| parent | queries | Expected |
|---|---|---|
[-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 on deep trees.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 306 ms | estimated |
| C++ (GCC, gnu++23) | 306 ms | derived |
| Python 3.13 | 1318 ms | derived |
| Java 25 | 2140 ms | derived |
| Kotlin 2.4 (JVM) | 1612 ms | estimated |
| C# 14 (.NET 10) | 1612 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 8 | verdict only |
| performance | 60 | 4 | verdict only |