【LCT】洞穴探测

甚至比模板题还要简单不少。

打通隧道就link，破坏隧道就cut

是否联通就findroot看两点的根节点是否相同。

Code

#include<bits/stdc++.h>
using namespace std;
#define lc c[x][0]
#define rc c[x][1]
const int SZ=1<<19,N=3e5+12;
int f[N],c[N][2],v[N],s[N],st[N];
bool r[N];
bool nroot(int x)
{
  return c[f[x]][0]==x || c[f[x]][1]==x;
}
void pushup(int x)
{
  s[x]=s[lc]^s[rc]^v[x];
}

void pushr(int x)
{
  int t=lc;
  lc=rc,rc=t,r[x]^=1;
}

void pushdown(int x)
{
  if( r[x] )
  {
    if( lc ) pushr(lc);
    if( rc ) pushr(rc);
    r[x]=0;
  }
}
void rotate(int x)
{
  int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
  if( nroot(y) ) c[z][c[z][1]==y]=x;
  c[x][!k]=y;c[y][k]=w;
  if( w ) f[w]=y;
  f[y]=x;f[x]=z;
  pushup(y);
}
void splay(int x)
{
  int y=x,z=0;
  st[++z]=y;
  while( nroot(y) ) st[++z]=y=f[y];
  while(    z     ) pushdown(st[z--]);
  while( nroot(x) )
  {
    y=f[x],z=f[y];
    if( nroot(y) )
    {
      rotate( (c[y][0]==x)^(c[z][0]==y) ? x:y);
    }
    rotate(x);
  }
  pushup(x);
}

void access(int x)
{
  for(int y=0;x;x=f[y=x]) splay(x),rc=y,pushup(x);
}

void makeroot(int x)
{
  access(x);
  splay(x);
  pushr(x);
}

int findroot(int x)
{
  access(x);splay(x);
  while(lc) pushdown(x),x=lc;
  splay(x);
  return x;
}

void split(int x,int y)
{
  makeroot(x);
  access(y);
  splay(y);
}

void link(int x,int y)
{
  makeroot(x);
  if( findroot(y)!=x ) f[x]=y;
}

void cut(int x,int y)
{
  makeroot(x);
  if( findroot(y)==x and f[y]==x and !c[y][0] )
  {
    f[y]=c[x][1]=0;
    pushup(x);
  }
}
int main(){
  int n,m;
  cin>>n>>m;
  string s;int x,y;
  while(m--)
  {
    cin>>s>>x>>y;
    if( s=="Connect" )
    {
      link(x,y);
    }
    else if( s=="Query" )
    {
      if( findroot(y)==findroot(x) )
      {
        cout<<"Yes"<<endl;
      }
      else cout<<"No"<<endl;
    }
    else
    {
        cut(x,y);
    }

  }
}