[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;
}