Fast LCA

View as PDF

Submit solution

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 N nodes (the root node is 1) and asked them to do Q LCA queries on the tree (each query is in the form x y, and its answer is the LCA of nodes x and y 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 i (2 \le i \le N), he picked a uniform random integer in the range [1, i) 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?

Constraints

2 \le x, y \le N \le 6 \times 10^6

1 \le Q \le 10^6

1 \le p_i < i for all 2 \le i \le N

Input Specification

The first line contains the integers N and Q.

The second line contains N-1 integers p_2, p_3, \ldots, p_N, the parents of nodes 2, 3, \ldots, N respectively. Note that node 1 does not have a parent as it's the root node of the tree.

The next Q 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:

tree


Comments

There are no comments at the moment.