Description
给你一个n个点的森林，要求支持m个操作：
1.连接两个点 x，y
2.询问若断掉 x，y这条边，两点所在联通块乘积的大小
Hint：
\(n,m<=10^5\)
Solution:
\(LCT\)维护子树\(size\)：
对于每一个点维护\(b[i]\)表示\(i\)点的虚子树大小
每次\(access\)动态更新\(b[i]\)
\(sz[]\)便可以直接\(push\_up\)
#include<bits/stdc++.h>
using namespace std;
const int mxn=1e5+5;
int n,m,t[mxn],fa[mxn],st[mxn],sz[mxn],b[mxn],rev[mxn],val[mxn],ch[mxn][2];
namespace lct {
int isnotrt(int x) {
return ch[fa[x]][0]==x||ch[fa[x]][1]==x;
};
void push_up(int x) {
t[x]=t[ch[x][0]]^t[ch[x][1]]^val[x];
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+b[x]+1;
};
void push_down(int x) {
if(rev[x]) {
rev[ch[x][0]]^=1,rev[ch[x][1]]^=1;
swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);
swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);
rev[x]=0;
}
}
void rotate(int x) {
int y=fa[x],z=fa[y],tp=ch[y][1]==x;
if(isnotrt(y)) ch[z][ch[z][1]==y]=x;/**/ fa[x]=z;
ch[y][tp]=ch[x][tp^1],fa[ch[x][tp^1]]=y;
ch[x][tp^1]=y,fa[y]=x;
push_up(y),push_up(x);
};
void splay(int x) {
int tp=x,s=0; st[++s]=tp;
while(isnotrt(tp)) st[++s]=tp=fa[tp];
while(s) push_down(st[s--]);
while(isnotrt(x)) {
int y=fa[x],z=fa[y];
if(isnotrt(y))
(ch[y][1]==x)^(ch[z][1]==y)?rotate(x):rotate(y);
rotate(x);
}
};
void access(int x) {
for(int y=0;x;x=fa[y=x])
splay(x),b[x]+=sz[ch[x][1]],b[x]-=sz[ch[x][1]=y],push_up(x);
};
void makert(int x) {
access(x); splay(x);
swap(ch[x][0],ch[x][1]);
rev[x]^=1;
};
int findrt(int x) {
access(x); splay(x);
while(ch[x][0]) push_down(x),x=ch[x][0];
splay(x); return x;
};
void split(int x,int y) {
makert(x); access(y); splay(y);
};
void link(int x,int y) {
split(x,y);
fa[x]=y,b[y]+=sz[x],push_up(y); //因为维护的是子树信息，故为了防止对其他节点信息产生影响，合并时两点都必须splay到根
};
}
using namespace lct;
int main()
{
scanf("%d%d",&n,&m); int x,y; char opt[10];
while(m--) {
scanf("%s %d %d",opt,&x,&y);
if(opt[0]=='Q') {
makert(x); access(y); splay(y);
printf("%lld\n",1ll*(sz[y]-sz[x])*(sz[x]));
}
else if(opt[0]=='A') link(x,y);
}
return 0;
}