Description:

给 $N$ 个点，支持连边操作，保证任意时刻是一棵树，询问经过某条边的简单路径的数量。

$1\le N \le 100000$

Solution:

$LCT$ 维护子树信息，需要记录子树大小，由于在 $LCT$ 中如果有一个点在原树中是一个点的父亲，则要么他们在一个辅助树中且父亲在儿子左边，要么儿子所在树的根的父亲是他的父亲，但父亲没有他所在树这个儿子。

因此记一个 $tot$ 表示他的虚儿子的大小， $siz$ 表示他的子树的大小，则 $siz_k=tot_k+siz_{lc}+siz_{rc}+1$ ，在 $access$ 时连了一个右儿子，原来的右儿子变成了虚儿子，新连的右儿子原来是虚儿子，这次变成了实儿子，则 $tot$ 加上原来的右儿子，减去新加的右儿子。在 $link$ 时连了一个 $father$ ，多加了一个虚儿子，则 $tot$ 应加上对应 $siz$ 。

对于询问边 $(u,v)$ 的容量时，先将 $makeroot(u)$ ，再 $access(v)$ ，再 $splay(u)$ ，则此时辅助树中只有 $u$ 和 $v$ ， $u$ 是根，则 $v$ 的全部子节点个数为 $tot_v$ ，因为 $v$ 只有虚儿子，而整个联通块中的节点个数是 $siz_u$ ，所以 $u$ 的子节点个数为 $siz_u-tot_v$ ，乘起来即可。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int read(){

	int res = 0;

	char c = getchar();

	while(c < '0' || c > '9')c = getchar();

	while('0' <= c && c <= '9')

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,q;

#define MAXN 100010

struct node

{

	int c[2],fa,siz,tot;

	bool rev;

	node(){rev = false;c[0] = c[1] = fa = siz = tot = 0;}

}t[MAXN];

inline void maintain(int k){t[k].siz = t[k].tot + t[t[k].c[0]].siz + t[t[k].c[1]].siz;return;}

inline bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

inline void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

inline int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

inline void rotate(int x){

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y)){t[z].c[fy] = x;}

	t[x].fa = z;

	connect(t[x].c[fx^1],y,fx);

	connect(y,x,fx^1);

	maintain(y);maintain(x);

	return;

}

void pushdown(int k){

	if(!t[k].rev)return;

	t[t[k].c[0]].rev ^= 1;t[t[k].c[1]].rev ^= 1;

	swap(t[k].c[0],t[k].c[1]);t[k].rev = false;

	return;

}

stack<int> s;

void splay(int x){

	s.push(x);

	for(int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(x))

	{

		int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

void access(int k){

	for(int i = 0;k;i = k,k = t[k].fa)

	{

		splay(k);

		t[k].tot += t[t[k].c[1]].siz;

		t[k].tot -= t[i].siz;

		t[k].c[1] = i;

		maintain(k);

	}

	return;

}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

void link(int x,int y){makeroot(x);makeroot(y);t[x].fa = y;t[y].tot += t[x].siz;maintain(y);return;}

char getc(){

	char c = getchar();

	while(c != 'A' && c != 'Q')c = getchar();

	return c;

}

int main()

{

	scanf("%d%d",&n,&q);

	for(int i = 1;i <= n;++i)t[i].siz = t[i].tot = 1; 

	char c;

	int a,b;

	for(int i = 1;i <= q;++i)

	{

		c = getc();a = read();b = read();

		if(c == 'A')

		{

			link(a,b);

		}

		else

		{

			makeroot(a);access(b);splay(a);

			cout << (long long)t[b].tot * (long long)(t[a].siz - t[b].tot) << endl;

		}

	}

	return 0;

}