题目描述
输入
输出
样例输入
8 6
A 2 3
A 3 4
A 3 8
A 8 7
A 6 5
Q 3 8
样例输出
6
题解
LCT维护子树信息
学了大神的LCT维护子树信息的方式，觉得还算好理解，于是自己yy了这道题。
我们知道，在LCT中的Splay Tree中，access某个点并splay到根，那么它的实儿子记录的信息是这条链的信息，并不是我们想要的子树信息。
而所有实儿子和虚儿子的信息才是我们想要求的子树信息。
但是由于虚儿子“儿子认爹，爹不认儿子”的性质，无法在pushup的时候上传信息。
事实上，我们注意到，对于Splay Tree的所有基本操作，除了access和link以外，都不会对虚儿子的信息进行修改。
那么我们每次在添加虚儿子时，顺便把虚儿子的信息也记录到父亲节点中。
这样我们每次调用一个节点时，将它Splay Tree中实儿子的信息，加上它自身的虚儿子的信息，就是我们想要的子树信息。
于是我们对于每个节点记录两个信息：它的总信息和它虚儿子的信息，pushup时更新x的总信息为：x实儿子的总信息+x虚儿子的信息+x本身的信息。
按照这种方法我们来思考这道题，可以发现所求的答案就是一条边两端点的子树大小乘积，我们把某一个端点定为整棵树的根，可以知道整棵树的大小，而根据另一个节点可以知道一个子树的大小，相减即为另一个子树的大小。
具体的实现：
access操作中割断了实边c[1][x]，该边变为了虚边，所以应该加到x的虚儿子信息中，加入了实边t，该边不再是虚边，所以应从x的虚儿子信息中减去。
link操作中为了在加入x时同时更新y的信息，需要makeroot(x),makeroot(y)，然后连x->y的虚边（实际上只需要access(y)和splay(y)）。
其余的操作，和普通的LCT没有任何区别。
代码中需要注意的是，sum[x]存的是总信息（子树大小），si[x]存的是虚儿子信息（子树除了链以外的大小），不要弄混。
#include <cstdio>
#include <algorithm>
#define N 100010
using namespace std;
int fa[N] , c[2][N] , si[N] , sum[N] , rev[N];
char str[5];
void pushup(int x)
{
sum[x] = sum[c[0][x]] + sum[c[1][x]] + si[x] + 1;
}
void pushdown(int x)
{
if(rev[x])
{
int l = c[0][x] , r = c[1][x];
swap(c[0][l] , c[1][l]) , swap(c[0][r] , c[1][r]);
rev[l] ^= 1 , rev[r] ^= 1 , rev[x] = 0;
}
}
bool isroot(int x)
{
return c[0][fa[x]] != x && c[1][fa[x]] != x;
}
void update(int x)
{
if(!isroot(x)) update(fa[x]);
pushdown(x);
}
void rotate(int x)
{
int y = fa[x] , z = fa[y] , l = (c[1][y] == x) , r = l ^ 1;
if(!isroot(y)) c[c[1][z] == y][z] = x;
fa[x] = z , fa[y] = x , fa[c[r][x]] = y , c[l][y] = c[r][x] , c[r][x] = y;
pushup(y) , pushup(x);
}
void splay(int x)
{
update(x);
while(!isroot(x))
{
int y = fa[x] , z = fa[y];
if(!isroot(y))
{
if((c[0][y] == x) ^ (c[0][z] == y)) rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x)
{
int t = 0;
while(x) splay(x) , si[x] += sum[c[1][x]] - sum[t] , c[1][x] = t , pushup(x) , t = x , x = fa[x];
}
void makeroot(int x)
{
access(x) , splay(x) , swap(c[0][x] , c[1][x]) , rev[x] = 1;
}
void split(int x , int y)
{
makeroot(x) , makeroot(y);
}
void link(int x , int y)
{
split(x , y) , fa[x] = y , si[y] += sum[x] , pushup(y);
}
int main()
{
int n , m , i , x , y;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ ) sum[i] = 1;
while(m -- )
{
scanf("%s%d%d" , str , &x , &y);
if(str[0] == 'A') link(x , y);
else split(x , y) , printf("%lld\n" , (long long)sum[x] * (sum[y] - sum[x]));
}
return 0;
}