K Generations Up

Difficulty: 1800 4000 ms 128 MB

trees binary-lifting

A rooted tree (root 1) is given by parents. Answer Q queries: the K-th ancestor of node X, or −1 if it does not exist.

Input: the first line has N and Q; the next N−1 lines give the parent of nodes 2..N; the next Q lines each have X and K.

Output: one line per query.

Constraints:

• 2 ≤ N, Q ≤ 2×10⁵ (tests smaller)

Sample Tests

5 3
1
1
2
2
4 1
4 2
4 3

2
1
-1

2 1
1
2 5

1

Read the Editorial