[BJOI2014] 大融合

一道不怎么裸的LCT。

题目传送门（洛谷P4219）

这道题明显是询问一条边所连接的两个连通块的大小之积。

LCT怎么维护子树大小呢？

推荐一个大佬的博客（传送门）：大佬的这篇博客有详解也有题，真心很棒的。

回到LCT，维护子树信息的话，我的理解就是把虚子树的信息也记录下来。

更新子树信息的时候把虚子树的也加进去。

至于怎么维护虚子树信息：

access和link的时候改变了树的形态，所以要顺便更新一下虚子树的信息。

access的时候是失去一个虚儿子又得到一个虚儿子。

link的时候连完边就顺手更新了。

别的操作没改变树的形态，所以虚子树信息不会变，代码跟原来一模一样的。

所以这道题现在就基本上也是裸题啦。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  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
",(long long)(szi[x]+1)*(szi[y]+1));
118         }
119     }
120     return 0;
121 }