题意：写一个数据结构，支持图上连边（保证图是森林）和询问一条边两端的连通块大小的乘积。$\text{点数、询问数} \leq 10^5$
图上连边，$LCT$跑不掉
支持子树$size$有点麻烦。我们需要虚子树的$size$和（实子树的可以直接$pushup$），那么我们对于每一个点就去维护其虚子树的$size$和，那么每一个点的子树和就是可以维护的了。可以知道只有$link$和$access$操作会修改虚子树和（其他都在实链上进行操作），稍微加一点东西就行了。相对来说还是比较裸。
注意$pushup$的改变。
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
struct node{
] , fa , allSize;
bool mark;
}Tree[MAXN];
int N , M;
inline bool nroot(int x){
] == x || Tree[Tree[x].fa].ch[] == x;
}
inline bool son(int x){
] == x;
}
inline void pushup(int x){
Tree[x].allSize = Tree[Tree[x].ch[]].allSize + Tree[Tree[x].ch[]].allSize + Tree[x].size + ;
}
inline void ZigZag(int x){
bool f = son(x);
];
if(nroot(y))
Tree[z].ch[son(y)] = x;
Tree[x].fa = z;
Tree[x].ch[f ^ ] = y;
Tree[y].fa = x;
Tree[y].ch[f] = w;
if(w)
Tree[w].fa = y;
pushup(y);
pushup(x);
}
inline void pushdown(int x){
if(Tree[x].mark){
Tree[Tree[x].ch[]].mark ^= ;
Tree[Tree[x].ch[]].mark ^= ;
Tree[x].mark = ;
swap(Tree[x].ch[] , Tree[x].ch[]);
}
}
void pushdown_all(int x){
if(nroot(x))
pushdown_all(Tree[x].fa);
pushdown(x);
}
inline void Splay(int x){
pushdown_all(x);
while(nroot(x)){
if(nroot(Tree[x].fa))
ZigZag(son(x) == son(Tree[x].fa) ? Tree[x].fa : x);
ZigZag(x);
}
}
inline void access(int x){
; x ; y = x , x = Tree[x].fa){
Splay(x);
Tree[x].size = Tree[x].size + Tree[Tree[x].ch[]].allSize - Tree[y].allSize;
Tree[x].ch[] = y;
pushup(x);
}
}
inline void makeroot(int x){
access(x);
Splay(x);
Tree[x].mark ^= ;
}
inline void split(int x , int y){
makeroot(x);
access(y);
Splay(y);
}
inline void link(int x , int y){
split(x , y);
Tree[x].fa = y;
Tree[y].size += Tree[x].allSize;
pushup(y);
}
inline char getc(){
char c = getchar();
while(!isupper(c))
c = getchar();
return c;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("4219.in" , "r" , stdin);
//freopen("4219.out" , "w" , stdout);
#endif
N = read();
; i <= N ; ++i)
Tree[i].allSize = ;
for(M = read() ; M ; --M)
if(getc() == 'A')
link(read() , read());
else{
int a = read() , b = read();
split(a , b);
printf("%lld\n" , 1ll * Tree[a].allSize * (Tree[b].allSize - Tree[a].allSize));
}
;
}