RE1~5,AC~6

//by olkieler
#include <bits/stdc++.h>
#define int long long
#define inf INT_MAX
#define N 1000005
using namespace std;
inline int r() {int x; cin >> x; return x;}
inline void w(int x) {cout << x << '\n';}
inline void W(int x) {cout << x << ' ';}
struct Edge {
    int next, pointer;
} edge[N << 1];
struct node {
    int l, r, lson, rson, sum;
} tree[N << 5];
int k, tot, dfn, cnt;
int a[N], b[N], head[N], son[N], hson[N], dep[N], fa[N], top[N], root[N];
inline void add(int u, int v) {
    edge[++ tot].next = v, 
    edge[tot].pointer = head[u], 
    head[u] = tot;
}
inline int nnode(int rt) {
    int to = ++ cnt;
    tree[to] = tree[rt];
    return to;
}
inline int update(int rt, int rk) {
    int to = nnode(rt);
    tree[to].sum ++;
    if (tree[to].l == tree[to].r) return to;
    int mid = tree[to].l + tree[to].r >> 1;
    if (rk <= mid) tree[to].lson = update(tree[to].lson, rk);
    else tree[to].rson = update(tree[to].rson, rk);
    return to;
}
inline void dfs1(int x, int f) {
    int pointer = lower_bound(b + 1, b + k + 1, a[x]) - b;
    root[x] = update(root[f], pointer);
    son[x] = 1, fa[x] = f, dep[x] = dep[f] + 1;
    for (int i = head[x]; i; i = edge[i].pointer) {
        int y = edge[i].next;
        if (y == f) continue;
        dfs1(y, x);
        son[x] += son[y];
        if (son[y] > son[hson[x]]) hson[x] = y;
    }
}
inline void dfs2(int x, int t) {
    top[x] = t;
    if (hson[x]) dfs2(hson[x], t);
    for (int i = head[x]; i; i = edge[i].pointer) {
        int y = edge[i].next;
        if (y == fa[x] || y == hson[x]) continue;
        dfs2(y, y);
    }
}
inline int build(int L, int R) {
    int to = ++ cnt;
    tree[to].l = L, tree[to].r = R;
    if (L == R) return to;
    int mid = L + R >> 1;
    tree[to].lson = build(L, mid), tree[to].rson = build(mid + 1, R);
    return to;
}
inline int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
inline int query(int rt1, int rt2, int rt3, int rt4, int rk) {
    if (tree[rt1].l == tree[rt1].r) return tree[rt1].l;
    int sum = tree[tree[rt1].lson].sum + tree[tree[rt2].lson].sum - tree[tree[rt3].lson].sum - tree[tree[rt4].lson].sum;
    if (sum >= rk) return query(tree[rt1].lson, tree[rt2].lson, tree[rt3].lson, tree[rt4].lson, rk);
    return query(tree[rt1].rson, tree[rt2].rson, tree[rt3].rson, tree[rt3].rson, rk - sum);
}
signed main() {
    // ios::sync_with_stdio(0); cin.tie(0);
    freopen("data.in", "r", stdin);
    freopen("mine.out", "w", stdout);
    int n = r(), m = r(), lans = 0;
    for (int i = 1; i <= n; i ++) a[i] = b[i] = r();
    sort(b + 1, b + n + 1);
    k = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i < n; i ++) {
        int u = r(), v = r();
        add(u, v), add(v, u);
    }
    root[0] = build(1, k), dfs1(1, 0), dfs2(1, 1);
    for (int i = 1; i <= m; i ++) {
        int u = r() ^ lans, v = r(), rk = r(), lca = LCA(u, v);
        w(lans = b[query(root[u], root[v], root[lca], root[fa[lca]], rk)]);
    }
    return 0;
}

拍出来了 hack 但是无从下手：

10 5
11 2 9 9 3 2 8 9 3 9 
2 4
10 2
8 5
2 3
6 2
3 5
3 9
3 1
5 7
8 1 3
8 10 1
1 7 1
10 4 1
1 10 3