[BJOI2014]大融合 lct维护虚子树大小

lct在动态连边和删边方面比较有优势，但是在维护子树信息方面又没有树链剖分那么方便。这道题算是lct维护虚子树信息比较裸的一道题。

以s[]数组为总的子树大小，sx[]数组为虚子树大小。

要维护虚子树信息 在lct原来的模板上有三个地方需要改。

pushup函数：总子树大小显然是实子树大小+虚子树大小

I pushup(R x){

    s[x]=s[lc]+s[rc]+sx[x]+1;

}

access函数：在进行access的过程，x的虚子树产生了变化，本来是y，后来变成了x现在的右儿子。

I access(R x){

    for(R y=0;x;x=f[y=x]){

        splay(x);

        sx[x]+=s[rc];

        sx[x]-=s[rc=y];

        pushup(x);//这个可以不写

    }

}

link函数：在连接两个点的时候，（x连y）我们把x连做y的虚儿子，显然y的虚子树需要加上x的大小 另外需要注意的是 必须把y结点splay到最上面才能保证更新的正确性（类似splay的更新原理）

I link(R x,R y){

    split(x,y);

    sx[f[x]=y]+=s[x];

    pushup(y);

}

答案显然就是把x和y结点split出来 然后(sx[x]+1)*(sx[y]+1)

最后推荐大佬：FlashHu的博客  真的有用 把lct讲的很透

#include<bits/stdc++.h>
#define R register int
#define I inline void
#define lc c[x][0]
#define rc c[x][1]
using namespace std;
const int N=2e5+100;
typedef long long ll;
inline int in(){
	int w=0,x=0;char c=0;
	while(c>'9'||c<'0') w|=c=='-',c=getchar();
	while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
int f[N],c[N][2],st[N];
int s[N],sx[N];
bool r[N];
inline bool nroot(R x){//判断节点是否为一个Splay的根（与普通Splay的区别1）
    return c[f[x]][0]==x||c[f[x]][1]==x;
}//原理很简单，如果连的是轻边，他的父亲的儿子里没有它
I pushup(R x){
	s[x]=s[lc]+s[rc]+sx[x]+1;
}
I pushr(R x){R t=lc;lc=rc;rc=t;r[x]^=1;}//翻转操作
I pushdown(R x){//判断并释放懒标记
    if(r[x]){
        if(lc)pushr(lc);
        if(rc)pushr(rc);
        r[x]=0;
    }
}
I rotate(R x){//一次旋转
    R 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(nroot(y))语句，此处不判断会引起致命错误（与普通Splay的区别2）
    if(w)f[w]=y;f[y]=x;f[x]=z;
    pushup(y);
}
I splay(R x){//只传了一个参数，因为所有操作的目标都是该Splay的根（与普通Splay的区别3）
    R y=x,z=0;
    st[++z]=y;//st为栈，暂存当前点到根的整条路径，pushdown时一定要从上往下放标记（与普通Splay的区别4）
    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);
}
I access(R x){
	for(R y=0;x;x=f[y=x]){
		splay(x);
		sx[x]+=s[rc];
		sx[x]-=s[rc=y];
		pushup(x);
	}
}
I makeroot(R x){//换根
    access(x);splay(x);
    pushr(x);
}
int findroot(R x){//找根（在真实的树中的）
    access(x);splay(x);
    while(lc)pushdown(x),x=lc;
    splay(x);
    return x;
}
I split(R x,R y){//提取路径
    makeroot(x);
    access(y);splay(y);
}
I link(R x,R y){
	split(x,y);
	sx[f[x]=y]+=s[x];
	pushup(y);
}//LCT模板到此结束
I cut(R x,R y){//断边
    makeroot(x);
    if(findroot(y)==x&&f[y]==x&&!c[y][0]){
        f[y]=c[x][1]=0;
        pushup(x);
    }
}
int main(){
   	int n,m;
   	n=in(),m=in();
   	for(int i = 1; i <= n; i++) s[i]=1;
   	char op[3];
   	int x,y;
   	for(int i = 1; i <= m; i++){
   		scanf("%s",op);
		x=in(),y=in();
		if(op[0]=='A') link(x,y);
		else{
			split(x,y);
			printf("%lld\n",1ll*(sx[x]+1)*(sx[y]+1));
		}   		
	}
    return 0;
}