洛谷 P4219 [BJOI2014]大融合 解题报告

P4219 [BJOI2014]大融合

题目描述

小强要在\(N\)个孤立的星球上建立起一套通信系统。这套通信系统就是连接\(N\)个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量。

现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的 询问。

输入输出格式

输入格式：

第一行包含两个整数 \(N, Q\),表示星球的数量和操作的数量。星球从 \(1\) 开始编号。

接下来的 \(Q\) 行，每行是如下两种格式之一：

• A x y 表示在 \(x\) 和 \(y\) 之间连一条边。保证之前 \(x\) 和 \(y\) 是不联通的。
• Q x y表示询问 \((x,y)\) 这条边上的负载。保证 \(x\) 和 \(y\) 之间有一条边。

输出格式：

对每个查询操作，输出被查询的边的负载。

说明

对于所有数据，\(1≤N,Q≤10^5\)

---

LCT维护子树信息，涨见识了。

\(sizx_i\)代表虚边连的儿子的大小。

然后\(updata\)这样写

void updata(int now){siz[now]=siz[ls]+siz[rs]+sizx[now]+1;}

然后是在\(access\)的时候修改一下虚边儿子大小，在\(link\)的时候要把两个树都选上去保证没得父亲，因为我们不想把被连的那个点的信息再向上更新。

维护最值可以在每个点开个平衡树

---

Code:

#include <cstdio>

#define ll long long

#define ls ch[now][0]

#define rs ch[now][1]

#define fa par[now]

const int N=1e5+10;

int ch[N][2],par[N],siz[N],sizx[N],tag[N],s[N],tot,tmp;

bool isroot(int now){return ch[fa][0]==now||ch[fa][1]==now;}

int identity(int now){return ch[fa][1]==now;}

void updata(int now){siz[now]=siz[ls]+siz[rs]+sizx[now]+1;}

void Reverse(int now){tag[now]^=1,tmp=ls,ls=rs,rs=tmp;}

void connect(int f,int now,int typ){ch[fa=f][typ]=now;}

void pushdown(int now)

{

    if(tag[now])

    {

        if(ls) Reverse(ls);

        if(rs) Reverse(rs);

        tag[now]^=1;

    }

}

void Rotate(int now)

{

    int p=fa,typ=identity(now);

    connect(p,ch[now][typ^1],typ);

    if(isroot(p)) connect(par[p],now,identity(p));

    else fa=par[p];

    connect(now,p,typ^1);

    updata(p),updata(now);

}

void splay(int now)

{

    while(isroot(now)) s[++tot]=now,now=fa;

    s[++tot]=now;

    while(tot) pushdown(s[tot--]);

    now=s[1];

    for(;isroot(now);Rotate(now))

        if(isroot(fa))

            Rotate(identity(now)^identity(fa)?now:fa);

}

void access(int now)

{

    for(int las=0;now;las=now,now=fa)

        splay(now),sizx[now]+=siz[rs]-siz[las],rs=las;

}

void evert(int now){access(now),splay(now),Reverse(now);}

void link(int u,int v){evert(u),access(v),splay(v),par[u]=v,sizx[v]+=siz[u],updata(v);}

void cat(int u,int v){evert(u),access(v),splay(v),ch[v][0]=par[u]=0,updata(v);}

int query(int now){access(now),splay(now);return siz[now];}

int n,q;

int main()

{

    scanf("%d%d",&n,&q);

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

    char op[3];

    for(int u,v,i=1;i<=q;i++)

    {

        scanf("%s%d%d",op,&u,&v);

        if(op[0]=='Q') cat(u,v),printf("%lld\n",1ll*query(u)*query(v)),link(u,v);

        else link(u,v);

    }

    return 0;

}

---

2018.12.7