您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

BZOJ 2588 Count on a Tree (COT)：可持久化線段樹解決樹上第 k 大查詢

編輯：C++ 入門

BZOJ 2588 Count on a Tree (COT)：可持久化線段樹解決樹上第 k 大查詢

題目要求在一棵帶點權的樹上，回答多次查詢：給定節點 u, v 與整數 k，求路徑 u → v 上第 k 大的點權值。N, Q ≤ 10^5，需 O((N+Q) log N) 算法。

核心思路：樹上差分 + 可持久化線段樹（Chairman Tree）

值域離散化：將所有點權排序去重，映射到 [1, N]；
DFS 構建版本樹：root[x] 表示從根節點到 x 的路徑上各權值出現次數的線段樹版本；
root[x] = update(root[fa[x]], 1, N, val[x])；
LCA 輔助：倍增法預處理 fa[x][j] 與 depth[x]，O(log N) 求 LCA；
查詢轉化：路徑 u→v 的權值多重集 = root[u] + root[v] - root[lca] - root[fa[lca]]；
在四棵線段樹上同時下降，利用左子樹計數判斷第 k 大落在左/右區間。

關鍵數據結構

struct Node {
    Node *ls, *rs;
    int cnt;
    Node(Node *l, Node *r, int c) : ls(l), rs(r), cnt(c) {}
    Node() : ls(nullptr), rs(nullptr), cnt(0) {}
} *root[MAXN], *null;

null = new Node(); null->ls = null->rs = null;  // 哨兵節點

核心函數

建樹（插入單個值）

Node* update(Node *pre, int l, int r, int pos) {
    if (l == r) return new Node(null, null, pre->cnt + 1);
    int mid = (l + r) >> 1;
    if (pos <= mid)
        return new Node(update(pre->ls, l, mid, pos), pre->rs, pre->cnt + 1);
    else
        return new Node(pre->ls, update(pre->rs, mid + 1, r, pos), pre->cnt + 1);
}

查詢第 k 大

int query(Node *u, Node *v, Node *lca, Node *plca, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int cnt = u->ls->cnt + v->ls->cnt - lca->ls->cnt - plca->ls->cnt;
    if (k <= cnt) return query(u->ls, v->ls, lca->ls, plca->ls, l, mid, k);
    else return query(u->rs, v->rs, lca->rs, plca->rs, mid + 1, r, k - cnt);
}

完整 AC 代碼框架

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
struct Node { Node *ls, *rs; int cnt; } *root[MAXN], *null;
int val[MAXN], rk[MAXN], fa[MAXN][20], dep[MAXN];
vector g[MAXN];
int N, Q;

void dfs(int u, int f) {
    fa[u][0] = f; dep[u] = dep[f] + 1;
    root[u] = update(root[f], 1, N, rk[u]);
    for (int v : g[u]) if (v != f) dfs(v, u);
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 19; ~i; --i) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    if (u == v) return u;
    for (int i = 19; ~i; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q;
    for (int i = 1; i <= N; ++i) cin >> val[i], rk[i] = val[i];
    sort(rk + 1, rk + N + 1);
    int M = unique(rk + 1, rk + N + 1) - rk - 1;
    for (int i = 1; i <= N; ++i)
        rk[i] = lower_bound(rk + 1, rk + M + 1, val[i]) - rk;

    for (int i = 1, u, v; i < N; ++i) {
        cin >> u >> v; g[u].push_back(v); g[v].push_back(u);
    }
    null = new Node(); null->ls = null->rs = null; null->cnt = 0;
    root[0] = null; dfs(1, 0);
    for (int j = 1; j < 20; ++j)
        for (int i = 1; i <= N; ++i) fa[i][j] = fa[fa[i][j-1]][j-1];

    int last = 0;
    while (Q--) {
        int u, v, k; cin >> u >> v >> k;
        u ^= last; v ^= last; k ^= last;          // 強制在線
        int p = lca(u, v);
        int ans = query(root[u], root[v], root[p], root[fa[p][0]], 1, M, k);
        cout << (last = val[ans]) << '\n';
    }
    return 0;
}