题解：P12393 「RiOI-6」flos

Register_int · 2025-05-01 18:24:04 · 题解

先考虑离线。把询问挂点上，可以直接对树进行搜索，维护出当前点 u 到根链上每个点除了 u 子树外的最深节点深度。设祖先 f 的深度为 d_f，树内最深节点到他的距离为 w_f，那么你要求的就是 \max_f(d_u-d_f+\min(t,w_f))。对值域开个线段树，\le t 的查最大的 w_f-d_f，>t 的查最大的 -d_f 即可。

发现上面这个过程是好在线的，你线段树换主席树就行了。时间复杂度 O(n\log n)。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;
const int inf = 0x3f3f3f3f;

struct node {
    int l, r, vx, vy;
    node(int l = 0, int r = 0, int vx = -inf, int vy = -inf)
        : l(l), r(r), vx(vx), vy(vy) {}
} t[MAXN << 6]; int n, m, op, rt[MAXN], cnt, last;

void modify(int &p, int pre, int k, int x, int l = 1, int r = n) {
    t[p = ++cnt] = t[pre];
    t[p].vx = max(t[p].vx, k - x), t[p].vy = max(t[p].vy, -x);
    if (l == r) return ; int mid = l + r >> 1;
    if (k <= mid) modify(t[p].l, t[pre].l, k, x, l, mid);
    else modify(t[p].r, t[pre].r, k, x, mid + 1, r);
}

int qx(int p, int ql, int qr, int l = 1, int r = n) {
    if (!p || ql > qr || r < ql || l > qr) return -inf;
    if (ql <= l && r <= qr) return t[p].vx; int mid = l + r >> 1;
    return max(qx(t[p].l, ql, qr, l, mid), qx(t[p].r, ql, qr, mid + 1, r));
}

int qy(int p, int ql, int qr, int l = 1, int r = n) {
    if (!p || ql > qr || r < ql || l > qr) return -inf;
    if (ql <= l && r <= qr) return t[p].vy; int mid = l + r >> 1;
    return max(qy(t[p].l, ql, qr, l, mid), qy(t[p].r, ql, qr, mid + 1, r));
}

vector<int> g[MAXN]; int dep[MAXN], d[MAXN], ans[MAXN];

multiset<int, greater<int>> s[MAXN];

void init(int u, int f) {
    dep[u] = dep[f] + 1;
    for (int v : g[u]) if (v != f) init(v, u), d[u] = max(d[u], d[v] + 1);
}

void dfs(int u, int f) {
    for (int v : g[u]) if (v != f) s[u].emplace(d[v]);
    for (int v : g[u]) {
        if (v == f) continue; s[u].erase(s[u].find(d[v]));
        modify(rt[v], rt[u], (s[u].empty() ? 0 : *s[u].begin() + 1), dep[u]);
        s[u].emplace(d[v]), dfs(v, u);
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &op);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        g[u].emplace_back(v), g[v].emplace_back(u);
    }
    init(1, 0), dfs(1, 0);
    for (int u, t; m--; ) {
        scanf("%d%d", &u, &t);
        if (op) u ^= last, t ^= last;
        int x = dep[u] + qx(rt[u], 1, t);
        int y = dep[u] + t + qy(rt[u], t + 1, n);
        printf("%d\n", last = max(min(d[u], t), max(x, y)));
    }
}