Description

小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。

这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够

联通的树上路过它的简单路径的数量。

例如，在上图中，现在一共有了5条边。其中，(3,8)这条边的负载是6，因

为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。

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

询问。

Input

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

接下来的Q行，每行是如下两种格式之一：

A x y 表示在x和y之间连一条边。保证之前x和y是不联通的。

Q x y 表示询问(x,y)这条边上的负载。保证x和y之间有一条边。

1≤N,Q≤100000

Output

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

Sample Input

8 6

A 2 3

A 3 4

A 3 8

A 8 7

A 6 5

Q 3 8

Sample Output

6

Solution

一个讲lct维护子树讲的很好的

感觉很好理解，就是$pushup$的时候把虚树的也合并一下

就是很鸡肋，因为这样就不能维护边了

$Size$表示子树的全部信息，$Si$表示虚子树的信息

询问的时候就是边两个端点的子树和的乘积

此题$link$的时候要将$y~makeroot$不然信息就会错误（在这挂了好久

Code

1 #include
     
       2 #include
      
        3 #include
       
         4 #define N (100000+100) 5 using namespace std; 6  7 int Father[N],Son[N][2],Size[N],Si[N],Rev[N]; 8 int n,m,x,y; 9 char opt[10];10 11 int  Get(int x) {
   return Son[Father[x]][1]==x;}12 void Update(int x) {Size[x]=Si[x]+Size[Son[x][0]]+Size[Son[x][1]]+1;}13 int  Is_root(int x) {
   return Son[Father[x]][0]!=x && Son[Father[x]][1]!=x;}14 15 void Rotate(int x)16 {17     int wh=Get(x);18     int fa=Father[x],fafa=Father[fa];19     if (!Is_root(fa)) Son[fafa][Son[fafa][1]==fa]=x;20     Father[fa]=x; Son[fa][wh]=Son[x][wh^1];21     if (Son[fa][wh]) Father[Son[fa][wh]]=fa;22     Father[x]=fafa; Son[x][wh^1]=fa;23     Update(fa); Update(x);24 }25 26 void Pushdown(int x)27 {28     if (Rev[x] && x)29     {30         if (Son[x][0]) Rev[Son[x][0]]^=1;31         if (Son[x][1]) Rev[Son[x][1]]^=1;32         swap(Son[x][0],Son[x][1]);33         Rev[x]=0;34     }35 }36 37 void Push(int x) {
   if (!Is_root(x)) Push(Father[x]); Pushdown(x);}38 void Splay(int x)39 {40     for (int fa;!Is_root(x);Rotate(x))41         if (!Is_root(fa=Father[x]))42             Rotate(Get(fa)==Get(x)?fa:x);43 }44 45 void Access(int x) {
   for (int y=0;x;y=x,x=Father[x]) Splay(x), Si[x]+=Size[Son[x][1]], Si[x]-=Size[y], Son[x][1]=y, Update(x);}46 void Make_root(int x) {Access(x); Splay(x); Rev[x]^=1;}47 int  Find_root(int x) {Access(x); Splay(x); while (Son[x][0]) x=Son[x][0]; return x;}48 void Link(int x,int y) {Make_root(x); Make_root(y); Father[x]=y; Si[y]+=Size[x]; Update(y);}49 int Query(int x,int y)50 {51     Make_root(x);52     Access(y);53     Splay(y);54     int sum=Size[y];55     int sizex=Size[x];56     int sizey=sum-sizex;57     return sizex*sizey;58 }59 60 int main()61 {62     scanf("%d%d",&n,&m);63     for(int i=1;i<=n;++i) Size[i]=1;64     for (int i=1;i<=m;++i)65     {66         scanf("%s%d%d",opt,&x,&y);67         if (opt[0]=='A') Link(x,y);68         else printf("%d\n",Query(x,y));69     }70 }