CF893F Subtree Minimum Query

给定一棵有 $n$ 个顶点的有根树，每个顶点上写有一个数字，第 $i$ 个顶点上写有数字 $a_i$。 我们记 $d(i,j)$ 表示树上顶点 $i$ 和顶点 $j$ 之间的距离（即从 $i$ 到 $j$ 的最短路径上的边数）。我们将顶点 $x$ 的 $k$-阻塞子树定义为所有满足以下两个条件的顶点 $y$ 的集合： - $x$ 是 $y$ 的祖先（每个顶点都是自己的祖先）； - $d(x, y) \leq k$。 你需要处理 $m$ 个关于这棵树的查询。第 $i$ 个查询由两个数字 $x_i$ 和 $k_i$ 表示，查询的答案是所有属于 $x_i$ 的 $k_i$-阻塞子树的顶点 $j$ 所对应的 $a_j$ 中的最小值。 请你编写程序高效地处理这些查询！ 注意：查询的输入方式经过了变形。

第一行包含两个整数 $n$ 和 $r$（$1 \leq r \leq n \leq 100000$），分别表示树的节点数和根节点编号。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq 10^9$），表示每个顶点上的数字。 接下来 $n-1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n$），表示树中的一条边。保证这些边构成一棵树。 接下来一行包含一个整数 $m$（$1 \leq m \leq 10^6$），表示查询的数量。 接下来的 $m$ 行，每行包含两个整数 $p_i$ 和 $q_i$（$1 \leq p_i, q_i \leq n$），可用于还原第 $i$ 个查询。 第 $i$ 个查询的还原方式如下： 令 $last$ 为上一个查询的答案（如果 $i=1$，则 $last=0$)。则 $x_i = ((p_i + last) \bmod n) + 1$，$k_i = (q_i + last) \bmod n$。

输出 $m$ 个整数，第 $i$ 个整数表示第 $i$ 个查询的答案。

由 ChatGPT 5 翻译