[BJOI2014]大融合

_Sein · 2019-08-08 19:57:56 · 题解

题面描述

题面不可描述

思路

貌似\operatorname{LCT}瞎搞维护一下虚儿子就行了。

但细节比较多啊。

通过瞎搞的规律，我们可以发现，答案貌似就是(x的儿子数+1)*(y的儿子数+1)。

经过询问操作的一系列操作，其实就等价于虚儿子 +1 * 虚儿子 +1

好了，就这么简单。

记得link的时候，将y调到所在辅助树的根节点，维护好状态再连。

AC code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=1e5+10;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar(x%10+48);
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node{int son[2],c,s,f;bool rv;}t[N<<1];
inline bool nroot(int p){return t[t[p].f].son[0]==p||t[t[p].f].son[1]==p;}
inline void update(int p){t[p].c=t[t[p].son[0]].c+1+t[p].s+t[t[p].son[1]].c;}
inline void crv(int p)
{
    if(!p)return;
    swap(t[p].son[0],t[p].son[1]);
    t[p].rv^=1;
}
void pushdown(int p)
{
    if(t[p].rv)
    {
        crv(t[p].son[1]),crv(t[p].son[0]);
        t[p].rv=0;
    }
}
void rotate(int p,int w)
{
    int f=t[p].f,gf=t[f].f;
    int r=t[p].son[w],R=f;t[R].son[w^1]=r;if(r)t[r].f=R;
    r=p;R=gf;if(nroot(f))t[R].son[t[R].son[1]==f]=r;t[r].f=R;
    r=f;R=p;t[R].son[w]=r;t[r].f=R;update(f);update(p);
}
void dfs(int p){if(nroot(p))dfs(t[p].f);pushdown(p);}
void splay(int p)
{
    for(dfs(p);nroot(p);)
    {
        int f=t[p].f,gf=t[f].f;
        if(!nroot(f))rotate(p,t[f].son[0]==p);
        else
        {
            if(t[f].son[0]==p&&t[gf].son[0]==f)rotate(f,1),rotate(p,1);
            else if(t[f].son[0]==p&&t[gf].son[1]==f)rotate(p,1),rotate(p,0);
            else if(t[f].son[1]==p&&t[gf].son[0]==f)rotate(p,0),rotate(p,1);
            else rotate(f,0),rotate(p,0);
        }
    }
}
void access(int x)
{
    for(int y=0;x;x=t[y=x].f)
    {
        splay(x);if(t[x].son[1])t[x].s+=t[t[x].son[1]].c;
        if((t[x].son[1]=y))t[x].s-=t[y].c;update(x);
    }
}
void makeroot(int x)
{
    access(x);splay(x);crv(x);
}
void link(int x,int y)
{
    makeroot(x);access(y);splay(y);t[x].f=y;//此时y不为根，信息得不到统计，因此需要access(y),splay(y); 
    t[y].s+=t[x].c;update(y);
}
void query(int x,int y)
{
    makeroot(x);access(y);splay(y);
    qw((t[x].s+1)*(t[y].s+1));puts("");
}
int main()
{
    int n,m;qr(n),qr(m);char s[10];
    while(m--)
    {
        int x,y;
        scanf("%s",s+1);qr(x),qr(y);
        if(s[1]=='A')link(x,y);
        else query(x,y);
    }
    return 0;
}