全RE，有离散化

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+10;
int n,m,last,tot,head[N<<1],fa[N<<1][22],dep[N*30],root[N*30],cnt,a[N*30],b[N*30];
struct node
{
	int to,next;
}edge[N<<1];
struct node2
{
	int ls,rs,data;
}t[N*30];
void read(int from,int to)
{
	tot++;
	edge[tot].to=to;
	edge[tot].next=head[from];
	head[from]=tot;
}
void dfs(int x,int fath)
{
	fa[x][0]=fath;
	for(int i=1;i<=18;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=head[x];i;i=edge[i].next)
	{
		int y=edge[i].to;
		if(y==fath)continue;
		dep[y]=dep[x]+1;
		dfs(y,x);
	}
}
int build(int l,int r)
{
	int p=++cnt;
	if(l==r)return p;
	int mid=l+r>>1;
	t[p].ls=build(l,mid);
	t[p].rs=build(mid+1,r);
	return p;
}
void pushup(int p)
{
	t[p].data=t[t[p].ls].data+t[t[p].rs].data;
}
int add(int now,int l,int r,int x,int k)
{
	int p=++cnt;
	t[p]=t[now];
	if(l==r)
	{
		t[p].data+=k;
		return p;
	}
	int mid=l+r>>1;
	if(x<=mid)t[p].ls=add(t[p].ls,l,mid,x,k);
	else t[p].rs=add(t[p].rs,mid+1,r,x,k);
	pushup(p);
	return p;
}
int lca(int x,int y)
{
	if(dep[x]>dep[y])swap(x,y);
	for(int i=18;i>=0;i--)
	{
		if(dep[fa[y][i]]>=dep[x])y=fa[y][i];
	}
	if(x==y)return x;
	for(int i=18;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}
int query(int p1,int p2,int p3,int p4,int l,int r,int x)
{
	if(l==r)return l;
	int mid=l+r>>1;
	int ret=t[t[p1].ls].data+t[t[p2].ls].data-t[t[p3].ls].data-t[t[p4].ls].data;
	if(x<=ret)return query(t[p1].ls,t[p2].ls,t[p3].ls,t[p4].ls,l,mid,x);
	else return query(t[p1].rs,t[p2].rs,t[p3].rs,t[p4].rs,mid+1,r,x-ret);
}
int ord[N];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		ord[i]=a[i];
	}
	sort(ord+1,ord+n+1);
	int lo=unique(ord+1,ord+n+1)-ord-1;
	for(int i=1;i<=n;i++)
	{
		int aa=a[i];
		a[i]=lower_bound(ord+1,ord+lo+1,a[i])-ord;
		b[a[i]]=aa;
		cout<<a[i]<<endl;
	}
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		read(x,y),read(y,x);
	}
	dep[1]=1;
	dfs(1,0);
	root[0]=build(1,n);
	for(int i=1;i<=n;i++)root[i]=add(root[fa[i][0]],1,n,a[i],1);
	for(int i=1;i<=m;i++)
	{
		int x,y,k;
		cin>>x>>y>>k;
		x^=last;
		int p=lca(x,y);
		last=query(root[x],root[y],root[p],root[fa[p][0]],1,n,k);
		last=b[last];
		cout<<last<<endl;
	}
	return 0;
}