对于每个询问$(u,v)$所求的是
（$u$的虚边子树大小+1）*（$v$的虚边子树大小+1）
于是我们再开个$si[i]$数组表示$i$的虚边子树大小，维护一下就好辣
#include<iostream> #include<cstdio> #include<cstring> using namespace std; inline void Swap(int &a,int &b){a^=b^=a^=b;} void read(int &x){ static char c=getchar();x=0; while(c<'0'||c>'9') c=getchar(); while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar(); } #define N 1000005 int n,m,ch[N][2],fa[N],s[N],si[N],rev[N]; #define lc ch[x][0] #define rc ch[x][1] inline bool nrt(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;} inline void up(int x){s[x]=s[lc]+s[rc]+si[x]+1;}//算上虚子树的大小 inline void Rev(int x){Swap(lc,rc),rev[x]^=1;} void down(int x){if(rev[x])Rev(lc),Rev(rc),rev[x]=0;} void Pre(int x){if(nrt(x))Pre(fa[x]); down(x);} void turn(int x){ int y=fa[x],z=fa[y],l=(ch[y][1]==x),r=l^1; if(nrt(y)) ch[z][ch[z][1]==y]=x; fa[ch[x][r]]=y; fa[y]=x; fa[x]=z; ch[y][l]=ch[x][r]; ch[x][r]=y; up(y); up(x); } void splay(int x){ Pre(x); for(;nrt(x);turn(x)){ int y=fa[x],z=fa[y]; if(nrt(y)) turn(((ch[z][1]==y)^(ch[y][1]==x))?x:y); } } void access(int x){ for(int y=0;x;y=x,x=fa[x]) splay(x),si[x]+=s[rc],rc=y,si[x]-=s[rc],up(x);///原来的rc变成了虚子树 } inline void makert(int x){access(x),splay(x),Rev(x);} inline void split(int x,int y){makert(x),access(y),splay(y);} inline void link(int x,int y){split(x,y),fa[x]=y,si[y]+=s[x];}//x向y连一条虚边，成为y的虚子树 int main(){ read(n);read(m); char opt[3]; int q1,q2; for(int i=1;i<=n;++i) s[i]=1; while(m--){ scanf("%s",opt); read(q1);read(q2); if(opt[0]=='Q'){ split(q1,q2),printf("%lld ",1ll*(si[q1]+1)*(si[q2]+1)); }else if(opt[0]=='A') link(q1,q2); }return 0; }