LCT维护子树并没有想象中的那么难，在这里只是复习下。
（其他的维护子树的题目，可见：“共价大爷游长沙”）
只要记录下虚边连接的信息就好了。
1 #include<bits/stdc++.h> 2 #define N 100010 3 typedef long long ll; 4 using namespace std; 5 int n,q,ans,tot,num; 6 struct Link_Cut_Tree{ 7 int c[N][2],fa[N],size1[N],size2[N],q[N],top,rev[N]; 8 inline void pushup(int x){ 9 int l=c[x][0],r=c[x][1]; 10 size1[x]=size1[l]+size1[r]+size2[x]; 11 } 12 inline bool isroot(int x){return c[fa[x]][1]!=x&&c[fa[x]][0]!=x;} 13 inline void pushdown(int x){ 14 int l=c[x][0],r=c[x][1]; 15 if(rev[x]){ 16 rev[l]^=1;rev[r]^=1;rev[x]^=1; 17 swap(c[x][0],c[x][1]); 18 } 19 } 20 inline void rotate(int x){ 21 int y=fa[x],z=fa[y],l,r; 22 if(c[y][0]==x)l=0;else l=1;r=l^1; 23 if(!isroot(y)){if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;} 24 fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 25 c[y][l]=c[x][r];c[x][r]=y; 26 pushup(y);pushup(x); 27 } 28 inline void splay(int x){ 29 top=1;q[top]=x; 30 for(int i=x;!isroot(i);i=fa[i])q[++top]=fa[i]; 31 for(int i=top;i;i--)pushdown(q[i]); 32 while(!isroot(x)){ 33 int y=fa[x],z=fa[y]; 34 if(!isroot(y)){ 35 if((c[z][0]==y)^(c[y][0]==x))rotate(x); 36 else rotate(y); 37 }rotate(x); 38 } 39 pushup(x); 40 } 41 void access(int x){ 42 for(int t=0;x;t=x,x=fa[x]){ 43 splay(x);size2[x]+=size1[c[x][1]]; 44 c[x][1]=t;size2[x]-=size1[t];pushup(x); 45 } 46 } 47 void makeroot(int x){access(x);splay(x);rev[x]^=1;} 48 int find(int x){access(x);splay(x);while(c[x][0])x=c[x][0];return x;} 49 void split(int x,int y){makeroot(x);access(y);splay(y);} 50 void link(int x,int y){ 51 makeroot(x);makeroot(y);fa[x]=y;size2[y]+=size1[x]; 52 pushup(y); 53 } 54 void cut(int x,int y){split(x,y);if(c[y][0]==x)c[y][0]=0,fa[x]=0;} 55 void init(int n){ 56 for(int i=1;i<=n;i++)size1[i]=size2[i]=1; 57 } 58 }T; 59 inline int read(){ 60 int f=1,x=0;char ch; 61 do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); 62 do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); 63 return f*x; 64 } 65 int main(){ 66 n=read();q=read(); 67 T.init(n);char s[10]; 68 while(q--){ 69 scanf("%s",s); 70 int x=read(),y=read(); 71 if(s[0]=='A')T.link(x,y); 72 else{ 73 T.makeroot(x);T.access(y);T.splay(x); 74 printf("%lld ",(ll)((T.size2[y])*(T.size1[x]-T.size2[y]))); 75 } 76 } 77 return 0; 78 }