洛谷P2633 Count on a tree 主席樹

😊 | Powered By HeartFireY

Problem Description

給定一棵 ​ 個節點的樹，每個點有一個權值。有 ​ 個詢問，每次給你 ​ 你需要回答 ​ 和 這兩個節點間第

其中 是上一個詢問的答案，定義其初始為 ，即第一個詢問的

Problem Analysis

動态查詢樹上區間點權第小，且查詢之間具有關系，是以考慮建立主席樹維護區間資訊。

首先回顧主席樹維護線性區間第大/小時我們的處理思路：

對于全局區間第​​小時，我們建立全局權值線段樹，維護的區間和表示某點子樹中點的個數。那麼我們在尋找區間第​小時，隻需要左右二分尋找即可。而對于某個區間的第​小，一個樸素的方式便是我們每次都建立一顆線段樹，但顯然這樣是不明智的算法。那麼我們是如何查詢這個區間第小的呢？

對于這個維護的過程我們很容易聯想到字首和的概念，我們可以先離線建樹，對于每個點建立一棵主席樹，維護區間，那麼對于區間查詢時，我們隻需要查詢到區間和即可取得區間的資訊，實作區間查詢。

然後分析樣例，作出樣例所示的樹(假設以為根節點)：

那麼我們可以發現，對于樹上區間查詢，我們也可以利用類似于線性區間查詢的思路進行解決，但是由于樹的結構限制，我們把線性區間的字首和改為樹上字首和的形式：

下面我們來說明這個式子：

如上，從根節點到号節點的路徑+從根節點到号節點的路徑重複了兩次，那麼我們要減去重疊的資訊：對于根節點到交點父節點的資訊均重複兩次，到交點的資訊重複一次(因為交點在鍊上，需要保留一次資訊)，是以字首和形式便是。

#include <bits/stdc++.h>
#define id(x) (lower_bound(b + 1, b + le + 1, a[x]) - b)
#define rid(x) (b[x])
using namespace std;

const int N = 1e5 + 10;

int n, m, le, ans = 0, lastans = 0;
int a[N], b[N], f[N][19], dep[N];
vector<int> g[N];

struct node{ int sum, lc, rc; }tree[N << 5];
int root[N], cnt = 0;


void build(node &rt, int l, int r){
    rt.sum = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    build(tree[rt.lc = ++cnt], l, mid);
    build(tree[rt.rc = ++cnt], mid + 1, r);
}

inline void update(node pre, node &rt, int l, int r, int p){
    rt.sum = pre.sum + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    if(p <= mid) update(tree[pre.lc], tree[rt.lc = ++cnt], l, mid, p), rt.rc= pre.rc;
    else update(tree[pre.rc], tree[rt.rc = ++cnt], mid + 1, r, p), rt.lc = pre.lc;
}

inline int query(node u, node v, node lca, node lca_fa, int l, int r, int k){
    if(l == r) return l;
    int sum = tree[u.lc].sum + tree[v.lc].sum - tree[lca.lc].sum - tree[lca_fa.lc].sum;
    int mid = l + r >> 1;
    if(sum >= k) return query(tree[u.lc], tree[v.lc], tree[lca.lc], tree[lca_fa.lc], l, mid, k);
    return query(tree[u.rc], tree[v.rc], tree[lca.rc], tree[lca_fa.rc], mid + 1, r, k - sum);
}

inline void dfs(int u, int fa){
    update(tree[root[fa]], tree[root[u] = ++cnt], 1, le, id(u));
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for(register int i = 1; i <= 18; i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for(auto v : g[u]){
        if(v == fa) continue;
        dfs(v, u);
    }
}

inline int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(register int i = 18; i >= 0; i--)
        if(dep[f[u][i]] >= dep[v]) u = f[u][i];
    if(u == v) return u;
    for(register int i = 18; i >= 0; i--)
        if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}

inline int querypath(int u, int v, int k){
    int lcaa = lca(u, v);
    return rid(query(tree[root[u]], tree[root[v]], tree[root[lcaa]], tree[root[f[lcaa][0]]], 1, le, k));
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //freopen("stdin.in", "r", stdin);
    //freopen("stdout.out", "w", stdout);
    cin >> n >> m;
    for(register int i = 1; i <= n; i++){ cin >> a[i]; b[i] = a[i]; }
    for(register int i = 1, u, v; i < n; i++){
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    sort(b + 1, b + 1 + n);
    le = unique(b + 1, b + n + 1) - (b + 1);
    build(tree[root[0] = ++cnt], 1, le);
    dfs(1, 0);
    while(m--){
        int u, v, k; cin >> u >> v >> k;
        ans = querypath(u ^ lastans, v, k);
        cout << ans << endl;
        lastans = ans;
    }
    return 0;
}