RT，强制在线，应该是答案有问题

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int n,m,cnt,f[2000002][30],dep[2000002],head[2000002];
int tot,L[5000002],R[5000002],rt[5000002],sum[5000002],son[5000002][2];

struct node{
	int id,rk,val;
}a[2000002];

bool cmp(node x,node y) {
	return x.val<y.val;
}

bool cmp2(node x,node y) {
	return x.id<y.id;
}

struct edge{
	int to,nxt;
}e[5000002];

void addedge(int A,int B) {
	e[++cnt].to=B;
	e[cnt].nxt=head[A];
	head[A]=cnt;
}

int Lca(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--) 
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=20;i>=0;i--) 
		if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}

int Update(int num,int l,int r,int x) {
	int nw=++tot;
	L[nw]=L[num],R[nw]=R[num],sum[nw]=sum[num]+1;
	if(l==r) return nw;
	int mid=(l+r)/2;
	if(x<=mid) L[nw]=Update(L[nw],l,mid,x);
	else R[nw]=Update(R[nw],mid+1,r,x);
	return nw;
}

int Query(int u,int v,int lca,int flca,int l,int r,int x) {
	if(l==r) return l;
	int mid=(l+r)/2,res=sum[L[u]]+sum[L[v]]-sum[L[lca]]-sum[L[flca]];
	if(x<=res) return Query(L[u],L[v],L[lca],L[flca],1,mid,x);
	return Query(R[u],R[v],R[lca],R[flca],mid+1,r,x-res);
}

void dfs(int u,int fa) {
	rt[u]=Update(rt[fa],1,n,a[u].rk);
	dep[u]=dep[fa]+1,f[u][0]=fa;
	for(int i=0;i<20;i++) f[u][i+1]=f[f[u][i]][i];
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
	}
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].id=i;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) a[i].rk=i;
	sort(a+1,a+n+1,cmp2);
	for(int i=1;i<n;i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(u,v),addedge(v,u);
	}
	dfs(1,0);
	int last=0;
	sort(a+1,a+n+1,cmp);
	while(m--) {
		int u,v,k;
		scanf("%d%d%d",&u,&v,&k);
		u^=last;
		int lca=Lca(u,v);
		last=a[Query(rt[u],rt[v],rt[lca],rt[f[lca][0]],1,n,k)].val;
		printf("%d\n",last);
	}
	return 0;
}

/kk