麻烦帮看一下，是一道主席树模板

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
long long n, m, last=0, cnt, a[N], b[N];
long long root[N], sum[N], ls[N], rs[N], node=0, new_node=0;
long long ans_sum[N], ans_ls[N], ans_rs[N];

struct edge{
    long long to, next;
}e[N<<2];
long long tmp=0, head[N];
void add(int u, int v){
    e[++tmp] = (edge){v, head[u]};
    head[u] = tmp;
}

int modify(int p, int l, int r, int pos){
    int np = ++node;
    sum[np] = sum[p]+1;
    if(l==r) return np;
    ls[np] = ls[p]; rs[np] = rs[p];
    int mid = l+r>>1;
    if(pos <= mid) ls[np] = modify(ls[p], l, mid, pos);
    else rs[np] = modify(rs[p], mid+1, r, pos);
    return np;
}

long long d[N], siz[N], fa[N], son[N];
void dfs1(int x, int f){
    d[x] = d[f]+1;
    fa[x] = f;
    siz[x] = 1;
    for(int i=head[x]; i; i=e[i].next){
        int y = e[i].to;
        if(y==fa[x]) continue;
        root[y] = modify(root[x], 1, cnt, a[y]);
        dfs1(y, x);
        siz[x] += siz[y];
        if(!son[x] || siz[y]>siz[son[x]])
            son[x] = y;
    }
}

long long number=0, top[N];
void dfs2(int x, int tp){
    top[x] = tp;
    if(!son[x]) return ;
    dfs2(son[x], tp);
    for(int i=head[x]; i; i=e[i].next){
        int y = e[i].to;
        if(y==fa[x] || y==son[x]) continue;
        dfs2(y, y);
    }
}

long long LCA(int x, int y){
   while(top[x] != top[y]){
      if(d[top[x]] < d[top[y]]) swap(x, y);
	  x = fa[top[x]];
   }
   return d[x]<d[y]?x:y;
}

long long query(int l, int r, int k, int u, int v, int lca, int fa){
    if(l==r) return l;
    long long mid = l+r>>1, ans;
    long long t=sum[ls[u]]-sum[ls[fa]]+sum[ls[v]]-sum[ls[lca]];
    if(t>=k) ans=query(l, mid, k, ls[u], ls[v], ls[lca], ls[fa]);
    else ans=query(mid+1, r, k-t, rs[u], rs[v], rs[lca], rs[fa]);
    return ans;
}
int main()
{
    freopen("P2633.in", "r", stdin);
    freopen("P2633.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%lld", b+i);
        a[i] = b[i];
    }
    sort(b+1, b+n+1);
    cnt = unique(b+1, b+n+1)-b-1;
    for(int i=1; i<=n; i++)
        a[i] = lower_bound(b+1, b+cnt+1, a[i])-b;
    for(int i=1; i<=n-1; i++){
        long long u, v;
        scanf("%lld%lld", &u, &v);
        add(u, v);
        add(v, u);
    }
    d[0]=0; sum[0]=0; ls[0]=0, rs[0]=0; root[0]=0;
    dfs1(1, 0);
    dfs2(1, 1);
    while(m--){    
        long long u, v, k;
        scanf("%lld%lld%lld", &u, &v, &k);
        u = u^last;
        long long lca = LCA(u, v);
        last = b[query(1, cnt, k, root[u], root[v], root[lca], root[fa[lca]])];
        cout << last << endl;
    }
    return 0;
}