\(\text{Solution:}\)
就是一个树上静态第 \(k\) 小。
考虑对于一个点 \(x\) 维护一棵主席树，它的信息是 \([root,x].\)
这样对于一条路径 \(<s,t>\) ，它的信息可以用树上差分的思想来统计：
\[cnt=root[s]+root[t]-root[LCA]-root[pa[LCA]] \]有了这个式子就好办了，树剖 LCA 套上树上差分即可。
时间复杂度 \(O(n\log n).\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=2e5+10;
const int N=(MAXN<<5);
int rt[MAXN],node,siz[MAXN],pa[MAXN];
struct Tr{int ls,rs,sum;}tr[N];
int head[MAXN],tot,top[MAXN],son[MAXN];
struct E{int nxt,to;}e[MAXN];
inline void add(int x,int y){e[++tot]=(E){head[x],y};head[x]=tot;}
int b[MAXN],blen,n,m,a[MAXN],lastans,dep[MAXN];
inline int Min(int x,int y){return x<y?x:y;}
inline int Max(int x,int y){return x>y?x:y;}
inline int read() {
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)) {
if(ch=='-')w=-1;
ch=getchar();
}
while(isdigit(ch)) {
s=s*10-48+ch;
ch=getchar();
}
return w*s;
}
inline int getpos(int v){return lower_bound(b+1,b+blen+1,v)-b;}
int change(int x,int l,int r,int pos,int v){
int p=++node;
tr[p]=tr[x];
tr[p].sum+=v;
if(l==r)return p;
int mid=(l+r)>>1;
if(pos<=mid)tr[p].ls=change(tr[p].ls,l,mid,pos,v);
else tr[p].rs=change(tr[p].rs,mid+1,r,pos,v);
return p;
}
int query(int x,int y,int l,int fl,int L,int R,int k){
//cnt=x+y-l-fl
if(L==R)return L;
int mid=(L+R)>>1;
int cnt=tr[tr[x].ls].sum+tr[tr[y].ls].sum-tr[tr[l].ls].sum-tr[tr[fl].ls].sum;
if(k<=cnt)return query(tr[x].ls,tr[y].ls,tr[l].ls,tr[fl].ls,L,mid,k);
else return query(tr[x].rs,tr[y].rs,tr[l].rs,tr[fl].rs,mid+1,R,k-cnt);
}
void dfs1(int x){
siz[x]=1;dep[x]=dep[pa[x]]+1;
for(int i=head[x];i;i=e[i].nxt){
int j=e[i].to;
if(j==pa[x])continue;
pa[j]=x;
dfs1(j);siz[x]+=siz[j];
if(siz[j]>siz[son[x]])son[x]=j;
}
}
void dfs2(int u,int t){
top[u]=t;
if(!son[u])return;
dfs2(son[u],t);
for(int i=head[u];i;i=e[i].nxt){
int j=e[i].to;
if(j==pa[u]||j==son[u])continue;
dfs2(j,j);
}
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]>=dep[top[y]])x=pa[top[x]];
else y=pa[top[y]];
// cout<<x<<" "<<y<<endl;
}
return dep[x]<dep[y]?x:y;
}
void dfs(int x,int fa){
rt[x]=change(rt[fa],1,blen,a[x],1);
for(int i=head[x];i;i=e[i].nxt){
int j=e[i].to;
if(j==fa)continue;
dfs(j,x);
}
}
signed main(){
// freopen("P2633_1.in","r",stdin);
// freopen("my.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i)a[i]=read(),b[i]=a[i];
sort(b+1,b+n+1);
blen=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;++i)a[i]=getpos(a[i]);
// for(int i=1;i<=n;++i)printf("%d ",a[i]);
// puts("");
for(int i=1;i<n;++i){
int u=read(),v=read();
add(u,v);add(v,u);
}
dfs1(1);dfs2(1,1);dfs(1,1);
//puts("RE!");return 0;
// for(int i=1;i<=n;++i)printf("%d:dep%d,siz%d\n",i,dep[i],siz[i]);
for(int i=1;i<=m;++i){
int u=read(),v=read(),k=read();
u^=lastans;
// printf("(%lld %lld)\n",u,v);
int Lca=LCA(u,v);
// printf("LCA:%lld\n",Lca);
lastans=b[query(rt[u],rt[v],rt[Lca],rt[pa[Lca]],1,blen,k)];
printf("%lld\n",lastans);
}
return 0;
}