[文章目录]
Description
n个点的树，q次操作，第一种操作，连接x，y，保证x,y之前不连通，第二种操作，查询经过某条边的简单路径个数。n,q<=10^5
LCT维护子树大小
s1表示splay中所有能爬到当前节点的节点个数，s2表示splay中不通过当前节点的儿子能爬到当前节点的节点个数。
操作的时候加些东西就好了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
typedef long long ll;
int n,m;
struct node
{
node *c[2],*fa;
int s1,s2;
bool tur;
node();
void pushup(){s1=c[0]->s1+c[0]->s2+c[1]->s1+c[1]->s2+1;}
void reverse(){swap(c[0],c[1]); tur^=1;}
void pushdown();
}*null=new node(),*t[N];
node::node()
{
c[0]=c[1]=fa=null?null:this;
s1=null?1:0; s2=0;
}
void node::pushdown()
{
if(tur)
{
if(c[0]!=null) c[0]->reverse();
if(c[1]!=null) c[1]->reverse();
tur=0;
}
}
bool isr(node *x){return x!=x->fa->c[0]&&x!=x->fa->c[1];}
void rotate(node *x)
{
node *y=x->fa; int l=(x==y->c[1]),r=l^1;
y->c[l]=x->c[r]; x->c[r]->fa=y;
x->c[r]=y; x->fa=y->fa;
if(!isr(y)) y->fa->c[y==y->fa->c[1]]=x;
y->fa=x; y->pushup(); x->pushup();
}
void downall(node *x)
{
if(!isr(x)) downall(x->fa);
x->pushdown();
}
void splay(node *x)
{
downall(x); node *y;
while(!isr(x))
{
y=x->fa;
if(!isr(y)) rotate((x==y->c[0])^(y==y->fa->c[0])?x:y);
rotate(x);
}
}
void access(node *x)
{
node *t=null;
while(x!=null)
{
splay(x);
x->s2=x->s2 -t->s1 -t->s2 +x->c[1]->s1 + x->c[1]->s2;
x->c[1]=t; x->pushup();
t=x; x=x->fa;
}
}
void moveroot(node *x){access(x); splay(x); x->reverse();}
void link(node *x,node *y)
{
moveroot(x); access(y); splay(y);
x->fa=y; y->s2+=x->s1+x->s2;
}
int main()
{
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=n;++i) t[i]=new node();
int x,y; char op[10];
while(m--)
{
scanf("%s%d%d",op,&x,&y);
if(op[0]=='A') link(t[x],t[y]);
else
{
moveroot(t[x]); access(t[y]); splay(t[y]);
printf("%lld\n",((ll)t[x]->s1+t[x]->s2)*(t[y]->s1+t[y]->s2-t[x]->s1-t[x]->s2));
}
}
return 0;
}