← 返回题目列表

Codeforces · 893/F

F. 子树最小查询

中文机器翻译题面 查看原题

给你一棵由 n 个顶点组成的有根树。每个顶点上都写有一个数字;数字ai写在顶点i上。

让我们将 d(i, j) 表示为树中顶点 i 和 j 之间的距离(即从 i 到 j 的最短路径中的边数)。另外,我们将顶点 x 的 k 分块子树表示为顶点 y 的集合,这样这两个条件都满足:

- x 是 y 的祖先(每个顶点都是其自身的祖先);
- d(x, y) ≤ k。

您将获得 m 个对树的查询。第 i 个查询由两个数字 xi 和 ki 表示,该查询的答案是此类顶点 j 中 aj 的最小值,使得 j 属于 xi 的 ki 块子树。

编写一个程序来快速处理这些查询!

请注意,查询是以修改后的方式给出的。

输入

第一行包含两个整数 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 成为上一个查询的答案(如果i = 1,则为0)。那么 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

输出 #1

2
5