Олимпиадный тренинг

Задача . F. Минимум в поддереве


Задача

Темы: Деревья Структуры данных *2300

Дано корневое дерево, состоящее из n вершин. В каждой вершине записано некоторое число: в i-й вершине — ai.

Определим расстояние между вершинами i и j в дереве — d(i, j) (количество ребер на кратчайшем пути из i в j). Также определим поддерево глубины k вершины x — набор вершин y такой, что выполняются следующие условия:

  • x является предком y (каждая вершина считается своим предком);
  • d(x, y) ≤ k.

Заданы m запросов к дереву. i-й запрос представляется двумя числами xi и ki. Ответ на запрос — минимальное значение aj среди таких вершин j, что j принадлежат поддереву глубины ki вершины xi.

Напишите программу, которая быстро обработает такие запросы.

Обратите внимание, что запросы подаются в особом виде.

Входные данные

В первой строке записаны два числа n и r (1 ≤ r ≤ n ≤ 100000) — количество вершин в дереве и номер корневой вершины, соответственно.

Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — числа, записанные в вершинах.

Затем идет n - 1 строка, в каждой записаны по два числа x и y (1 ≤ x, y ≤ n), представляющие ребро между вершинами x и y. Гарантируется, что данные ребра составляют дерево.

В следующей строке записано одно целое число m (1 ≤ m ≤ 106) — количество запросов, которые требуется обработать.

Затем идут m строк, в i-й записаны два целых числа pi и qi, которые используются для получения i-го запроса (1 ≤ pi, qi ≤ n).

i-й запрос получается следующим образом:

Пусть last — ответ на предыдущий запрос (или 0, если i = 1). Тогда xi = ((pi + last) mod n) + 1, и ki = (qi + last) mod n.

Выходные данные

Выведите m чисел. i-е из них должно быть ответом на i-й запрос.


Примеры
№Входные данныеВыходные данные
1 
5 2
1 3 2 3 5
2 3
5 1
3 4
4 1
2
1 2
2 3
 
2
5

time 6000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++5
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет