https://www.luogu.com.cn/problem/P2633
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,Siz,cnt,last,rt[N],a[N],s[N];
int fa[N][20],dep[N];
struct node
{
int l,r,sum;
}tree[N*32];
vector<int>v[N];
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;--i)
if(dep[fa[x][i]]>dep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=19;i>=0;--i)
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
return fa[x][0];
}
int update(int x,int l,int r,int k)
{
int now=++cnt;
tree[now]=tree[x];
tree[now].sum++;
if(l<r)
{
int mid=(l+r)/2;
if(k<=mid) tree[now].l=update(tree[x].l,l,mid,k);
else tree[now].r=update(tree[x].r,mid+1,r,k);
}
return now;
}
int query(int a,int b,int c,int d,int l,int r,int k)
{
if(l==r) return s[l];
int val=tree[tree[a].l].sum+tree[tree[b].l].sum-tree[tree[c].l].sum-tree[tree[d].l].sum;
int mid=(l+r)/2;
if(val>=k) return query(tree[a].l,tree[b].l,tree[c].l,tree[d].l,l,mid,k);
return query(tree[a].r,tree[b].r,tree[c].r,tree[d].r,mid+1,r,k-val);
}
void dfs(int x,int father)
{
int t=lower_bound(s+1,s+1+Siz,a[x])-s;
rt[t]=update(x,1,Siz,a[x]);
dep[x]=dep[father]+1;
fa[x][0]=father;
for(int i=1;i<=19;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(auto i:v[x])
{
if(i==father) continue;
dfs(i,x);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>a[i],s[i]=a[i];
for(int i=1;i<n;++i)
{
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
sort(s+1,s+1+n);
int Siz=unique(s+1,s+1+n)-s-1;
dfs(1,0);
while(m--)
{
int x,y,k;
cin>>x>>y>>k;
x^=last;
int t=lca(x,y);
last=query(x,y,t,fa[t][0],1,Siz,k);
cout<<last<<"\n";
}
return 0;
}