## Fast LCA

View as PDF

Points: 12
Time limit: 2.0s
Memory limit: 40M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Recently, Angie's math teacher began teaching the class about trees (the graph theory kind, of course). As homework, he gave everyone a rooted tree of nodes (the root node is ) and asked them to do LCA queries on the tree (each query is in the form x y, and its answer is the LCA of nodes and in the tree). Since he didn't have the funds to make proper test data for his trees, he generated them randomly with the following algorithm: for every node , he picked a uniform random integer in the range to be its parent node.

Angie is feeling very demotivated and doesn't want to do her work. Can you solve the queries for her?

for all

#### Input Specification

The first line contains the integers and .

The second line contains integers , the parents of nodes respectively. Note that node does not have a parent as it's the root node of the tree.

The next lines each contain a query of the form x y.

#### Output Specification

For each query, output its answer on a new line.

#### Sample Input

10 5
1 2 1 1 4 2 1 6 9
3 9
10 7
4 4
1 3
2 3

#### Sample Output

1
1
4
1
2

#### Explanation

The tree from the sample input: