4530: [Bjoi2014]大融合
拿这题作为lct子树查询的练手。本来以为这会是一个大知识点，结果好像只是一个小技巧？
多维护一个虚边连接着的子树大小即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 210010
using namespace std; int p,ca,f;
inline int read(){
p=;ca=getchar();f=;
while(ca<''||ca>'') {if (ca=='-') f=-;ca=getchar();}
while(ca>=''&&ca<='') p=p*+ca-,ca=getchar();
return p*f;
}
struct na{
int y,ne,c,nu;
}b[MN*];
int fa[MN],n,t,x,y,c,num,id[MN],key[MN],ch[MN][],ma[MN],st[MN],Si[MN],si[MN];
bool rt[MN],rev[MN];
inline int max(int a,int b){return a>b?a:b;}
inline void up(int x){si[x]=si[ch[x][]]+si[ch[x][]]+Si[x]+;}
inline void pd(int x){if (rev[x]) swap(ch[x][],ch[x][]),rev[ch[x][]]^=,rev[ch[x][]]^=,rev[x]=;}
inline void rot(int x){
int y=fa[x],kind=ch[y][]==x;
fa[x]=fa[y];
fa[y]=x;
ch[y][kind]=ch[x][!kind];
fa[ch[y][kind]]=y;
ch[x][!kind]=y;
if(rt[y]) rt[y]=,rt[x]=;else ch[fa[x]][ch[fa[x]][]==y]=x;
up(y);up(x);
}
inline void splay(int x){
int i=x,to=;
while (!rt[i]) st[++to]=i,i=fa[i];pd(i);
for (;to;to--) pd(st[to]);
while(!rt[x]){
if (rt[fa[x]]) rot(x);else
if ((ch[fa[fa[x]]][]==fa[x])==(ch[fa[x]][]==x)) rot(fa[x]),rot(x);else rot(x),rot(x);
}
}
inline void acc(int u){
int x=;
while(u){
splay(u);
Si[u]+=si[ch[u][]]-si[x];
rt[ch[u][]]=;rt[ch[u][]=x]=;
up(u);
u=fa[x=u];
}
}
inline void root(int x){acc(x);splay(x);rev[x]^=;}
inline void link(int x,int y){
root(x);acc(y);splay(y);
fa[x]=y;Si[y]+=si[x];
}
inline int qu(int x,int y){
root(x);acc(y);
return (Si[x]+)*(Si[y]+);
}
char ss[];
int main(){
n=read();t=read();
for (int i=;i<=n;i++) rt[i]=si[i]=;
while(t--){
scanf("%s",ss);
x=read();y=read();
if (ss[]=='Q') printf("%d\n",qu(x,y));else link(x,y);
}
}