思路

运用树上差分的思想，转化成一个普通的主席树模型即可求解

代码

#include 
    
     #include 
     
      #include 
      
       using namespace std;struct Node{    int lson,rson,sz;}pt[100100*30];const int MAXlog=19;int dep[100100],jump[100100][MAXlog],lastans=0,n,m,u[100100<<1],Nodecnt,v[100100<<1],w_p[100100],ax[100100],nx,fir[100100],nxt[100100<<1],cnt,root[100100];void addedge(int ui,int vi){    ++cnt;    u[cnt]=ui;    v[cnt]=vi;    nxt[cnt]=fir[ui];    fir[ui]=cnt;}void insert(int L,int R,int pos,int &o){    pt[++Nodecnt]=pt[o];    o=Nodecnt;    pt[o].sz++;    if(L==R)        return;    int mid=(L+R)>>1;    if(pos<=mid)        insert(L,mid,pos,pt[o].lson);    else        insert(mid+1,R,pos,pt[o].rson);}int lca(int x,int y){    if(dep[x]
       
        =0;i--)        if(dep[x]-(1<
        
         =dep[y])            x=jump[x][i];    if(x==y)        return x;    for(int i=MAXlog-1;i>=0;i--)        if(jump[x][i]!=jump[y][i])            x=jump[x][i],y=jump[y][i];    return jump[x][0];}int query(int L,int R,int k,int rootx,int rooty,int rootlca,int falca){    if(L==R)        return L;    int lch=pt[pt[rootx].lson].sz+pt[pt[rooty].lson].sz-pt[pt[rootlca].lson].sz-pt[pt[falca].lson].sz;    int mid=(L+R)>>1;    if(lch