## 能够解决的题目类型这个 Trick 能解决的题目形如： - 给定 $n$ 个节点的**有根无边权有点权**树。 - 有 $m$ 个询问，每个询问形如点 $x$ 的**子树内**与 $x$ **深度差**不超过 $k$ 的点的极值/排名/和。 - $O(n\,log\,n)$ 可过。 ## 优缺点优点：可以强制在线，代码简单。缺点：可能被卡常（概率非常小）。 ## 思路首先，深度差不超过 $k$ 这个限制很难办，我们无法用一维的编号把这些点串起来，而且没有什么差分方法。那么——二维，启动！我们把一个数点 $x$ 变成二维平面上的点：$(depp_x\,,dfn_x)$。那么对于一个点 $p$ 的询问就变成了横坐标在 $[depp_p\,,depp_p+k]$ 中，纵坐标在 $[dfn_p\,,dfn_p+sz_p-1]$ 的点的极值/排名/和。这个显然可以用树套树，但是 $O(n\,log^2\,n)$，有没有更优的方法呢？我们考虑主席树，但是主席树必须满足**可减性**，而最值没有。 **但是，当一个点的横坐标在属于** $[1,depp_p-1]$ **时，他的纵坐标一定不属于** $[depp_p\,,dep_p+k]$，也就是说**我们并不需要将两颗线段树相减，那么询问也就不用讲满足可减性。** 所以我们就可以愉快地切题了。 ## 算法流程 1. 用一个 dfs 求出每个节点的 $dfn,sz,depp$。 2. 把节点按照深度排序，一个一个加入主席树，并记录**对于每个深度的最后一课主席树的根的下标** $idx$。 ## 例题代码本 Trick 的代码基本每道题没什么变化，直接套用就行了 [CF893F Subtree Minimum Query](https://www.luogu.com.cn/problem/CF893F) ```cpp #include using namespace std; #define midd ((node[u].l + node[u].r) >> 1) constexpr int maxn = 100010; int n, r, m, v[maxn], a, b, dfn[maxn], nowdfn, depp[maxn], s[maxn], idx[maxn], sz[maxn], lans, maxdep = 0; vector G[maxn]; struct nodee { int v, l, r, ls, rs; } ; struct tr { nodee node[maxn << 5]; int root[maxn], cnt; void build(int &u, int l, int r) { u = ++cnt; node[u] = {1000000000, l, r, 0, 0}; if (l == r) return ; build(node[u].ls, l, midd); build(node[u].rs, midd + 1, r); return ; } void update(int &u, int pree, int x, int k) { u = ++cnt; node[u] = node[pree]; node[u].v = min(node[u].v, k); if (node[u].l == node[u].r) return ; if (x <= midd) update(node[u].ls, node[pree].ls, x, k); else update(node[u].rs, node[pree].rs, x, k); return ; } int query(int u, int l, int r) { if (node[u].l >= l && node[u].r <= r) return node[u].v; int ress = 1000000000; if (l <= midd) ress = min(query(node[u].ls, l, r), ress); if (r > midd) ress = min(query(node[u].rs, l, r), ress); return ress; } } t; void dfs(int u, int fa) { sz[u] = 1; dfn[u] = ++nowdfn; for (int now : G[u]) { if (now == fa) continue; depp[now] = depp[u] + 1; maxdep = max(maxdep, depp[now]); dfs(now, u); sz[u] += sz[now]; } return ; } signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); cin >> n >> r; depp[r] = 1; for (int i = 1; i <= n; i++) { s[i] = i; cin >> v[i]; } for (int i = 1; i < n; i++) { cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } dfs(r, 0); sort(s + 1, s + 1 + n, [](int a, int b){return depp[a] < depp[b];}); // 以上为第一部分 dfs t.build(t.root[0], 1, n); idx[0] = t.root[0]; for (int i = 1; i <= n; i++) { t.update(t.root[i], t.root[i - 1], dfn[s[i]], v[s[i]]); if (depp[s[i]] != depp[s[i + 1]]) idx[depp[s[i]]] = i; } // 以上为第二部分主席树预处理 cin >> m; while (m--) { cin >> a >> b; a = (a + lans) % n + 1; b = (b + lans) % n; lans = t.query(t.root[idx[min(maxdep, depp[a] + b)]], dfn[a], dfn[a] + sz[a] - 1); cout << lans << '\n'; } return 0; } ```