# CF893F Subtree Minimum Query

• 67通过
• 195提交
• 题目来源
• 评测方式 RemoteJudge
• 标签 主席树
• 难度 NOI/NOI+/CTSC
• 时空限制 6000ms / 512MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

题目大意：

给你一颗有根树，点有权值，m次询问，每次问你某个点的子树中距离其不超过k的点的权值的最小值。（边权均为1，点权有可能重复，k值每次询问有可能不同，强制在线

真实询问计算方法：

x=(x′+lans)modn+1;

k=(k′+lans)modn;

数据范围： n<=100000,ai<=10^9,m<=1000000

## 题目描述

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

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。