P4219 [BJOI2014]大融合

动态维护森林

显然考虑 $LCT$

但是发现询问求的是子树大小，比较不好搞

维护 $sum[x]$ 表示节点 $x$ 的子树大小，$si[x]$ 表示 $x$ 的子树中虚儿子的子树大小和

那么 $pushup$ 可以这样写：

inline void pushup(int x) { sum[x]=sum[c[x][]]+sum[c[x][]]+si[x]+; }

考虑什么时候 $si$ 会变

首先对于 $rotate,splay$ 因为都是对一条实链搞，所以对虚边没影响

然后考虑 $access$ ，发现边的虚实有改变

原本 $x$ 的右儿子变成另一个节点，那么要记得更新

然后 $makeroot$ ，发现我们翻转的是一条实链，所以同样不会对虚边产生影响

然后 $split$ ，调用了 $makeroot,access,splay$ 这些之前都考虑过了

然后 $link$，发现多了一条虚边，所以要记得更新一下

然后 $cut$，因为断的是实边，所以不会改变

那么询问时只要 $makeroot(x),access(y),splay(y)$ ，然后 $y$ 的右儿子就是 $x$ ，输出 $(si[x]+1)*(si[y]+1)$ 即可

具体看代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+;

int c[N][],fa[N],si[N],sum[N];

bool rev[N];//维护的是延时标记

inline void pushup(int x) { sum[x]=sum[c[x][]]+sum[c[x][]]+si[x]+; }

inline void pushdown(int x)

{

    if(!x||!rev[x]) return;

    int &lc=c[x][],&rc=c[x][];

    swap(lc,rc); rev[x]=;

    if(lc) rev[lc]^=;

    if(rc) rev[rc]^=;

}

inline void rever(int x) { rev[x]^=; pushdown(x); }

inline bool notroot(int x) { return (c[fa[x]][]==x)|(c[fa[x]][]==x); }

inline void rotate(int x)

{

    int y=fa[x],z=fa[y],d=(c[y][]==x);

    if(notroot(y)) c[z][c[z][]==y]=x;

    fa[x]=z; fa[y]=x; fa[c[x][d^]]=y;

    c[y][d]=c[x][d^]; c[x][d^]=y;

    pushup(y); pushup(x);

}

void push_tag(int x)

{

    if(notroot(x)) push_tag(fa[x]);

    else pushdown(x);

    pushdown(c[x][]); pushdown(c[x][]);

}

inline void splay(int x)

{

    push_tag(x);

    while(notroot(x))

    {

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

        if(notroot(y))

        {

            if(c[z][]==y ^ c[y][]==x) rotate(x);

            else rotate(y);

        }

        rotate(x);

    }

}

inline void access(int x)

{

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

    {

        splay(x); si[x]+=(sum[c[x][]]-sum[y]);//记得更新si

        c[x][]=y; pushup(x);

    }

}

inline void makeroot(int x) { access(x); splay(x); rever(x); }

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

inline void link(int x,int y) { split(x,y); fa[x]=y; si[y]+=sum[x];/*更新si*/ pushup(y); }

inline void query(int x,int y)

{

    split(x,y);//和makeroot(x),access(y),splay(y)是同样的写法

    printf("%lld\n",1ll*(si[x]+)*(si[y]+));

}

int n,m;

int main()

{

    int a,b; char s[];

    n=read(); m=read();

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

    while(m--)

    {

        scanf("%s",s); a=read(),b=read();

        if(s[]=='A') link(a,b);

        else query(a,b);

    }

    return ;

}

巴特西

P4219 [BJOI2014]大融合

最新文章

热门文章