「BZOJ4530」[BJOI2014]大融合

Description

小强要在 NN 个孤立的星球上建立起一套通信系统。这套通信系统就是连接 NN 个点的一个树。这个树的边是一条一条添加上去的。在某个时刻,一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。

例如,在上图中,现在一共有五条边。其中,(3,8)(3,8) 这条边的负载是 66,因为有六条简单路径 238, 2387, 38, 387, 438, 43872-3-8,\ 2-3-8-7,\ 3-8,\ 3-8-7,\ 4-3-8,\ 4-3-8-7 路过了 (3,8)(3,8)

现在,你的任务就是随着边的添加,动态的回答小强对于某些边的负载的询问。

Input

第一行包含两个整数 N,QN,Q,表示星球的数量和操作的数量。星球从 11 开始编号。

接下来的 QQ 行,每行是如下两种格式之一:
A x y 表示在 xxyy 之间连一条边。保证之前 xxyy 是不联通的。
Q x y 表示询问 (x,y)(x,y) 这条边上的负载。保证 xxyy 之间有一条边。

Output

对每个查询操作,输出被查询的边的负载。

Sample Input

1
2
3
4
5
6
7
8 6
A 2 3
A 3 4
A 3 8
A 8 7
A 6 5
Q 3 8

Sample Output

1
6

HINT

对于所有数据,1N,Q1000001 \leq N,Q \leq 100000

Solution

Lct维护子树的信息。
sixsi_x表示所有虚儿子的大小之和。
splaysplaylinklinkcutcut操作的时候要更新sisi
(six+1)(siy+1)(si_x+1)\cdot(si_y+1)sx(sysx)s_x\cdot(s_y-s_x)是等价的。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 210000;
struct Link_cut_tree {
int ch[N][2], tot, s[N], si[N], fa[N];
bool nr(int x) {
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
bool ident(int x) {
return ch[fa[x]][1] == x;
}
void con(int x, int F, int how) {
ch[F][how] = x;
fa[x] = F;
}
void up(int x) {
s[x] = si[x] + s[ch[x][0]] + s[ch[x][1]] + 1;
}
void rotate(int x) {
if(ident(x)) {
int y = fa[x];
int z = ch[x][0];
fa[x] = fa[y];
if(nr(y)) con(x, fa[y], ident(y));
con(y, x, 0);
con(z, y, 1);
up(y); up(x);
} else {
int y = fa[x];
int z = ch[x][1];
fa[x] = fa[y];
if(nr(y)) con(x, fa[y], ident(y));
con(y, x, 1);
con(z, y, 0);
up(y); up(x);
}
}
bool r[N];
void down(int x) {
if(r[x]) {
r[ch[x][0]] ^= 1;
r[ch[x][1]] ^= 1;
swap(ch[x][0], ch[x][1]);
r[x] = 0;
}
}
int st[N], top;
void splay(int x) {
int y = x;
top = 0;
while(nr(y)) st[++top] = y, y = fa[y];
st[++top] = y;
while(top) down(st[top--]);
for(int y = fa[x]; nr(x); y = fa[x]) {
if(nr(y)) rotate(ident(x) == ident(y) ? y :x);
rotate(x);
}
}
void access(int x) {
for(int y = 0; x; x = fa[y = x]) {
splay(x);
si[x] += s[ch[x][1]];
si[x] -= s[y];
ch[x][1] = y;
up(x);
}
}
void makeroot(int x) {
access(x);
splay(x);
r[x] ^= 1;
}
void link(int x, int y) {
makeroot(x);
access(y);//否则父亲的s都要改
splay(y);
si[y] += s[x];
fa[x] = y;
up(y);
}
ll query(int x, int y) {
makeroot(x);
access(y);
splay(y);
//return (ll)(si[y] + 1) * (si[x] + 1);
return(ll)s[x] * (s[y] - s[x]);
}
}lct;


int n, m;
char op[4];
int main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i) lct.s[i] = 1;
for(int T = 1; T <= m; ++T) {
scanf("%s", op);
int x = read(), y = read();
if(op[0] == 'A') {
lct.link(x, y);
} else {
writeln(lct.query(x, y));
}
}
return 0;
}