Subtree Minimum Query

题意翻译

题目大意： 给你一颗有根树，点有权值，$m$ 次询问，每次问你某个点的子树中距离其不超过 $k$ 的点的权值的最小值。（边权均为 $1$，点权有可能重复，$k$ 值每次询问有可能不同） **本题强制在线**，真实询问计算方法： $x =(x'+\text{lans})\bmod n + 1$； $k=(k'+\text{lans})\bmod n$。 其中 $\text{lans}$ 为上一次询问的答案，定义初始 $\text{lans} = 0$ 【数据范围】 对于 $100\%$ 的数据：$1\le n \le 10^5$，$1 \le a_i \le 10^9$，$1 \le m \le 10^6$

题目描述

You are given a rooted tree consisting of $ n $ vertices. Each vertex has a number written on it; number $ a_{i} $ 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 $ x_{i} $ and $ k_{i} $ , and the answer to this query is the minimum value of $ a_{j} $ among such vertices $ j $ such that $ j $ belongs to $ k_{i} $ -blocked subtree of $ x_{i} $ . Write a program that would process these queries quickly! Note that the queries are given in a modified way.

输入输出格式

输入格式

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 $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ) — 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<=10^{6} $ ) — the number of queries to process. Then $ m $ lines follow, $ i $ -th line containing two numbers $ p_{i} $ and $ q_{i} $ , which can be used to restore $ i $ -th query ( $ 1<=p_{i},q_{i}<=n $ ). $ i $ -th query can be restored as follows: Let $ last $ be the answer for previous query (or $ 0 $ if $ i=1 $ ). Then $ x_{i}=((p_{i}+last)modn)+1 $ , and $ k_{i}=(q_{i}+last)modn $ .

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

2
5

题意翻译

题目大意： 给你一颗有根树，点有权值，$m$ 次询问，每次问你某个点的子树中距离其不超过 $k$ 的点的权值的最小值。（边权均为 $1$，点权有可能重复，$k$ 值每次询问有可能不同） **本题强制在线**，真实询问计算方法： $x =(x'+\text{lans})\bmod n + 1$； $k=(k'+\text{lans})\bmod n$。 其中 $\text{lans}$ 为上一次询问的答案，定义初始 $\text{lans} = 0$ 【数据范围】 对于 $100\%$ 的数据：$1\le n \le 10^5$，$1 \le a_i \le 10^9$，$1 \le m \le 10^6$