跑的很慢，差不多是n方的感觉，但写的明明是nlogn。

正确性确保正确。

求调

#include<bits/stdc++.h>
namespace IO{
	static const int buf_size=1000000;
	static unsigned char buf[buf_size];
	static int buf_len,buf_pos;
	bool isEOF(){
		if(buf_pos==buf_len){
			buf_pos=0;
			buf_len=fread(buf,1,buf_size,stdin);
			if(buf_pos==buf_len)return 1;
		}
		return 0;
	}
	char gc(){
		return isEOF()?EOF:buf[buf_pos++];
	}
	int rint(){
		int x=0;char c=gc();
		for(;c<48||c>57;c=gc());
		for(;c>=48&&c<=57;c=gc())
			x=(x<<1)+(x<<3)+(c^48);
		return x;
	}
	template<typename T>
	void read(T&x){x=rint();}
	template<typename T,typename...S>
	void read(T&x,S&...rest){read(x);read(rest...);}
}
using IO::read;
using namespace std;
const int N=1e5+1,M=2e5+1;
int n,nn,m,u,v,k,q[N],b[N],rt[N],bb,ans;
int s[N*21],lz[N*21],rz[N*21];
int sz[N],f[N],dep[N],zz[N],top[N];
int tot,head[N],nxt[M],to[M];
void add(int u,int v){
	nxt[++tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}
void dfs1(int u,int fa){
	f[u]=fa;
	sz[u]=1;
	dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==fa)continue;
		dfs1(v,u);
		sz[v]+=sz[u];
		if(sz[v]>sz[zz[u]])zz[u]=v;
	}
}
void dfs2(int u,int t){
	top[u]=t;
	if(zz[u])dfs2(zz[u],t);
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==f[u]||v==zz[u])continue;
		dfs2(v,v);
	}
}
int lca(int x,int y){
	for(;top[x]!=top[y];x=f[top[x]])
		if(dep[top[x]]<dep[top[y]])swap(x,y);
	if(dep[x]>dep[y])swap(x,y);
	return x;
}
int update(int pre,int l,int r,int v){
	int k=++bb;
	lz[k]=lz[pre];rz[k]=rz[pre];
	s[k]=s[pre]+1;
	int mid=(l+r)>>1;
	if(l<r){
		if(v<=mid)lz[k]=update(lz[pre],l,mid,v);
		else rz[k]=update(rz[pre],mid+1,r,v);
	}
	return k;
}
int query(int u,int v,int p,int pp,int l,int r,int k){
	if(l==r)return l;
	int mid=(l+r)>>1,x=s[lz[u]]+s[lz[v]]-s[lz[p]]-s[lz[pp]];
	if(x>=k)return query(lz[u],lz[v],lz[p],lz[pp],l,mid,k);
	else return query(rz[u],rz[v],rz[p],rz[pp],mid+1,r,k-x);
}
void dfs(int u){
	int x=lower_bound(b+1,b+nn+1,q[u])-b;
	rt[u]=update(rt[f[u]],1,nn,x);
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==f[u])continue;
		dfs(v);
	}
} 
int main(){
	read(n,m);
	for(int i=1;i<=n;++i){
		read(q[i]);
		b[i]=q[i];
	}
	sort(b+1,b+n+1);
	nn=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<n;++i){
		read(u,v);
		add(u,v);
		add(v,u);
	}
	dfs1(1,0);
	dfs2(1,1);
	dfs(1);
	for(int i=1;i<=m;++i){
		read(u,v,k);
		u^=ans;
		int p=lca(u,v);
		ans=b[query(rt[u],rt[v],rt[p],rt[f[p]],1,nn,k)];
		printf("%d\n",ans);
	}
	return 0;
}