rt，救救孩子，调了一年了/wq

2、3、4测点 RE 了，1、5过了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
	int ss=0,ww=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			ww=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		ss=ss*10+ch-'0';
		ch=getchar();
	}
	return ss*ww;
}
const int N=1000010;
int n,m;
int a[N],b[N];
int root[N],tot;
struct ST{
	int ls;
	int rs;
	int dat;
}st[N*40];
int head[N],to[N*2],nex[N*2],cnt;
void add(int x,int y){
	cnt++;
	to[cnt]=y;
	nex[cnt]=head[x];
	head[x]=cnt;
}
int fa[N],dep[N],tp[N],sz[N],son[N];
int ct;
int build(int l,int r){
	tot++;
	int q=tot;
	if(l==r)
		return q;
	int mid=(l+r)/2;
	st[q].ls=build(l,mid);
	st[q].rs=build(mid+1,r);
	return q;
}
int add(int p,int l,int r,int x){
	tot++;
	int q=tot;
	st[q].dat=st[p].dat;
	if(l==r){
		st[q].dat++;
		return q;
	}
	int mid=(l+r)/2;
	if(mid>=x){
		st[q].rs=st[p].rs;
		st[q].ls=add(st[p].ls,l,mid,x);
	}
	else{
		st[q].ls=st[p].ls;
		st[q].rs=add(st[p].rs,mid+1,r,x);
	}
	st[q].dat=st[st[q].ls].dat+st[st[q].rs].dat;
	return q;
}
void dfs1(int x,int f){
	fa[x]=f;
	dep[x]=dep[f]+1;
	sz[x]=1;
	int maxn=-1;
	for(int i=head[x];i;i=nex[i]){
		int y=to[i];
		if(y==f)
			continue;
		dfs1(y,x);
		sz[x]+=sz[y];
		if(sz[y]>maxn){
			maxn=sz[y];
			son[x]=y;
		}
	}
}
void dfs2(int x,int top){
	tp[x]=top;
	if(son[x])
		dfs2(son[x],top);
	for(int i=head[x];i;i=nex[i]){
		int y=to[i];
		if(y==fa[x]||y==son[x])
			continue;
		dfs2(y,y);
	}
}
void dfs3(int x){
	int t=lower_bound(a+1,a+ct+1,b[x])-a;
	root[x]=add(root[fa[x]],1,n,t);
	for(int i=head[x];i;i=nex[i]){
 		int y=to[i];
		if(y==fa[x])
			continue;
		dfs3(y);
	}
}
int LCA(int x,int y){
	while(tp[x]!=tp[y]){
		if(dep[tp[x]]<dep[tp[y]])
			swap(x,y);
		x=fa[tp[x]];
	}
	if(dep[x]<dep[y])
		return x;
	return y;
}
int ask(int x,int y,int z,int w,int l,int r,int k){
	if(l==r)
		return l;
	int mid=(l+r)/2;
	int CNT=st[st[x].ls].dat+st[st[y].ls].dat-st[st[z].ls].dat-st[st[w].ls].dat;
	if(CNT>=k)
		return ask(st[x].ls,st[y].ls,st[z].ls,st[w].ls,l,mid,k);
	else
		return ask(st[x].rs,st[y].rs,st[z].rs,st[w].rs,mid+1,r,k-CNT);
}
signed main(){
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	n=read();
	m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		b[i]=a[i];
	}
	sort(a+1,a+n+1);
	ct=unique(a+1,a+n+1)-(a+1);
	for(int i=1;i<n;i++){
		int x,y;
		x=read();
		y=read();
		add(x,y);
		add(y,x);
	}
	dfs1(1,1);
	dfs2(1,1);
	root[0]=build(1,ct);
	fa[1]=0;
	dfs3(1);
	int last=0;
	for(int i=1;i<=m;i++){
		int x,y,k;
		x=read();
		y=read();
		k=read();
		x=(x^last);
		int lca=LCA(x,y);
		last=a[ask(root[x],root[y],root[lca],root[fa[lca]],1,ct,k)];
		printf("%lld\n",last);
	}
	return 0;
}