[BZOJ1969] [AHOI2005]LANE 航线规划

2024-03-18 14:49:04

Description

对Samuel星球的探险已经取得了非常巨大的成就，于是科学家们将目光投向了Samuel星球所在的星系——一个巨大的由千百万星球构成的Samuel星系。星际空间站的Samuel II巨型计算机经过长期探测，已经锁定了Samuel星系中许多星球的空间坐标，并对这些星球从1开始编号1、2、3……。一些先遣飞船已经出发，在星球之间开辟探险航线。探险航线是双向的，例如从1号星球到3号星球开辟探险航线，那么从3号星球到1号星球也可以使用这条航线。例如下图所示：在5个星球之间，有5条探险航线。 A、B两星球之间，如果某条航线不存在，就无法从A星球抵达B星球，我们则称这条航线为关键航线。显然上图中，1号与5号星球之间的关键航线有1条：即为4-5航线。然而，在宇宙中一些未知的磁暴和行星的冲撞，使得已有的某些航线被破坏，随着越来越多的航线被破坏，探险飞船又不能及时回复这些航线，可见两个星球之间的关键航线会越来越多。假设在上图中，航线4-2（从4号星球到2号星球）被破坏。此时，1号与5号星球之间的关键航线就有3条：1-3，3-4，4-5。小联的任务是，不断关注航线被破坏的情况，并随时给出两个星球之间的关键航线数目。现在请你帮助完成。

Input

第一行有两个整数N，M。表示有N个星球（1< N < 30000），初始时已经有M条航线（1 < M < 100000）。随后有M行，每行有两个不相同的整数A、B表示在星球A与B之间存在一条航线。接下来每行有三个整数C、A、B。C为1表示询问当前星球A和星球B之间有多少条关键航线；C为0表示在星球A和星球B之间的航线被破坏，当后面再遇到C为1的情况时，表示询问航线被破坏后，关键路径的情况，且航线破坏后不可恢复； C为-1表示输入文件结束，这时该行没有A,B的值。被破坏的航线数目与询问的次数总和不超过40000。

Output

对每个C为1的询问，输出一行一个整数表示关键航线数目。注意：我们保证无论航线如何被破坏，任意时刻任意两个星球都能够相互到达。在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。

Sample Input

Sample Output

1
3

Solution

\(LCT\)维护边双连通分量模板题。

开个并查集维护边双联通分量，用\(LCT\)维护缩完点之后的联通情况就好了。

具体细节还是挺多的。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

const int maxn = 2e5+10;

int n,m;
int f[maxn],fa[maxn],son[maxn][2],sz[maxn],rev[maxn];
int ina[maxn],inb[maxn],inc[maxn],e1[maxn],e2[maxn];

#define ls son[x][0]
#define rs son[x][1]

#define sleep for(int i=1;i<=1e8;i++);

map<int,int > e[maxn];

int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}

int which(int x) {return son[fa[x]][1]==x;}
int nrt(int x) {return son[fa[x]][0]==x||son[fa[x]][1]==x;}

void update(int x) {sz[x]=sz[ls]+sz[rs]+1;}

void rotate(int x) {
    int y=fa[x],z=fa[y],w=which(x);
    if(nrt(y)) son[z][son[z][1]==y]=x;
    fa[x]=z,fa[y]=x,fa[son[x][w^1]]=y,son[y][w]=son[x][w^1],son[x][w^1]=y;
    update(y),update(x);
}

void push_rev(int x) {swap(ls,rs),rev[x]^=1;}
void pushdown(int x) {if(rev[x]) push_rev(ls),push_rev(rs),rev[x]=0;}

void push(int x) {if(nrt(x)) push(fa[x]);pushdown(x);}

void splay(int x) {
    push(x);
    for(;nrt(x);rotate(x)) if(nrt(fa[x])) rotate(which(fa[x])==which(x)?x:fa[x]);
    update(x);
}

void access(int x) {for(int t=0;x;splay(x),rs=t,update(t=x),x=fa[x]=find(fa[x]));}
//ATTENTION to the "x=fa[x]=find(fa[x])"

void make_root(int x) {access(x),splay(x),push_rev(x);}

int find_root(int x) {access(x),splay(x);pushdown(x);while(ls) pushdown(x=ls);return x;}

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

int query(int x,int y) {split(x=find(x),y=find(y));return sz[y]-1;}

void del(int x,int y) {if(x) f[x]=y,del(ls,y),del(rs,y);}

void link(int x,int y) {
    x=find(x),y=find(y);
    if(x==y) return ;
    make_root(x);
    if(find_root(y)!=x) fa[x]=y;
    else splay(x),del(rs,x),rs=0,update(x);
}

vector <int > ans;

int main() {
    read(n),read(m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1,x,y;i<=m;i++) read(x),read(y),e[x][y]=1,e[y][x]=1,e1[i]=x,e2[i]=y;
    int k,x,y,z;
    for(k=1;;k++) {
        read(x);
        if(x<0) {k--;break;}
        read(y),read(z);ina[k]=x,inb[k]=y,inc[k]=z;
        if(!x) e[y][z]=e[z][y]=0;
    }
    for(int i=1;i<=m;i++) if(e[e1[i]][e2[i]]) link(e1[i],e2[i]);
    for(int i=k;i;i--) {
        if(ina[i]) ans.push_back(query(inb[i],inc[i]));
        else link(inb[i],inc[i]);
    }
    reverse(ans.begin(),ans.end());
    for(vector <int > :: iterator i=ans.begin();i!=ans.end();i++) write(*i);
    return 0;
}

码农公寓