Problems Base course RU

The common folder

tree range queries precomputation version control contests

The repository of this site holds thousands of files arranged in folders. A comparison tool needs to find, for a pair of files, their nearest common folder quickly: the one that contains both, while none of its subfolders contains both at once. There are many pairs, and the folder tree does not change.

The tree is given by parents: node 1 is the root, and every other node v has a parent p_v < v. Nodes are both folders and files. One of the tests is the real source tree of this site (the folders app, lang, resources, routes and tests as of 16 October 2026, 4701 nodes), with nodes numbered in alphabetical order of their paths.

Input

The first line holds n (1 ≤ n ≤ 100,000). The second holds n − 1 numbers p₂, …, p_n (1 ≤ p_v < v); for n = 1 the line is empty. The third holds the number of questions q (1 ≤ q ≤ 50,000), followed by q lines with node numbers u and v.

Output

For each question, the number of the lowest common ancestor of nodes u and v: the deepest node that lies on the path from the root both to u and to v. A node counts as its own ancestor.

Examples

Example 1

Input

8
1 1 2 2 3 5 5
5
6 7
4 8
8 7
3 6
5 5

Output

Example 2

Input

Output

Limits

Time · Python: 6000 ms
Time · Go: 2000 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Climbing from both nodes towards the root until they meet is correct, but takes as many steps as the depth. Folders can be nested tens of thousands of levels deep, at least in the tests. The question about the tree has to be reduced to a question about an array.

2Hint 2

Walk the tree depth-first and write out the nodes in the order of the walk. Where in this record, between nodes u and v, do their common ancestor or its children turn up?

3The idea

A common ancestor is a range minimum. In an Euler tour a node is written down on entry and on each return from a child. Between the first appearances of u and v the tour passes through their common ancestor and does not climb above it, so the common ancestor is the shallowest node in that stretch of the record. The depths do not change, and the range minimum comes from a sparse table in O(1).

4Walkthrough

The Go solution is exactly that: an Euler tour without recursion (a stack of “node, next child” pairs), a record of length 2n − 1, the first appearance of each node, and a sparse table over positions of the record that compares depths.

The Python solution makes do with a record half as long: the order of entry into nodes, n positions. Let u ≠ v, with u entered earlier. All the nodes entered after u and no later than v lie in the subtree of the common ancestor w but are not w: w was entered before u. Among them is a child of w, the one through which the path to v goes (and if u is itself an ancestor of v, the child of u on the path to v). So the shallowest node of this stretch is a child of w, and the answer is its parent. The table stores pairs (depth, node) packed into one number depth·(n + 1) + node, and is built with calls to map(min, …).

4+Solution

5Complexity

The walk is O(n), the table O(n log n) time and memory, each question O(1). Climbing by parents is O(depth) per question: in the fourth test three chains of 33,333 nodes hang from the root, and the questions are about deep nodes from different chains, while in the fifth the tree is a single path of a hundred thousand nodes.

6Common mistakes

Climbing by parents. On the real tree of the site it is fast, as the depth there is under ten, but on long chains each question costs tens of thousands of steps.
A recursive depth-first walk. On a chain of a hundred thousand nodes Python’s recursion hits the depth limit, and in Go it eats the stack; an explicit stack is needed.
A range by last appearances. First appearances must be taken (or any, but then the stretch between them must still lie within the subtree of the common ancestor); in the shortened record of n positions the range must start at the position after u, otherwise the answer turns out to be u itself.
Forgetting u = v. A node is its own ancestor, and the answer is the node itself.

Algorithms behind it

DS Data structure Sparse table The minimum of any range in O(1) after O(n log n) preparation: two overlapping blocks of length 2^k. O(1) per query, O(n log n) to build 2 problems GRA Algorithm Lowest common ancestor The common ancestor of two tree vertices: binary lifting in O(log n), an Euler tour in O(1), Tarjan off-line. O(log n) per query 2 problems