萌新刚学OI不知道多长时间，树套树求卡常

#include<bits/stdc++.h>
const int lim=1000000000;
struct Segment{int w,ls,rs;}s[20000005];
int n,m,cnt,seg,a[100005],d[100005],h[100005],f[100005],w[100005],ro[100005],dfn[100005],top[100005],
wson[100005],to[200005],nxt[200005];
inline void addstar(int x,int y){
    to[++cnt]=y,nxt[cnt]=h[x],h[x]=cnt;
}
void fisdfs(int x,int las){
    w[x]=1,f[x]=las,d[x]=d[las]+1;
    for(int i=h[x];i;i=nxt[i]) if(to[i]!=las){
        fisdfs(to[i],x),w[x]+=w[to[i]];
        if(w[to[i]]>w[wson[x]]) wson[x]=to[i];
    }
}
void secdfs(int x,int las){
    static int pos;
    dfn[x]=++pos,top[x]=las;
    if(!wson[x]) return;
    secdfs(wson[x],las);
    for(int i=h[x];i;i=nxt[i]) if(to[i]!=f[x]&&to[i]!=wson[x]) secdfs(to[i],to[i]);
}
void update(int &u,int l,int r,int p,int k){
    if(u==0) u=++seg;
    if(l==r) return s[u].w+=k,void();
    int mid=(l+r)>>1;
    if(p<=mid) update(s[u].ls,l,mid,p,k);
    else update(s[u].rs,mid+1,r,p,k);
    s[u].w=s[s[u].ls].w+s[s[u].rs].w;
}
void add(int x,int y){
    for(int i=x;i<=n;i+=i&-i) update(ro[i],1,lim,y,1);
}
int posl,posr,mil[505],mir[505];
void preload(int l,int r){
    for(int i=l-1;i;i-=i&-i) mil[++posl]=ro[i];
    for(int i=r;i;i-=i&-i) mir[++posr]=ro[i];
}
int query(int l,int r,int k){//树套树第k大
    if(l==r) return l;
    int sum=0,mid=(l+r)>>1;
    for(int i=1;i<=posl;i++) sum-=s[s[mil[i]].ls].w;
    for(int i=1;i<=posr;i++) sum+=s[s[mir[i]].ls].w;
    if(k<=sum){
        for(int i=1;i<=posl;i++) mil[i]=s[mil[i]].ls;
        for(int i=1;i<=posr;i++) mir[i]=s[mir[i]].ls;
        return query(l,mid,k);
    }
    else{
        for(int i=1;i<=posl;i++) mil[i]=s[mil[i]].rs;
        for(int i=1;i<=posr;i++) mir[i]=s[mir[i]].rs;
        return query(mid+1,r,k-sum);
    }
}
int querypath(int x,int y,int k){
    using std::swap;
    posl=0,posr=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        preload(dfn[top[x]],dfn[x]);
        x=f[top[x]];
    }
    if(d[x]<d[y]) swap(x,y);
    preload(dfn[y],dfn[x]);
    return query(1,lim,k);
}
int main(){//树剖+树套树 O(nlog^3n)
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n-1;i++){
        int x=read(),y=read();
        addstar(x,y);
        addstar(y,x);
    }
    fisdfs(1,0),secdfs(1,1);
    for(int i=1;i<=n;i++) add(dfn[i],a[i]);
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),k=read();
        write(querypath(x,y,k));
    }
    return sunflush();
}