P4219 [BJOI2014]大融合（LCT）

P4219 [BJOI2014]大融合

对于每个询问$(u,v)$所求的是

（$u$的虚边子树大小+1）*（$v$的虚边子树大小+1）

于是我们再开个$si[i]$数组表示$i$的虚边子树大小，维护一下就好辣

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

inline void Swap(int &a,int &b){a^=b^=a^=b;}

void read(int &x){

    static char c=getchar();x=;

    while(c<''||c>'') c=getchar();

    while(''<=c&&c<='') x=x*+(c^),c=getchar();

}

#define N 1000005

int n,m,ch[N][],fa[N],s[N],si[N],rev[N];

#define lc ch[x][0]

#define rc ch[x][1]

inline bool nrt(int x){return ch[fa[x]][]==x||ch[fa[x]][]==x;}

inline void up(int x){s[x]=s[lc]+s[rc]+si[x]+;}//算上虚子树的大小

inline void Rev(int x){Swap(lc,rc),rev[x]^=;}

void down(int x){if(rev[x])Rev(lc),Rev(rc),rev[x]=;}

void Pre(int x){if(nrt(x))Pre(fa[x]); down(x);}

void turn(int x){

    int y=fa[x],z=fa[y],l=(ch[y][]==x),r=l^;

    if(nrt(y)) ch[z][ch[z][]==y]=x;

    fa[ch[x][r]]=y; fa[y]=x; fa[x]=z;

    ch[y][l]=ch[x][r]; ch[x][r]=y;

    up(y); up(x);

}

void splay(int x){

    Pre(x);

    for(;nrt(x);turn(x)){

        int y=fa[x],z=fa[y];

        if(nrt(y)) turn(((ch[z][]==y)^(ch[y][]==x))?x:y);

    }

}

void access(int x){

    for(int y=;x;y=x,x=fa[x])

        splay(x),si[x]+=s[rc],rc=y,si[x]-=s[rc],up(x);///原来的rc变成了虚子树

}

inline void makert(int x){access(x),splay(x),Rev(x);}

inline void split(int x,int y){makert(x),access(y),splay(y);}

inline void link(int x,int y){split(x,y),fa[x]=y,si[y]+=s[x];}//x向y连一条虚边，成为y的虚子树

int main(){

    read(n);read(m); char opt[]; int q1,q2;

    for(int i=;i<=n;++i) s[i]=;

    while(m--){

        scanf("%s",opt); read(q1);read(q2);

        if(opt[]=='Q'){

            split(q1,q2),printf("%lld\n",1ll*(si[q1]+)*(si[q2]+));

        }else if(opt[]=='A') link(q1,q2);

    }return ;

}