对于每个节点维护这个节点到根的权值线段树
对于每个询问(x,y),这条路径上的线段树
tree[x]+tree[y]-tree[lca(x,y)]-tree[fa[lca(x,y)]]
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=;
const int maxm=;
int n,m,tot,cnt,ind,sz,last;
int tmp[maxn],hash[maxn],g[maxn],v[maxn];
int num[maxn],pos[maxn],deep[maxn];
int sum[maxm],lch[maxm],rch[maxm];
int root[maxn];
int fa[maxn][];
struct Edge
{
int t,next;
}e[*maxn];
inline long long read()
{
long long x=,f=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//二分查找离散化之后的x的下标
int find(int x)
{
int l=,r=tot;
while(l<=r)
{
int mid=(l+r)>>;
if(hash[mid]<x) l=mid+;
else if(hash[mid]==x) return mid;
else r=mid-;
}
return l;
}
void insert(int u,int v)
{
cnt++;
e[cnt].t=v;e[cnt].next=g[u];g[u]=cnt;
cnt++;
e[cnt].t=u;e[cnt].next=g[v];g[v]=cnt;
}
void dfs(int x)
{
ind++;num[ind]=x;pos[x]=ind;
for(int i=;i<=;i++)
if((<<i)<=deep[x]) fa[x][i]=fa[fa[x][i-]][i-];
else break;
for(int tmp=g[x];tmp;tmp=e[tmp].next)
{
if(fa[x][]!=e[tmp].t)
{
deep[e[tmp].t]=deep[x]+;
fa[e[tmp].t][]=x;
dfs(e[tmp].t);
}
}
}
void update(int l,int r,int x,int &y,int num)
{
y=++sz;
sum[y]=sum[x]+;
if(l==r) return;
lch[y]=lch[x];rch[y]=rch[x];
int mid=(l+r)>>;
if(num<=mid)
update(l,mid,lch[x],lch[y],num);
else update(mid+,r,rch[x],rch[y],num);
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for(int i=;i<=;i++)
if((<<i)&t) x=fa[x][i];
for(int i=;i>=;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
if(x==y) return x;
return fa[x][];
}
int query(int x,int y,int rk)
{
int a=x,b=y,c=lca(x,y),d=fa[c][];
a=root[pos[a]],b=root[pos[b]],c=root[pos[c]],d=root[pos[d]];
int l=,r=tot;
while(l<r)
{
int mid=(l+r)>>;
int tmp=sum[lch[a]]+sum[lch[b]]-sum[lch[c]]-sum[lch[d]];
if(tmp>=rk) r=mid,a=lch[a],b=lch[b],c=lch[c],d=lch[d];
else rk-=tmp,l=mid+,a=rch[a],b=rch[b],c=rch[c],d=rch[d];
}
return hash[l];
}
int main()
{
n=read();m=read();
for(int i=;i<=n;i++)
v[i]=read(),tmp[i]=v[i];
sort(tmp+,tmp+n+); //点权排序
hash[++tot]=tmp[];
for(int i=;i<=n;i++)
if(tmp[i]!=tmp[i-])
hash[++tot]=tmp[i];
//离散化
for(int i=;i<=n;i++) v[i]=find(v[i]);
//存位置,离散化
for(int i=;i<n;i++)
{
int u,v;
u=read();v=read();
insert(u,v);
}
dfs();
for(int i=;i<=n;i++)
{
int t=num[i]; //树上点权
update(,tot,root[pos[fa[t][]]],root[i],v[t]);//建立主席树
}
for(int i=;i<=m;i++)
{
int x=read(),y=read(),rk=read();
x^=last;
last=query(x,y,rk);
printf("%d",last);
if(i!=m) printf("\n");
}
return ;
}