P28 · 1 second · 256 MB
LCA Queries
`parent` is an array of length `n`. `parent[0]` is `-1` (0 is the root). For `i > 0`, `parent[i]` is the parent of node `i`. `queries` is a list of `[u, v]` pairs. Return the lowest common ancestor of each pair. `lca(u,u)` is `u`. The parent pointers form a tree rooted at 0.
function lcaQueries(parent, queries) → number[]
CONSTRAINTS
- 1 ≤ parent.length ≤ 200
- parent[0] === -1
- 0 ≤ parent[i] < i for i > 0 (parents have smaller ids — a topological order)
- 0 ≤ queries.length ≤ 400
Input: parent = [-1, 0, 0, 1, 2], queries = [[3, 4], [3, 1], [3, 3]]
Output: [0, 1, 3]
Input: parent = [-1], queries = [[0, 0]]
Output: [0]
1
2
3
4
5
6
7
8
Arena judges JavaScript in a Web Worker (1s wall-clock, then TLE). Samples are public; submit runs hidden tests too. C++/Python is a later swarm package.