BZOJ4530 [BJOI2014] 大融合

//Love and Freedom.
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define inf 20021225
#define fa(x) t[x].fa
#define ls(x) t[x].son[0]
#define rs(x) t[x].son[1]
#define nrt(x) (ls(fa(x))==x||rs(fa(x))==x)
#define N 100010
using namespace std;
int read()
{
    int s=0,f=1; char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘) s=s*10+ch-‘0‘,ch=getchar();
    return f*s;
}
struct node{int cnt,sum,fa,son[2]; bool tag;}t[N];
void pushup(int x){t[x].sum=1+t[x].cnt+t[ls(x)].sum+t[rs(x)].sum;}
void rotate(int x)
{
    if(!nrt(x) || !x)    return;
    int f=fa(x),gf=fa(f);
    int k=rs(f)==x,p=k^1;
    if(nrt(f))    t[gf].son[rs(gf)==f]=x;
    if(t[x].son[p])    t[t[x].son[p]].fa=f;
    t[f].son[k]=t[x].son[p]; t[x].son[p]=f;
    t[x].fa=gf; t[f].fa=x;
    pushup(f); pushup(x);
}
void pushdown(int x)
{
    if(t[x].tag)
    {
        swap(ls(x),rs(x));
        if(ls(x))    t[ls(x)].tag^=1;
        if(rs(x))    t[rs(x)].tag^=1;
        t[x].tag=0;
    }
}
void push(int x)
{
    if(nrt(x))    push(fa(x));
    pushdown(x);
}
void splay(int x)
{
    push(x);
    while(nrt(x))
    {
        int f=fa(x),gf=fa(f);
        if(nrt(gf))    (rs(f)==x)^(rs(gf)==f)?rotate(x):rotate(f);
        rotate(x);
    }
}
void access(int x)
{
    int y=0;
    do
    {
        splay(x); t[x].cnt+=t[rs(x)].sum-t[y].sum;
        rs(x)=y; pushup(x); y=x; x=fa(x);
    }while(x);
}
void makeroot(int x)
{
    access(x); splay(x); t[x].tag=1;
}
int getroot(int x)
{
    access(x); splay(x);
    while(ls(x))    x=ls(x);
    return x;
}
void split(int x,int y)
{
    makeroot(x); access(y); splay(y);
}
void link(int x,int y)
{
    split(x,y);
    if(getroot(y)==x)    return;
    t[x].fa=y; t[y].cnt+=t[x].sum;
}
ll calc(int x,int y)
{
    split(x,y);
    return 1ll*t[x].sum*(t[y].sum-t[x].sum);
}
char ch[10];
int main()
{
    int n=read(),m=read();
    for(int i=1;i<=n;i++)    t[i].sum=1;
    while(m--)
    {
        scanf("%s",ch); int x=read(),y=read();
        if(ch[0]==‘A‘)    link(x,y);
        else    printf("%lld\n",calc(x,y));
    }
    return 0;
}