1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include<bits/stdc++.h>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;
inline int read()
{
int data=0, w=1;
char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1, ch=getchar();
while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();
return data*w;
}
const int maxn(1e5+10);
int n, q;
int fa[maxn], son[2][maxn], size[maxn], vir[maxn], st[maxn], top;
bool rev[maxn];
inline bool isroot(int x) { return son[0][fa[x]]!=x&&son[1][fa[x]]!=x; }
inline bool get_son(int x) { return son[1][fa[x]]==x; }
inline void update(int x) { size[x]=size[son[0][x]]+size[son[1][x]]+vir[x]+1; }
inline void pushdown(int x)
{
if(rev[x])
{
rev[son[0][x]]^=1; rev[son[1][x]]^=1; rev[x]=0;
swap(son[0][x], son[1][x]);
}
}
inline void rotate(int x)
{
int f=fa[x], g=fa[f], l=get_son(x), r=l^1;
if(!isroot(f)) son[get_son(f)][g]=x;
fa[x]=g; fa[f]=x; fa[son[r][x]]=f;
son[l][f]=son[r][x]; son[r][x]=f;
update(f); update(x);
}
inline void splay(int x)
{
top=1; st[top]=x;
for(RG int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i];
for(RG int i=top;i;i--) pushdown(st[i]);
for(;!isroot(x);rotate(x)) if(!isroot(fa[x])) rotate(get_son(fa[x])^get_son(x)?x:fa[x]);
}
inline void access(int x)
{
for(RG int t=0;x;t=x, x=fa[x]) splay(x), vir[x]+=size[son[0][x]], vir[x]-=size[son[0][x]=t], update(x);
}
inline void makeroot(int x) { access(x); splay(x); rev[x]^=1; }
inline void split(int x, int y) { makeroot(x); access(y); splay(y); }
inline void link(int x, int y) { split(x, y); vir[fa[x]=y]+=size[x]; }
char s[3];
int a, b;
int main()
{
n=read(); q=read();
for(RG int i=1;i<=n;i++) size[i]=1;
while(q--)
{
scanf("%s", s); a=read(); b=read();
if(s[0]=='A') link(a, b);
else split(a, b), printf("%lld\n", 1ll*(vir[a]+1)*(vir[b]+1));
}
return 0;
}
|