Luogu P2633 Count on a tree

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
    int next, to;
}edge[A];
struct OO {
    int l, r, w;
}tree[A << 4];
int head[A], num_edge;
void add_edge(int from, int to) {
    edge[++num_edge].next = head[from];
    edge[num_edge].to = to;
    head[from] = num_edge;
}
vector<int> v;
int n, m, a[A], b[A], x, y, z, cnt, tot, k;
int siz[A], dep[A], fa[A], son[A], top[A], tp, dfn[A], pre[A], root[A << 4];
void prepare(int fr) {
    siz[fr] = 1;
    for (int i = head[fr]; i; i = edge[i].next) {
        int ca = edge[i].to;
        if (ca == fa[fr]) continue;
        fa[ca] = fr;
        dep[ca] = dep[fr] + 1;
        prepare(ca);
        siz[fr] += siz[ca];
        if (siz[ca] > siz[son[fr]]) son[fr] = ca;
    }
}
void dfs(int fr, int tp) {
    dfn[fr] = ++cnt, pre[cnt] = fr, top[fr] = tp;
    if (!son[fr]) return;
    dfs(son[fr], tp);
    for (int i = head[fr]; i; i = edge[i].next) {
        int ca = edge[i].to;
        if (ca == fa[fr] or ca == son[fr]) continue;
        dfs(ca, ca);
    }
}
int lca(int x, int y) {
    while (top[x] != top[y])
        if (dep[top[x]] >= dep[top[y]])
            x = fa[top[x]];
        else y = fa[top[y]];
    return dep[x] < dep[y] ? x : y;
}
void build(int &k, int l, int r) {
    k = ++tot;
    tree[k].w = 0;
    if (l == r) return;
    int m = (l + r) >> 1;
    build(tree[k].l, l, m);
    build(tree[k].r, m + 1, r);
}
void change(int l, int r, int &x, int &y, int k) {
    tree[++tot] = tree[y];
    tree[tot].w++;
    x = tot;
    if (l == r) return;
    int m = (l + r) >> 1;
    if (k <= m) change(l, m, tree[x].l, tree[y].l, k);
    else change(m + 1, r, tree[x].r, tree[y].r, k);
}
int query(int t1, int t2, int t3, int t4, int l, int r, int k) {
    if (l == r) return l;
    int m = (l + r) >> 1; //看要往哪邊走
    int xx = tree[tree[t2].l].w + tree[tree[t1].l].w - tree[tree[t3].l].w - tree[tree[t4].l].w;
    if (k <= xx) return query(tree[t1].l, tree[t2].l, tree[t3].l, tree[t4].l, l, m, k);
    else return query(tree[t1].r, tree[t2].r, tree[t3].r, tree[t4].r, m + 1, r, k - xx);
}
void open(int fr, int faa) { //沿用faa建自己
    change(1, v.size(), root[fr], root[faa], a[fr]);
    for (int i = head[fr]; i; i = edge[i].next) {
        int ca = edge[i].to;
        if (ca == fa[fr]) continue;
        open(ca, fr);
    }
}

int main(int argc, char const *argv[]) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    build(root[0], 1, v.size());
    for (int i = 1; i <= n; i++) a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &x, &y);
        add_edge(x, y);
        add_edge(y, x);
    }
    dep[1] = 1; prepare(1); dfs(1, 1);
    open(1, 0);
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &k); x ^= ans;
        int ll = lca(x, y);
        int xx = v[query(root[x], root[y], root[ll], root[fa[ll]], 1, v.size(), k) - 1];
        printf("%d\n", xx);
        ans = xx;
    }
}