rt，指如何快速实现主席树。

我的代码使用指针实现动态开点，按理说应该比较快且省空间，然而却用了 1s 多，空间用了 88MB

#include<bits/stdc++.h>
#define ls(x) x->lc
#define rs(x) x->rc
#define sum(x) x->sum
using namespace std;
const int N=1e5+5;
int n,m,a[N],la,lsh,rev[N],f[20][N],d[N],lg[N];
set<int>s;
map<int,int>mp;
vector<int>g[N];
struct node{
    int sum;
    node*lc,*rc;
    node(){
        sum=0;
        lc=rc=NULL;
    }
}*rt[N];
void build(node*&x,int l,int r){
    x=new node;
    if(l^r){
        int mid=(l+r)>>1;
        build(ls(x),l,mid);
        build(rs(x),mid+1,r);
    }
}
void insert(node*&x,node*y,int l,int r,int k){
    x=new node;
    sum(x)=sum(y)+1;
    if(l^r){
        int mid=(l+r)>>1;
        if(k<=mid){
            rs(x)=rs(y);
            insert(ls(x),ls(y),l,mid,k);
        }else{
            ls(x)=ls(y);
            insert(rs(x),rs(y),mid+1,r,k);
        }
    }
}
int query(node*x,node*y,node*u,node*v,int l,int r,int k,int ok){
    if(l^r){
        int mid=(l+r)>>1,p=sum(ls(x))+sum(ls(y))-sum(ls(u))-sum(ls(v))+ok;
        if(p>=k){
            return query(ls(x),ls(y),ls(u),ls(v),l,mid,k,ok);
        }
        return query(rs(x),rs(y),rs(u),rs(v),mid+1,r,k,p);
    }
    return l;
}
void dfs(int x,int fa){
    insert(rt[x],rt[fa],1,lsh,a[x]);
    for(int i=1;i<=lg[d[x]];++i){
        f[i][x]=f[i-1][f[i-1][x]];
    }
    for(vector<int>::iterator it=g[x].begin();it!=g[x].end();++it){
        if(*it^fa){
            d[*it]=d[x]+1;
            dfs(*it,f[0][*it]=x);
        }
    }
}
int lca(int x,int y){
    if(d[x]<d[y]){
        swap(x,y);
    }
    while(d[x]^d[y]){
        x=f[lg[d[x]-d[y]]][x];
    }
    if(x^y){
        for(int i=lg[d[x]];~i;--i){
            if(f[i][x]^f[i][y]){
                x=f[i][x];
                y=f[i][y];
            }
        }
        return f[0][x];
    }
    return x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
        s.insert(a[i]);
        lg[i]=log2(i);
    }
    for(set<int>::iterator it=s.begin();it!=s.end();++it){
        rev[mp[*it]=++lsh]=*it;
    }
    for(int i=1;i<=n;++i){
        a[i]=mp[a[i]];
    }
    build(rt[0],1,lsh);
    for(int i=1,u,v;i^n;++i){
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    for(int x,y,k,h;m--;){
        scanf("%d%d%d",&x,&y,&k);
        h=lca(x^=la,y);
        printf("%d\n",la=rev[query(rt[x],rt[y],rt[h],rt[f[0][h]],1,lsh,k,0)]);
    }
}