rt 为什么我把深度大的合并到深度小的就会ac 把深度小的合并的深度大的就会t ac片段

if(opt==1)
    {
      cin>>a>>b;
      int fax=findfa(a,i-1);
      int fay=findfa(b,i-1);
      int dpx=st.ask_dp(st.root[i-1],1,n,fax);
      int dpy=st.ask_dp(st.root[i-1],1,n,fay);
      if(dpx<dpy)
        st.root[i]=st.change(st.root[i-1],1,n,fay,fax);
      else if(dpx!=dpy)
        st.root[i]=st.change(st.root[i-1],1,n,fax,fay);
      else
        st.root[i]=st.change(st.root[i-1],1,n,fax,fay),
        st.root[i]=st.change_s(st.root[i],1,n,fay);
    }

tle片段

if(opt==1)
    {
      cin>>a>>b;
      int fax=findfa(a,i-1);
      int fay=findfa(b,i-1);
      int dpx=st.ask_dp(st.root[i-1],1,n,fax);
      int dpy=st.ask_dp(st.root[i-1],1,n,fay);
      if(dpx>dpy)
        st.root[i]=st.change(st.root[i-1],1,n,fay,fax);
      else if(dpx!=dpy)
        st.root[i]=st.change(st.root[i-1],1,n,fax,fay);
      else
        st.root[i]=st.change(st.root[i-1],1,n,fax,fay),
        st.root[i]=st.change_s(st.root[i],1,n,fay);
    }

完整代码

#include<bits/stdc++.h>
using namespace std;
#define N 400005
int n,m;
int a[N];
int nxtk;
struct setshit
{
  int tot=0;
  struct node 
  {
    int son[2];
    int val;
    int dep;
  }tr[N<<5];
  int root[N];
  int change(int x,int l,int r,int k,int v)
  {
    int rtt=++tot;
    tr[rtt]=tr[x];
    if(l==r)
    {
      tr[rtt].val=v;
      return rtt;
    } 
    int mid=(l+r)>>1;
    if(k<=mid)
      tr[rtt].son[0]=change(tr[x].son[0],l,mid,k,v);
    else
      tr[rtt].son[1]=change(tr[x].son[1],mid+1,r,k,v);
    return rtt;
  }
  int change_s(int x,int l,int r,int k)
  {
    int rtt=++tot;
    tr[rtt]=tr[x];
    if(l==r)
    {
      tr[rtt].dep++;
      return rtt;
    } 
    int mid=(l+r)>>1;
    if(k<=mid)
      tr[rtt].son[0]=change_s(tr[x].son[0],l,mid,k);
    else
      tr[rtt].son[1]=change_s(tr[x].son[1],mid+1,r,k);
    return rtt;
  }
  int ask(int x,int l,int r,int k)
  {
    if(l==r)
      return tr[x].val;
    int mid=(l+r)>>1;
    if(k<=mid)
      return ask(tr[x].son[0],l,mid,k);
    if(mid<k)
      return ask(tr[x].son[1],mid+1,r,k);
  }
  int ask_dp(int x,int l,int r,int k)
  {
    if(l==r)
      return tr[x].dep;
    int mid=(l+r)>>1;
    if(k<=mid)
      return ask(tr[x].son[0],l,mid,k);
    if(mid<k)
      return ask(tr[x].son[1],mid+1,r,k);
  }
  int build(int l,int r)
  {
    int rtt=++tot;
    if(l==r)
    {
      tr[rtt].val=a[l];
      tr[rtt].dep=1;
      return rtt;
    }                             
    int mid=(l+r)>>1;                                         
    tr[rtt].son[0]=build(l,mid);
    tr[rtt].son[1]=build(mid+1,r);
    return rtt;
  }
}st;
int nowk=0;
int findfa(int x,int kt)
{
  int fa=st.ask(st.root[kt],1,n,x);
  if(fa==x)
    return x;
  else
    return findfa(fa,kt);
}
int main()
{
  ios::sync_with_stdio(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++)
    a[i]=i;
  st.root[0]=st.build(1,n);
  for(int i=1;i<=m;i++)
  {
    nxtk=i;
    int opt,a,b;
    cin>>opt;
    if(opt==2)
    {
      cin>>a;
      st.root[i]=st.root[a];
    }
    if(opt==1)
    {
      cin>>a>>b;
      int fax=findfa(a,i-1);
      int fay=findfa(b,i-1);
      int dpx=st.ask_dp(st.root[i-1],1,n,fax);
      int dpy=st.ask_dp(st.root[i-1],1,n,fay);
      if(dpx<dpy)
        st.root[i]=st.change(st.root[i-1],1,n,fay,fax);
      else if(dpx!=dpy)
        st.root[i]=st.change(st.root[i-1],1,n,fax,fay);
      else
        st.root[i]=st.change(st.root[i-1],1,n,fax,fay),
        st.root[i]=st.change_s(st.root[i],1,n,fay);
    }
    if(opt==3)
    {
      cin>>a>>b;
      if(findfa(a,i-1)==findfa(b,i-1))
        cout<<1<<endl;
      else
        cout<<0<<endl;
      st.root[i]=st.root[i-1];
    }
  }
  return 0;
}