query can be restored as follows:Let last be the answer for previous query (or 00 if i1 1). Then xi((pilast)modn)1 (( ) mod ) 1, and ki(qilast)modn ( ) mod .OutputPrint m integers. i-th of them has to be equal to the answer to i-th query.ExampleInput5 2 1 3 2 3 5 2 3 5 1 3 4 4 1 2 1 2 2 3Output2 5解题思路本题的每次询问相当于在以 x 为根的子树中求与 x 距离不超过 k 的节点权值的最小值。通过引入 DFS 序我们可以将树上的子树问题转化为序列上的区间问题。设节点 x 对应的 DFS 序区间为 [lx,rx][,]则合法节点 y 的 DFS 序需满足 lx≤ly≤rx≤≤。定义 dx 为节点 x 到根节点的距离由于 y 是 x 的后代两者间的距离即为深度差 dy−dx−因此距离不超过 k 等价于 dy−dx≤k−≤即 dy≤dxk≤。综上所求点集可表示为满足 lx≤ly≤rx≤≤ 且 dy≤dxk≤ 的节点 y 的集合。虽然题目要求强制在线处理查询但我们可以先考虑离线做法以寻求启发。在给定 x 和 k 时约束 dy≤dxk≤ 意味着合法节点 y 的深度不超过某一固定上界。因此我们只需在所有深度不超过 dxk 且 DFS 序落在 [lx,rx][,] 内的节点中寻找最小点权。如果对每个询问单独处理显然会超时但若允许离线我们可将询问按 dxk 升序排序并按此顺序处理。在处理当前询问前将深度不超过 dxk 的所有节点插入线段树插入位置为节点的 DFS 序值为其权值。此时线段树中恰好包含了所有深度不超过 dxk 的节点直接查询区间 [lx,rx][,] 的最小值即为该询问的答案。对于在线查询而言我们无法为每个询问重新构建线段树但如果能快速获取维护了深度不超过 dxk 的所有节点的线段树就能快速查询答案。一个自然的想法是直接保存每个深度对应的线段树这便引出了可持久化线段树的应用。由于深度为 d 的线段树是在深度为 d−1−1 的线段树基础上扩展而来我们只需在上一深度的历史版本上依次插入当前深度的节点即可构建出当前深度的版本。只需在处理询问前通过预处理构建可持久化线段树即可时间和空间复杂度均为 O(nlogn)(log⁡)。这种利用可持久化线段树扩展历史版本的思路与 G - Copy Query 相似。AC 代码如下时间复杂度为 O((nq)logn)(()log⁡)#include bits/stdc.h using namespace std; typedef long long LL; const int N 1e5 5, M N * 2; int a[N]; int h[N], e[M], ne[M], idx; int tin[N], tout[N], d[N]; int p[N]; struct Node { int l, r, mn; }tr[N * 35]; int root[N]; void add(int u, int v) { e[idx] v, ne[idx] h[u], h[u] idx; } void dfs(int u, int p) { tin[u] idx; d[u] d[p] 1; for (int i h[u]; i ! -1; i ne[i]) { int v e[i]; if (v p) continue; dfs(v, u); } tout[u] idx; } int modify(int u, int l, int r, int x, int c) { int v idx; tr[v] tr[u]; if (l r) { tr[v].mn c; } else { int mid l r 1; if (x mid) tr[v].l modify(tr[u].l, l, mid, x, c); else tr[v].r modify(tr[u].r, mid 1, r, x, c); tr[v].mn min(tr[tr[v].l].mn, tr[tr[v].r].mn); } return v; } int query(int u, int l, int r, int ql, int qr) { if (l ql r qr) return tr[u].mn; int mid l r 1; if (qr mid) return query(tr[u].l, l, mid, ql, qr); if (ql mid 1) return query(tr[u].r, mid 1, r, ql, qr); return min(query(tr[u].l, l, mid, ql, qr), query(tr[u].r, mid 1, r, ql, qr)); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; for (int i 1; i n; i) { cin a[i]; } memset(h, -1, sizeof(h)); for (int i 0; i n - 1; i) { int u, v; cin u v; add(u, v), add(v, u); } idx 0; dfs(m, 0); iota(p 1, p 1 n, 1); sort(p 1, p n 1, [](int i, int j) { return d[i] d[j]; }); idx 0; tr[0].mn 0x3f3f3f3f; for (int i 1; i n; i) { root[d[p[i]]] modify(root[d[p[i - 1]]], 1, n, tin[p[i]], a[p[i]]); } int ret 0; cin m; while (m--) { int x, k; cin x k; x (x ret) % n 1, k (k ret) % n; ret query(root[min(d[p[n]], d[x] k)], 1, n, tin[x], tout[x]); cout ret \n; } return 0; }对本题进一步扩展。假设每次查询的是在以 x 为根的子树中求与 x 距离至少为 lb 且不超过 ub 的节点权值最小值约束条件将变为 lx≤ly≤rx≤≤ 且 dxlb≤dy≤dxub≤≤。在强制在线的情况下上述的可持久化线段树做法不再适用可能需要用树套树来维护深度与 DFS 序的两维约束由于博主不了解这里暂不展开讨论。若允许离线处理则可使用 dsu on tree 来解决。具体而言先将询问按节点 x 分类分发到每个对应的节点。在 dfs 遍历树的过程中对于当前节点 x先求解其所有轻儿子的答案再求解重儿子的答案。此时利用线段树维护重儿子对应子树中各节点在其深度位置上的权值接着将轻儿子对应子树的节点也插入该线段树。最后对于当前节点 x 的所有询问直接在维护好