有没有和我思路一样的啊……
记录每个节点的版本号，它是从根一路加到这个节点的主席树对应版本号
这样每个点对应的版本就可以一遍 $dfs$ 搞出来，从父亲版本转移到它的版本
然后query的时候在 $ind[u]$ 和 $ind[v]$ 两个版本上一起跳，减掉两个 $fa[LCA(u,v)]$ 的版本的贡献找第 $k$ 大

但是SPOJ那道题在#11RE，这题全MLE……

#include <bits/stdc++.h>
#define ri register int
#define MAXN 100001
#define ll long long
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template<typename T>
using namespace std;

namespace SlowIO{
    Tp inline void rd(T &x){
        x=0; bool f=1; char in=g();
        while(!isdigit(in)) f&=(in!='-'),in=g();
        while(isdigit(in)) x=(x<<3)+(x<<1)+(in^48),in=g();
        x*=((f<<1)-1);
    }
    Tp inline void op(T x){
        if(x<0) pc('-'),x=-x;
        if(x>=10) op(x/10);
        pc(x%10+48);
    }
    Tp inline void writeln(T x){ op(x),pc('\n'); }
    Tp inline void writesp(T x){ op(x),pc(' '); }
}; using namespace SlowIO;

namespace Chairman_Tree{
    int root[MAXN],tot;
    struct seg{
        int lc,rc;
        int val;
    }tr[MAXN<<7];
    #define lef(a) tr[a].lc
    #define rig(a) tr[a].rc
    #define Val(a) tr[a].val
    inline void change(int &u,int lst,int l,int r,int pos,int delta){
        u=++tot;
        tr[u]=tr[lst],Val(u)+=delta;
        if(l==r) return;
        int mid=l+r>>1;
        if(pos<=mid) change(lef(u),lef(lst),l,mid,pos,delta);
        else change(rig(u),rig(lst),mid+1,r,pos,delta);
    }
    inline int query(int u,int v,int lst,int l,int r,int k){
        if(l==r) return l;
        int mid=l+r>>1,t=Val(lef(u))+Val(lef(v))-(Val(lef(lst))<<1);
        if(k<=t) return query(lef(u),lef(v),lef(lst),l,mid,k);
        else return query(rig(u),rig(v),rig(lst),mid+1,r,k-t);
    }
}; using namespace Chairman_Tree;

int head[MAXN],cntr;
struct edge{
    int to,nxt;
}e[MAXN<<1];
inline void add(int u,int v){
    e[++cntr]=(edge){v,head[u]};
    head[u]=cntr;
}

int n,m;
int a[MAXN],maxa;

int top[MAXN],fa[MAXN],son[MAXN],id;
int siz[MAXN],depth[MAXN],ind[MAXN];
#define gfore(u) for(ri i=head[u];i;i=e[i].nxt)
inline void dfs(int u,int father){
    ind[u]=++id,change(root[ind[u]],root[ind[father]],1,maxa,a[u],1);
    fa[u]=father,siz[u]=1;
    depth[u]=depth[father]+1;
    gfore(u){ int &v=e[i].to;
        if(v==father) continue;
        dfs(v,u),siz[u]+=siz[v];
        son[u]=(siz[son[u]]<siz[v]?v:son[u]);
    }
}
inline void deu5(int u,int tp){
    top[u]=tp;
    if(!son[u]) return;
    deu5(son[u],tp);
    gfore(u){ int &v=e[i].to;
        if(v==fa[u]||v==son[u]) continue;
        deu5(v,v);
    }
}
#define swp(a,b) a^=b^=a^=b
inline int LCA(int a,int b){
    while(top[a]!=top[b]){
        if(depth[top[a]]<depth[top[b]]) swp(a,b);
        a=fa[top[a]];
    } return depth[a]>depth[b]?b:a;
}

int main()
{
    rd(n),rd(m);
    for(ri i=1;i<=n;i++)
    rd(a[i]),maxa=max(maxa,a[i]);
    for(ri i=1,x,y;i<=n-1;i++){
        rd(x),rd(y);
        add(x,y),add(y,x);
    } dfs(1,0),deu5(1,1);
    ri u,v,k,lst=0,lca;
    while(m--){
        rd(u),rd(v),rd(k);
        u^=lst;
        lca=LCA(u,v);
        lst=query(root[ind[u]],root[ind[v]],root[ind[fa[lca]]],1,maxa,k);
        writeln(lst);
    }
    return 0;
}
//悲