洛谷P4219 - [BJOI2014]大融合

Description

初始有\(n(n\leq10^5)\)个孤立的点，进行\(Q(Q\leq10^5)\)次操作：

连接边\((u,v)\)，保证\(u,v\)不连通。
询问有多少条简单路径经过边\((u,v)\)。

Solution

加边用lct，询问结果相当于\(p\)为根时的\((siz[p]-siz[q])\times siz[q]\)。

那么如何用lct维护子树大小呢？维护\(isiz[p]\)表示\(p\)在lct上的虚子树大小，\(siz[p]\)表示\(isiz[p]\)加上在辅助树上的实子树大小（子树大小也包括子树的虚子树和实子树）。当\(p=rt\)或\(p\)没有实子树时，\(siz[p]\)等于其原树上的子树大小。

如何维护\(isiz\)呢？只有当树的虚实划分变化时，\(isiz\)才会变化，也就是access和link。access(p)中有一句ch[p][1]=q，说明\(ch[p][1]\)变为虚子树，\(q\)变为实子树，则isiz[p]+=siz[ch[p][1]]-siz[q]。link(p,q)将\(p\)变为\(q\)的虚子树，因此\(q\)到\(q\)的根的\(isiz\)都要改变；因为不好实现所以makeRt(q)之后再连接，并isiz[q]+=siz[p]。

询问时，只要makeRt(p),access(q),splay(q)，此时\(q=rt\)，\(p\)没有实子树，\(siz\)均正确。

时间复杂度\(O(Qlogn)\)。

Code

//[BJOI2014]大融合

#include <cstdio>

#include <algorithm>

using namespace std;

int read()

{

    int x=0; char ch=getchar();

    while(ch<'0'||'9'<ch) ch=getchar();

    while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();

    return x;

}

int const N=1e5+10;

int n,Q;

int fa[N],ch[N][2],siz[N],isiz[N]; bool rev[N];

int wh(int p) {return p==ch[fa[p]][1];}

int notRt(int p) {return p==ch[fa[p]][wh(p)];}

void rever(int p) {rev[p]^=1; swap(ch[p][0],ch[p][1]);}

void update(int p) {siz[p]=siz[ch[p][0]]+siz[ch[p][1]]+isiz[p]+1;}

void pushdw(int p) {if(rev[p]) rever(ch[p][0]),rever(ch[p][1]),rev[p]=false;}

void rotate(int p)

{

    int q=fa[p],r=fa[q],w=wh(p);

    fa[p]=r; if(notRt(q)) ch[r][wh(q)]=p;

    fa[ch[q][w]=ch[p][w^1]]=q;

    fa[ch[p][w^1]=q]=p;

    update(q),update(p);

}

void pushdwRt(int p) {if(notRt(p)) pushdwRt(fa[p]); pushdw(p);}

void splay(int p)

{

    pushdwRt(p);

    for(int q=fa[p];notRt(p);rotate(p),q=fa[p]) if(notRt(q)) rotate(wh(p)^wh(q)?p:q);

}

void access(int p) {for(int q=0;p;q=p,p=fa[p]) splay(p),isiz[p]+=siz[ch[p][1]]-siz[q],ch[p][1]=q,update(p);}

void makeRt(int p) {access(p),splay(p),rever(p);}

void link(int p,int q) {makeRt(p),makeRt(q); fa[p]=q,isiz[q]+=siz[p]; update(q);}

long long query(int p,int q) {makeRt(p),access(q),splay(q); return (long long)siz[p]*(siz[q]-siz[p]);}

int main()

{

    n=read(),Q=read();

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

    for(int i=1;i<=Q;i++)

    {

        char opt[5]; scanf("%s",opt);

        int u=read(),v=read();

        if(opt[0]=='A') link(u,v);

        else printf("%lld\n",query(u,v));

    }

    return 0;

}

P.S.

比Icefox短了20行！

巴特西

洛谷P4219 - [BJOI2014]大融合

Description

Solution

Code

P.S.

最新文章

热门文章