LCT维护子树信息（
考虑维护两个值，一个虚子树信息，一个全部信息。
因为虚子树只有在link和access的时候改变，可以方便的维护。
具体可以康康代码。
近期考虑写点大代码题练练手。
//Love and Freedom. #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ll long long #define inf 20021225 #define fa(x) t[x].fa #define ls(x) t[x].son[0] #define rs(x) t[x].son[1] #define nrt(x) (ls(fa(x))==x||rs(fa(x))==x) #define N 100010 using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return f*s; } struct node{int cnt,sum,fa,son[2]; bool tag;}t[N]; void pushup(int x){t[x].sum=1+t[x].cnt+t[ls(x)].sum+t[rs(x)].sum;} void rotate(int x) { if(!nrt(x) || !x) return; int f=fa(x),gf=fa(f); int k=rs(f)==x,p=k^1; if(nrt(f)) t[gf].son[rs(gf)==f]=x; if(t[x].son[p]) t[t[x].son[p]].fa=f; t[f].son[k]=t[x].son[p]; t[x].son[p]=f; t[x].fa=gf; t[f].fa=x; pushup(f); pushup(x); } void pushdown(int x) { if(t[x].tag) { swap(ls(x),rs(x)); if(ls(x)) t[ls(x)].tag^=1; if(rs(x)) t[rs(x)].tag^=1; t[x].tag=0; } } void push(int x) { if(nrt(x)) push(fa(x)); pushdown(x); } void splay(int x) { push(x); while(nrt(x)) { int f=fa(x),gf=fa(f); if(nrt(gf)) (rs(f)==x)^(rs(gf)==f)?rotate(x):rotate(f); rotate(x); } } void access(int x) { int y=0; do { splay(x); t[x].cnt+=t[rs(x)].sum-t[y].sum; rs(x)=y; pushup(x); y=x; x=fa(x); }while(x); } void makeroot(int x) { access(x); splay(x); t[x].tag=1; } int getroot(int x) { access(x); splay(x); while(ls(x)) x=ls(x); return x; } void split(int x,int y) { makeroot(x); access(y); splay(y); } void link(int x,int y) { split(x,y); if(getroot(y)==x) return; t[x].fa=y; t[y].cnt+=t[x].sum; } ll calc(int x,int y) { split(x,y); return 1ll*t[x].sum*(t[y].sum-t[x].sum); } char ch[10]; int main() { int n=read(),m=read(); for(int i=1;i<=n;i++) t[i].sum=1; while(m--) { scanf("%s",ch); int x=read(),y=read(); if(ch[0]=='A') link(x,y); else printf("%lld\n",calc(x,y)); } return 0; }