题解

模拟题意即可，把每次接过去的子树看做一个点，然后这个关系构成了一棵树。

大力倍增即可。

代码

#include
    
     #define N 100009#define ls tr[cnt].l#define rs tr[cnt].rusing namespace std;typedef long long ll;int p[20][N],deep[N],tot,head[N],n,m,q,tott,dep[N],pr[20][N],T[N],size[N],c[N],pre[N];ll dis[20][N],noww,b[N],nowid;inline ll rd(){    ll x=0;char c=getchar();bool f=0;    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}struct node{    int l,r,size;}tr[N*40];struct edge{int n,to;}e[N<<1];inline void add(int u,int v){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;}inline void ins(int &cnt,int l,int r,int id){    cnt=++tott;    tr[cnt].size++;    if(l==r)return;    int mid=(l+r)>>1;    if(mid>=id)ins(ls,l,mid,id);    else ins(rs,mid+1,r,id);}int merge(int u,int v){    if(!u||!v)return u^v;    int cnt=++tott;    tr[cnt].size=tr[u].size+tr[v].size;    ls=merge(tr[u].l,tr[v].l);    rs=merge(tr[u].r,tr[v].r);    return cnt;} inline int kth(int &cnt,int l,int r,int k){    int mid=(l+r)>>1;    if(l==r)return l;    if(tr[ls].size
     
      =0;--i)if(deep[u]-(1<
      
       =deep[v])u=p[i][u];    if(u==v)return u;    for(int i=19;i>=0;--i)if(p[i][u]!=p[i][v])u=p[i][u],v=p[i][v];    return p[0][u];}inline int jump(int x,int xx){    for(int i=19;i>=0;--i)if((1<
       
        =0;--i)if((1<
        
         =0;--i)if(dep[x]-(1<
         
          =dep[y]){ ans+=dis[i][x];x=pr[i][x]; } for(int i=19;i>=0;--i)if(pr[i][x]!=pr[i][y]){ ans+=dis[i][x]+dis[i][y];x=pr[i][x];y=pr[i][y]; } int dx=pre[x],dy=pre[y];ans+=2; // cout<
          
           <<" "<
           
            <<" "<
            
             <<" "<
             
              <<" "; ans+=deep[dx]+deep[dy]-2*deep[getlca(dx,dy)]; } printf("%lld\n",ans); } return 0;}