说来惭愧，这么多天才a了一道题，怎比得上当时myc在二十分钟内就切了此题
正解就是dfs一遍，搞出主席树，然后每次lca完在主席树上询问,非常裸
//By Richard
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (int)(31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X)
#define debugout(X)
#endif
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
/////////////////////read4.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
template <typename T>
inline void read(T &x,T &y,T &z){read(x);read(y);read(z);}
/////////////////////graph///////////////////////////////
#ifdef graphv
const int maxn=,maxm=;
struct GRAPH
{
int next[maxm],first[maxn],to[maxm],value[maxm],cnt;
void addedge(int x,int y,int z){next[++cnt]=first[x];first[x]=cnt;to[cnt]=y;value[cnt]=z;}
void addedge2(int x,int y,int z){addedge(x,y,z);addedge(y,x,z);}
void addedge2(int x,int y,int z,int xx){addedge(x,y,z);addedge(y,x,xx);}
};
#endif
const int maxn=200001,maxm=200002;
/////////////////variables&functions////////////////////
int n,m,v[maxn],nn,vv[maxn];
map <int,int> mm;
struct node
{
node l,r;
int value;
node():l(0),r(0),value(0){}
node(node *ll,node *rr):l(ll),r(rr),value((l?l->value:0)+(r?r->value:0)){}
node(node *ll,node *rr,int vv):l(ll),r(rr),value(vv){}
node(int vv):l(0),r(0),value(vv){}
};
char ___[maxn30sizeof(node)];
char *=___;
inline void *myalloc(size_t size)
{
return (+=size)-size;
}
#define newnode new (myalloc(sizeof(node))) node
#define getll(x) (x?(x->l?x->l->value:0):0)
#define getl(x) (x?x->l:0)
#define getr(x) (x?x->r:0)
struct Chairman_Tree
{
node *root[maxn];
node *insert(node *x,int k,int L=1,int R=nn)
{
if (L==R) return newnode(x?x->value+1:1);
int mid=(L+R)>>1;
if (k<=mid) return newnode(insert(getl(x),k,L,mid),getr(x));
else return newnode(getl(x),insert(getr(x),k,mid+1,R));
}
int query(node *x,node *y,node *anc,node *ancc,int k,int L=1,int R=nn)
{
if (L==R) return L;
int mid=(L+R)>>1;
int ll=getll(x)+getll(y)-getll(anc)-getll(ancc);
if (k<=ll) return query(getl(x),getl(y),getl(anc),getl(ancc),k,L,mid);
else return query(getr(x),getr(y),getr(anc),getr(ancc),k-ll,mid+1,R);
}
int query(node *x,node *y,node *anc,int k,int L=1,int R=nn)
{
if (L==R) return L;
int mid=(L+R)>>1;
int ll=getll(x)+getll(y)-getll(anc);
if (k<=ll) return query(getl(x),getl(y),getl(anc),k,L,mid);
else return query(getr(x),getr(y),getr(anc),k-ll,mid+1,R);
}
inline int query(int x,int y,int anc,int ancc,int k)
{
if (anc!=ancc) return query(root[x],root[y],root[anc],root[ancc],k);
else return query(root[x],root[y],root[anc],k);
}
}seg;
struct TREE
{
int next[maxm],first[maxn],to[maxm],cnt,aa[maxm],cna,fa[maxn];
int rmq[maxm][21],ff[maxn],depth[maxn],rmqq[maxm][21];
void addedge(int x,int y){next[++cnt]=first[x];first[x]=cnt;to[cnt]=y;}
void addedge2(int x,int y){addedge(x,y);addedge(y,x);}
void dfs(int x,int previous,int step)
{
seg.root[x]=seg.insert(seg.root[previous],v[x]);
aa[++cna]=x;depth[x]=step;
if (!ff[x]) ff[x]=cna;
for (int q=first[x];q;q=next[q]) if (to[q]!=previous)
{
fa[to[q]]=x;
// seg.root[to[q]]=seg.insert(seg.root[x],v[x]);
dfs(to[q],x,step+1);
aa[++cna]=x;
}
}
void initrmq()
{
rep(i,1,cna)
{
rmq[i][0]=depth[aa[i]];
rmqq[i][0]=aa[i];
}
rep(j,1,log2(cna)+1)
for (int i=1;i<=cna+1-(1<<(j-1));++i)
{
rmq[i][j]=rmq[i][j-1];
rmqq[i][j]=rmqq[i][j-1];
if (rmq[i][j]>rmq[i+(1<<(j-1))][j-1])
{
rmq[i][j]=rmq[i+(1<<(j-1))][j-1];
rmqq[i][j]=rmqq[i+(1<<(j-1))][j-1];
}
}
}
int lca(int x,int y)
{
if (x==y) return x;
int l=ff[x],r=ff[y],k;
if (l==r) return rmq[l][0];
if (l>r) swap(l,r);
k=log2(r-l+1);
if (rmq[l][k]>rmq[r-(1<<k)+1][k]) return rmqq[r-(1<<k)+1][k];
else return rmqq[l][k];
}
}tree;
int main()
{
read(n,m);
rep(i,1,n) {read(v[i]);vv[i]=v[i];}
sort(vv+1,vv+1+n);
nn=unique(vv+1,vv+1+n)-vv-1;
rep(i,1,nn) mm[vv[i]]=i;
rep(i,1,n) v[i]=mm[v[i]];
rep(i,1,n-1)
{
int x,y;
read(x,y);
tree.addedge2(x,y);
}
tree.fa[1]=1;
seg.root[0]=newnode();
// seg.root[1]=seg.insert(seg.root[0],v[1]);
tree.dfs(1,0,1);
tree.initrmq();
int lastans=0;
rep(i,1,m)
{
int u,v,k;
read(u,v,k);
u^=lastans;
int temp=tree.lca(u,v);
printf("%d",lastans=vv[seg.query(u,v,temp,tree.fa[temp],k)]);
if (i!=m) putchar(‘\n’);
}
return 0;
}