一道不怎么裸的LCT。
这道题明显是询问一条边所连接的两个连通块的大小之积。
LCT怎么维护子树大小呢？
推荐一个大佬的博客（）：大佬的这篇博客有详解也有题，真心很棒的。
回到LCT，维护子树信息的话，我的理解就是把虚子树的信息也记录下来。
更新子树信息的时候把虚子树的也加进去。
至于怎么维护虚子树信息：
access和link的时候改变了树的形态，所以要顺便更新一下虚子树的信息。
access的时候是失去一个虚儿子又得到一个虚儿子。
link的时候连完边就顺手更新了。
别的操作没改变树的形态，所以虚子树信息不会变，代码跟原来一模一样的。
所以这道题现在就基本上也是裸题啦。
1 #include2 #include 3 #include 4 #define id(x) (s[f[x]][1]==x) 5 using namespace std; 6 7 int n,m; 8 int s[100005][2],f[100005],szi[100005],sz[100005]; 9 bool rt[100005],rev[100005]; 10 11 void pushup(int p) 12 { 13 sz[p]=sz[s[p][0]]+sz[s[p][1]]+szi[p]+1; 14 } 15 16 void reverse(int p) 17 { 18 swap(s[p][0],s[p][1]); 19 rev[p]^=1; 20 } 21 22 void pushdown(int p) 23 { 24 if(!rev[p])return; 25 reverse(s[p][0]); 26 reverse(s[p][1]); 27 rev[p]=0; 28 } 29 30 void down(int p) 31 { 32 if(!rt[p])down(f[p]); 33 pushdown(p); 34 } 35 36 void rotate(int p) 37 { 38 int k=id(p); 39 int fa=f[p]; 40 if(rt[fa])rt[p]=1,rt[fa]=0; 41 else s[f[fa]][id(fa)]=p; 42 s[fa][k]=s[p][!k]; 43 s[p][!k]=fa; 44 f[p]=f[fa]; 45 f[fa]=p; 46 f[s[fa][k]]=fa; 47 pushup(fa); 48 pushup(p); 49 } 50 51 void splay(int p) 52 { 53 down(p); 54 while(!rt[p]) 55 { 56 int fa=f[p]; 57 if(rt[fa]) 58 { 59 rotate(p); 60 return; 61 } 62 if(id(p)^id(fa))rotate(p); 63 else rotate(fa); 64 rotate(p); 65 } 66 } 67 68 void access(int p) 69 { 70 int son=0; 71 while(p) 72 { 73 splay(p); 74 szi[p]+=sz[s[p][1]]; 75 rt[s[p][1]]=1,rt[son]=0; 76 s[p][1]=son; 77 szi[p]-=sz[s[p][1]]; 78 pushup(p); 79 son=p,p=f[p]; 80 } 81 } 82 83 void mtr(int p) 84 { 85 access(p); 86 splay(p); 87 reverse(p); 88 } 89 90 void isolate(int x,int y) 91 { 92 mtr(x); 93 access(y); 94 splay(y); 95 } 96 97 int main() 98 { 99 scanf("%d%d",&n,&m);100 for(int i=1;i<=n;i++)sz[i]=rt[i]=1;101 for(int i=1;i<=m;i++)102 {103 char op[5];104 scanf("%s",op+1);105 int x,y;106 scanf("%d%d",&x,&y);107 if(op[1]=='A')108 {109 isolate(x,y);110 f[x]=y;111 szi[y]+=sz[x];112 pushup(y);113 }114 if(op[1]=='Q')115 {116 isolate(x,y);117 printf("%lld\n",(long long)(szi[x]+1)*(szi[y]+1));118 }119 }120 return 0;121 }