Subtree Minimum Query
Contest: Educational Codeforces Round 33 (Rated for Div. 2)
Difficulty rating: 2300
Tags: data structures, trees

You are given a rooted tree consisting of n vertices. Each vertex has a number written on it; number ai is written on vertex i.

Let's denote d(i, j) as the distance between vertices i and j in the tree (that is, the number of edges in the shortest path from i to j). Also let's denote the k-blocked subtree of vertex x as the set of vertices y such that both these conditions are met:

- x is an ancestor of y (every vertex is an ancestor of itself);
- d(x, y) ≤ k.

You are given m queries to the tree. i-th query is represented by two numbers xi and ki, and the answer to this query is the minimum value of aj among such vertices j such that j belongs to ki-blocked subtree of xi.

Write a program that would process these queries quickly!

Note that the queries are given in a modified way.

Input format:
The first line contains two integers n and r (1 ≤ r ≤ n ≤ 100000) — the number of vertices in the tree and the index of the root, respectively.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the numbers written on the vertices.

Then n - 1 lines follow, each containing two integers x and y (1 ≤ x, y ≤ n) and representing an edge between vertices x and y. It is guaranteed that these edges form a tree.

Next line contains one integer m (1 ≤ m ≤ 106) — the number of queries to process.

Then m lines follow, i-th line containing two numbers pi and qi, which can be used to restore i-th query (1 ≤ pi, qi ≤ n).

i-th query can be restored as follows:

Let last be the answer for previous query (or 0 if i = 1). Then xi = ((pi + last) mod n) + 1, and ki = (qi + last) mod n.

Output format:
Print m integers. i-th of them has to be equal to the answer to i-th query.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Example input:
5 2
1 3 2 3 5
2 3
5 1
3 4
4 1
2
1 2
2 3

Example output:
2
5

Editorial:
The main idea is to use a two-dimensional data structure: one dimension is depth of vertices, and other dimension is the time we entered a vertex during DFS.
Model solution uses sparse table for these purposes. First of all, let's renumerate the vertices so we can handle them easier. We run DFS from the root and then sort the vertices by their depth (and if depths are equal, by time we entered them in DFS). Then we renumerate vertices in this sorted order.
We need to denote some functions in order to continue:
• D(x) — depth of vertex x in the tree;
• tin(x) — the time we entered x during DFS;
• tout(x) — the time we left x during DFS.
For each depth we can store a sorted array of vertices belonging do this depth. This will allow us to build an auxiliary sparse table lf, where lf[i][x] is such vertex j that:
• D(j) = D(x) + 2i;
• tin(j) > tin(x);
• tin(j) is minimal among all vertices that meet first two conditions.
We also need a second sparse table rg, where rg[i][x] is j iff:
• D(j) = D(x) + 2i;
• tout(j) > tout(x);
• tout(j) is minimal among all vertices that meet first two conditions.
These sparse tables can be built using binary search in arrays we created for depths.
Okay, why do we need them? To create a third sparse table that will process the queries themselves:
table[i][j][x] — the minimum value of ay among vertices y such that y belongs to 2j-blocked subtree of some vertex with index included in [x, x + 2i). This table can be built backwards with the help of auxiliary tables.
So, how do we answer the queries? We need to look at the binary representation of k + 1 and do something like binary lifting (but descending the tree instead of ascending) and maintain the leftmost and the rightmost vertices on current depth which belong to the subtree we are interested in (and make queries to table on the segment between these two vertices).
This solution works in $${\mathcal {O}}(n\log ^{2}n+m\log n)$$, but, unfortunately (or fortunately to some participants), we made the time limit too high so the structures that require $${\mathcal {O}}(\log ^{2}n)$$ time to process each query, such as two-dimensional segment trees, might also get AC.