数据结构 Trick 之：子树 k 距离内问题

porse114514 · 2025-01-17 22:21:22 · 算法·理论

能够解决的题目类型

这个 Trick 能解决的题目形如：

给定 n 个节点的有根无边权有点权树。
有 m 个询问，每个询问形如点 x 的子树内与 x 深度差不超过 k 的点的极值/排名/和。
## 优缺点优点：可以强制在线，代码简单。缺点：可能被卡常（概率非常小）。 ## 思路首先，深度差不超过 $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]，也就是说我们并不需要将两颗线段树相减，那么询问也就不用讲满足可减性。

所以我们就可以愉快地切题了。

算法流程

用一个 dfs 求出每个节点的 dfn,sz,depp。
把节点按照深度排序，一个一个加入主席树，并记录对于每个深度的最后一课主席树的根的下标 idx。

例题代码

本 Trick 的代码基本每道题没什么变化，直接套用就行了 CF893F Subtree Minimum Query

#include <bits/stdc++.h>
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 <int> 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;
}