BZOJ4530 BJOI 2014 大融合

对LCT子树大小进行维护。

size表示实子树大小，sz表示虚子树大小。

具体操作是体现在link和splay中，可以看代码。

注意每次做完都要update。

By：大奕哥

 #include<bits/stdc++.h>

 using namespace std;

 const int N=1e5+;

 int fa[N],ma[N],pos[N],c[N][],rev[N],s[N],n,m,q,size[N],sz[N];

 bool isroot(int x){return c[fa[x]][]!=x&&c[fa[x]][]!=x;}

 void update(int x)

 {

     size[x]=size[c[x][]]+size[c[x][]]++sz[x];

 }

 void pushup(int x)

 {

     if(rev[x])

     {

         rev[x]^=;rev[c[x][]]^=;rev[c[x][]]^=;

         swap(c[x][],c[x][]);

     }

 }

 void rotate(int x)

 {

     int y=fa[x],z=fa[y],l,r;

     l=c[y][]==x;r=l^;

     if(!isroot(y))c[z][c[z][]==y]=x;

     fa[x]=z;fa[y]=x;fa[c[x][r]]=y;

     c[y][l]=c[x][r];c[x][r]=y;

     update(y);update(x);

 }

 void splay(int x)

 {

     int top=,i;

     for(i=x;!isroot(i);i=fa[i])s[++top]=i;s[++top]=i;

     for(;top;top--)pushup(s[top]);

     while(!isroot(x))

     {

         int y=fa[x],z=fa[y];

         if(!isroot(y))

         {

             if(c[y][]==x^c[z][]==y)rotate(x);

             else rotate(y);

         }

         rotate(x);

     }

     return;

 }

 void access(int x)

 {

     int y=;

     while(x)

     {

         splay(x);

         sz[x]=sz[x]-size[y]+size[c[x][]];

         c[x][]=y;

         update(x);

         y=x;x=fa[x];

     }

 }

 void mroot(int x)

 {

     access(x);splay(x);rev[x]^=;

 }

 void link(int x,int y)

 {

     mroot(x);mroot(y);

     sz[y]+=size[x];

     update(y);

     fa[x]=y;

     splay(x);

 }

 int main()

 {

     scanf("%d%d",&n,&q);long long ans;

     for(int i=;i<=n;++i)size[i]=;int x,y;

     for(int i=;i<=q;++i)

     {

         scanf("%s%d%d",s,&x,&y);

         if(s[]=='A')link(x,y);

         else

         {

             mroot(x);access(y);

             ans=sz[y]+;

             mroot(y);access(x);

             ans*=(sz[x]+);

             printf("%lld\n",ans);

         }

     }

     return ;

 }