求解释

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;

struct segnote
{
    int l,r;
    int cnt;
}segtree[N*30];
struct bian
{
    int data;
    int nex;
}e[N<<1];
int head[N],root[N],idx;
int a[N],A[N],cnt;
int deep[N],siz[N],son[N],top[N],fa[N];

void read()
{
    return ;
}

template <typename T,typename ...Args>
void read(T &x,Args &...args)
{
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    read(args...);
}

void add(int x,int y)
{
    e[++cnt].data=y;  e[cnt].nex=head[x];  head[x]=cnt;
}

void insert(int &x,int y,int pos,int left,int right)
{
    x=++idx;
    segtree[x]=segtree[y];
    segtree[x].cnt++;
    if(left==right) return ;
    int mid=(left+right)>>1;
    if(pos<=mid) insert(segtree[x].l,segtree[y].l,pos,left,mid);
    else insert(segtree[x].r,segtree[y].r,pos,mid+1,right);
}

void dfs(int x,int before)
{
    fa[x]=before;
    deep[x]=deep[before]+1;
    siz[x]=1;
    for(int i=head[x];i;i=e[i].nex)
    {
        if(e[i].data==before) continue;
        insert(root[e[i].data],root[x],a[e[i].data],1,cnt);
        dfs(e[i].data,x);
        siz[x]+=siz[e[i].data];
        if(siz[e[i].data]>siz[son[x]]) son[x]=e[i].data;
    }
}

void dfs1(int x,int u)
{
    top[x]=u;
    if(son[x]) dfs1(son[x],u);
    for(int i=head[x];i;i=e[i].nex)
    {
        if(e[i].data==fa[x]||e[i].data==son[x]) continue;
        dfs1(e[i].data,e[i].data);
    }
}

int LCA(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    return x;
}

int query(int x,int y,int z,int w,int k,int left,int right)
{
    if(left==right) return left;
    int num=segtree[segtree[x].l].cnt+segtree[segtree[y].l].cnt-segtree[segtree[z].l].cnt-segtree[segtree[w].l].cnt,mid=(left+right)>>1;
    if(num>=k) return query(segtree[x].l,segtree[y].l,segtree[z].l,segtree[w].l,k,left,mid);
    else return query(segtree[x].r,segtree[y].r,segtree[z].r,segtree[w].r,k-num,mid+1,right);
}

int main()
{
    int n,m,last=0,l,r,k,lca,fa_lca;
    read(n,m);
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        A[i]=a[i];
    }
    sort(A+1,A+1+n);
    cnt=unique(A+1,A+1+n)-A-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(A+1,A+1+cnt,a[i])-A;
    for(int i=1;i<n;i++)
    {
        read(l,r);
        add(l,r);  add(r,l);
    }
    insert(root[1],root[0],a[1],1,cnt);
    dfs(1,0);  dfs1(1,0);
    for(int i=1;i<=m;i++)
    {
        read(l,r,k);
        l^=last;
        lca=LCA(l,r);
        fa_lca=fa[lca];
        printf("%d\n",last=A[query(root[l],root[r],root[lca],root[fa_lca],k,1,cnt)]);
    }
    return 0;
}