（帮发）20pts球跳

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
#define int long long
int n,m,N;
class LCA
{
public:
	int dep[400005];
	int F[400005][25];
	vector<int> G[400005];
	LCA(){memset(F,0,sizeof F);memset(dep,0,sizeof dep);}
	void ST_create()
	{
		int k=log2(n);
		for(int j=1;j<=k;j++)
			for(int i=1;i<=n;i++)F[i][j]=F[F[i][j-1]][j-1];
	}
	int Lca(int x,int y)
	{
		if(dep[x]>dep[y])swap(x,y);
		int k=log2(n);
		while(k>=0)
		{
			if(dep[F[y][k]]>=dep[x])y=F[y][k];
			k--;
		}
		if(x==y)return x;
		k=log2(n);
		while(k>=0)
		{
			if(F[x][k]!=F[y][k])x=F[x][k],y=F[y][k];
			k--;
		}
		return F[x][0];
	}
};LCA Tr;
struct node
{
	int ls,rs;
	int sum;
}tree[2000005];
int rt[800005],idx=0;
int a[400005],Last=0;
vector<int> num;
void pushup(int id){tree[id].sum=tree[tree[id].ls].sum+tree[tree[id].rs].sum;}
void update(int &id,int xid,int l,int r,int x,int k)
{
	if(id==0)id=++idx;
	tree[id]=tree[xid];
	if(l==r){tree[id].sum+=k;return ;}
	int mid=(l+r)>>1;
	if(x<=mid)update(tree[id].ls,tree[xid].ls,l,mid,x,k);
	else update(tree[id].rs,tree[xid].rs,mid+1,r,x,k);
	pushup(id);
}
void bfs(int root)
{
    queue<int> q;
    q.push(root);
    rt[root]=0;
    Tr.dep[root]=1;
    Tr.F[root][0]=0;
    while(q.size())
	{
        int u=q.front();q.pop();
        int val=lower_bound(num.begin(),num.end(),a[u])-num.begin()+1;
        update(rt[u],rt[Tr.F[u][0]],1,N,val,1);
        for(int v:Tr.G[u])
		{
            if(v==Tr.F[u][0])continue;
            Tr.dep[v]=Tr.dep[u]+1;
            Tr.F[v][0]=u;
            q.push(v);
        }
    }
}
int query(int uid,int vid,int lid,int flid,int l,int r,int k)
{
	if(l==r)return l;
	int cnt=tree[tree[uid].ls].sum+tree[tree[vid].ls].sum-tree[tree[lid].ls].sum-tree[tree[flid].ls].sum;
	int mid=(l+r)>>1;
	if(k<=cnt)return query(tree[uid].ls,tree[vid].ls,tree[lid].ls,tree[flid].ls,l,mid,k);
	return query(tree[uid].rs,tree[vid].rs,tree[lid].rs,tree[flid].rs,mid+1,r,k-cnt);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);tree[0].ls=tree[0].rs=tree[0].sum=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],num.push_back(a[i]);
	sort(num.begin(),num.end());
	num.erase(unique(num.begin(),num.end()),num.end());
	N=num.size();
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		Tr.G[u].push_back(v);
		Tr.G[v].push_back(u);
	}
	bfs(1);Tr.ST_create();
	while(m--)
	{
		int u,v,k;
		cin>>u>>v>>k;u=u^Last;
		int lca=Tr.Lca(u,v);
		Last=query(rt[u],rt[v],rt[lca],rt[Tr.F[lca][0]],1,N,k);
		Last=num[Last-1];
		cout<<Last<<"\n";
	}
	return 0;
}