在树上建主席树......
每个点从父亲那里建过来，最后建出来就是从根到$i$这条链上的主席树，查询的时候一边差分一边查询
($cmt[u]+cmt[v]-cmt[lca(u,v)]-cmt[anc[lca(u,v)]]$)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,K=;
int p[N],noww[*N],goal[*N];
int siz[N],anc[N],dep[N],imp[N],top[N];
int num[N],tep[N],cmt[N*K],son[N*K][],sum[N*K],uni[N*K];
int n,m,t1,t2,t3,lca,cnt,tot,len,xnt,ans,n1,n2,n3,n4;
void link(int f,int t)
{
noww[++cnt]=p[f];
goal[cnt]=t,p[f]=cnt;
}
int Create(int pre,int l,int r,int pos)
{
int nde=++xnt;
son[nde][]=son[pre][];
son[nde][]=son[pre][];
sum[nde]=sum[pre]+;
if(l<r)
{
int mid=(l+r)/;
if(pos<=mid) son[nde][]=Create(son[pre][],l,mid,pos);
else son[nde][]=Create(son[pre][],mid+,r,pos);
}
return nde;
}
int Query(int l,int r,int rnk)
{
if(l==r) return l;
int mid=(l+r)/,noww=sum[son[n1][]];
noww+=sum[son[n2][]]-sum[son[n3][]]-sum[son[n4][]];
if(rnk<=noww)
{
n1=son[n1][],n2=son[n2][],n3=son[n3][],n4=son[n4][];
return Query(l,mid,rnk);
}
else
{
n1=son[n1][],n2=son[n2][],n3=son[n3][],n4=son[n4][];
return Query(mid+,r,rnk-noww);
}
}
void DFS(int nde,int fth,int dth)
{
int tmp=;
siz[nde]=,dep[nde]=dth,anc[nde]=fth;
cmt[nde]=Create(cmt[anc[nde]],,len,num[nde]);
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth)
{
DFS(goal[i],nde,dth+);
siz[nde]+=siz[goal[i]];
if(siz[goal[i]]>tmp)
tmp=siz[goal[i]],imp[nde]=goal[i];
}
}
void MARK(int nde,int tpp)
{
top[nde]=tpp;
if(imp[nde])
{
MARK(imp[nde],tpp);
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=anc[nde]&&goal[i]!=imp[nde])
MARK(goal[i],goal[i]);
}
}
int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y); x=anc[top[x]];
}
return dep[x]<dep[y]?x:y;
}
int main ()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&num[i]),tep[i]=num[i];
sort(tep+,tep++n),len=unique(tep+,tep++n)-tep-;
for(int i=;i<=n;i++)
num[i]=lower_bound(tep+,tep++len,num[i])-tep;
for(int i=;i<n;i++)
scanf("%d%d",&t1,&t2),link(t1,t2),link(t2,t1);
DFS(,,); MARK(,);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&t3),t1^=ans,lca=LCA(t1,t2);
n1=cmt[t1],n2=cmt[t2],n3=cmt[lca],n4=cmt[anc[lca]];
printf("%d\n",ans=tep[Query(,len,t3)]);
}
return ;
}