不知道为什么，这个题一直有一个点过不去，本地测试会直接RE

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define int long long
const int N=1e6;
int tree[4*N];
int ls[4*N];
int rs[4*N];
int cnt=0;
int clone(int x){
    tree[++cnt]=tree[x];
    ls[cnt]=ls[x];
    rs[cnt]=rs[x];
    return cnt;
}
#define mid ((l+r)>>1)
void insert(int& root,int l,int r,int pos,int data){
    // cout<<l<<" "<<r<<endl;
    root=clone(root);
    if(l==r){
        tree[root]+=data;
        return;
    }
    if(pos<=mid)
        insert(ls[root],l,mid,pos,data);
    else insert(rs[root],mid+1,r,pos,data);
    tree[root]+=data;
}
int query(int a,int b,int c,int d,int l,int r,int rk){
    if(l==r)
        return l;
    int temp=tree[ls[a]]+tree[ls[b]]-tree[ls[c]]-tree[ls[d]];
    if(rk>temp)
        return query(rs[a],rs[b],rs[c],rs[d],mid+1,r,rk-temp);
    else return query(ls[a],ls[b],ls[c],ls[d],l,mid,rk);
}
struct side{
    int t,n;
}ss[N];
int head[N];
int now=0;
void add(int f,int t){
    ss[++now].t=t;
    ss[now].n=head[f];
    head[f]=now;
}
#define FOR(x) for(int nxt=head[x];nxt;nxt=ss[nxt].n)
#define TP ss[nxt].t
int n,m;
int a[N],siz[N],son[N],dep[N],fa[N],top[N];
int root[N];
const int M=2e6;
void dfs1(int x,int fat){
    siz[x]=1;
    dep[x]=dep[fat]+1;
    fa[x]=fat;
    root[x]=root[fat];
    insert(root[x],1,M,a[x],1);
    FOR(x){
        if(TP==fat)
            continue;
        dfs1(TP,x);
        siz[x]+=siz[TP];
        if(siz[TP]>siz[son[x]])
            son[x]=TP;
    }
}
void dfs2(int x){
    FOR(x){
        if(TP==son[x]){
            top[TP]=top[x],dfs2(TP);
        }else if(!top[TP]){
            top[TP]=TP,dfs2(TP);
        }
    }
}
void print(int root,int l,int r){
    if(l==r){
        if(tree[root]!=0)
            cout<<l<<":"<<tree[root]<<" ";
        return ;
    }
    print(ls[root],l,mid);
    print(rs[root],mid+1,r);
}
int ncnt=0;
void Print(int a,int b,int c,int d,int l,int r){
    if(l==r){
        int temp=tree[a]+tree[b]-tree[c]-tree[d];
        if(temp!=0)
            cout<<l<<":"<<temp<<":"<<ncnt<<" ";
        ncnt+=temp;
        return ;
    }
    Print(ls[a],ls[b],ls[c],ls[d],l,mid);
    Print(rs[a],rs[b],rs[c],rs[d],mid+1,r);
}
int lca(int x,int y){
    int tx=top[x],ty=top[y];
    while(tx!=ty){
        if(dep[tx]<dep[ty])
            swap(tx,ty),swap(x,y);
        x=fa[tx];
        tx=top[x];
    }
    if(dep[x]>dep[y])
        return y;
    else return x;
}
int read(){
    int x=0;char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x;
}
int t[N];
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        t[i]=a[i]=read();
    sort(t+1,t+1+n);
    int all=unique(t+1,t+1+n)-t-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(t+1,t+1+n,a[i])-t;
    for(int f,t,i=1;i<n;i++){
        cin>>f>>t;
        add(f,t);
        add(t,f);
    }
    dfs1(1,0);
    dfs2(1);
    int last=0;
    for(int l,r,x,i=1;i<=m;i++){
        l=read(),r=read(),x=read();
        l^=last;
        int g=lca(l,r); last=query(root[l],root[r],root[g],root[fa[g]],1,M,x);
        last=t[last];
        printf("%lld\n",last);
    }
}