题解:原来LCT也能维护子树信息,我太Naive了

用LCT维护当前子树节点个数

具体做法维护siz[x]=当前Splay子树和指向当前Splay子树的虚边所代表的节点个数

auxsiz[x]=指向x节点的虚边代表的节点个数

Link的时候x,y都要makeroot一下(针对我的写法)

然后就在LCT的基础上维护auxsiz即可

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100009; int n,TT; int fa[maxn]={0},ch[maxn][2]={0},siz[maxn]={0},auxsiz[maxn]={0},rev[maxn]={0};
inline bool isroot(int x){
return (ch[fa[x]][0]!=x)&&(ch[fa[x]][1]!=x);
}
inline void pushup(int x){
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1+auxsiz[x];
}
inline int son(int x){
if(ch[fa[x]][0]==x)return 0;
else return 1;
}
inline void pushdown(int x){
if(rev[x]){
rev[x]^=1;
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
swap(ch[x][0],ch[x][1]);
}
}
void Downfa(int x){
if(!isroot(x))Downfa(fa[x]);
pushdown(x);
} inline void Rotate(int x){
int y=fa[x];
int z=fa[y];
int b=son(x),c=son(y);
int a=ch[x][b^1];
if(!isroot(y))ch[z][c]=x;
fa[x]=z;
if(a)fa[a]=y;
ch[y][b]=a;
fa[y]=x;ch[x][b^1]=y;
pushup(y);pushup(x);
} void Splay(int x){
Downfa(x);
while(!isroot(x)){
int y=fa[x];
if(isroot(y)){
Rotate(x);
}else{
if(son(x)==son(y)){
Rotate(y);Rotate(x);
}else{
Rotate(x);Rotate(x);
}
}
}
} void Access(int x){
for(int t=0;x;){
Splay(x);
auxsiz[x]+=siz[ch[x][1]];
auxsiz[x]-=siz[t];
ch[x][1]=t;
pushup(x);
t=x;x=fa[x];
}
}
void Makeroot(int x){
Access(x);Splay(x);rev[x]^=1;
}
void Link(int x,int y){
Makeroot(x);Makeroot(y);fa[x]=y;
auxsiz[y]+=siz[x];pushup(y);
}
void Cut(int x,int y){
Makeroot(x);Access(y);Splay(y);
fa[ch[y][0]]=0;ch[y][0]=0;
pushup(y);
} int main(){
scanf("%d%d",&n,&TT);
for(int i=1;i<=n;++i)siz[i]=1;
while(TT--){
char opty=getchar();
int x,y;
while(opty!='Q'&&opty!='A')opty=getchar();
scanf("%d%d",&x,&y);
if(opty=='A'){
Link(x,y);
}else{
Cut(x,y);
Splay(x);Splay(y);
printf("%lld\n",1LL*siz[x]*siz[y]);
Link(x,y);
}
}
return 0;
}

  

05-27 19:12