题解 P2542 【[AHOI2005]航线规划】

2018-06-06 21:49:06


题解在博客食用效果更佳哦~

楼下dalao的lct我并不会

只会蒻蒻的树剖qwq

Hint

我们保证无论航线如何被破坏,任意时刻任意两个星球都能够相互到达。在整个数据中,任意两个星球之间最多只可能存在一条直接的航线。

Solution

首先这题离线逆序处理不必多说了,这类删除点/边题固定套路

刚看到这题的想法是 $Tarjan$ 缩点然后怎么拓扑乱搞求一下距离

然而这是一个无向图并不存在拓扑序

然而我并不会求距离

我们注意到 $Hint$ 里面保证了这么一句话在整个数据中,任意两个星球之间最多只可能存在一条直接的航线。

题目保证不存在重边,而且互相连通,又是无向图...想到了什么?缩完点后的图是一棵树啊!

也就是说,我们需要动态的维护树上点之间的距离

树上把点连起来的是什么?边啊!

那么我们需要维护树上两点之间的边权不就行了!

想到了什么?树链剖分!

对,我们可以树剖维护树上的边权,这样就可以轻而易举的求出树上两点之间的距离了。

那...怎么动态缩点呢?

做这题时,我为这事纠结了半天...

然后才发现,既然能维护树上两点间距离,那还缩点干啥呢?

直接将一个环内的点之间的边权赋为0不就行了!

算法流程如下:

  1. 读入询问,逆序处理
  2. 先随便在原图中求出一棵生成树,我直接用 $dfs$ 序实现的
  3. 然后用那些没被删除的非树边先更新一遍当前的边权
  4. 树剖裸题。

因为是边权下放到点权,注意修改的时候不要改它们的 $lca$ !

Code

#include<map>
#include<cstdio>
#include<cctype>
#define N 30005
#define Q 40005
#define M 100005
#define max(A,B) ((A)>(B)?(A):(B))
#define min(A,B) ((A)<(B)?(A):(B))
#define swap(A,B) ((A)^=(B)^=(A)^=(B))

int n,m,d[N],ans[Q];
std::map<int,int> mp;
int cnt,tot,son[N],pos;
int val[N],head[N],fa[N];
int dfn[N],top[N],ques[Q][5];
int sze[N],sum[N<<2],lazy[N<<2];

struct Edge{
    int to,nxt,ok;
}edge[M<<1];

void add(int x,int y){
    edge[++cnt].to=y;
    edge[cnt].nxt=head[x];
    head[x]=cnt;
    mp[x*(n+1)+y]=cnt;;
}

int getint(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}

void first_dfs(int now){
    sze[now]=1;
    for(int i=head[now];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(sze[to] or edge[i].ok)
            continue;
        d[to]=d[now]+1;
        fa[to]=now;
        first_dfs(to);
        sze[now]+=sze[to];
        if(sze[to]>sze[son[now]])
            son[now]=to;
    }
}

void second_dfs(int now,int low){
    dfn[now]=++tot;
    top[now]=low;
    if(son[now])
        second_dfs(son[now],low);
    for(int i=head[now];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(fa[to]!=now or to==son[now] or edge[i].ok)
            continue;
        second_dfs(to,to);
    }
}

void pushup(int cur){
    sum[cur]=sum[cur<<1]+sum[cur<<1|1];
}

void build(int cur,int l,int r){
    if(l==r){
        sum[cur]=1;
        return;
    }
    int mid=l+r>>1;
    build(cur<<1,l,mid);
    build(cur<<1|1,mid+1,r);
    pushup(cur);
}

void pushdown(int cur){
    if(!lazy[cur])
        return;
    sum[cur<<1]=sum[cur<<1|1]=0;
    lazy[cur<<1]=lazy[cur<<1|1]=1;
    lazy[cur]=0;
}

void modify(int cur,int l,int r,int ql,int qr){
    if(ql<=l and r<=qr){
        sum[cur]=0;
        lazy[cur]=1;
        return;
    }
    pushdown(cur);
    int mid=l+r>>1;
    if(ql<=mid)
        modify(cur<<1,l,mid,ql,qr);
    if(mid<qr)
        modify(cur<<1|1,mid+1,r,ql,qr);
    pushup(cur);
}

void change(int x,int y){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])
            swap(x,y);
        modify(1,1,n,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(d[x]<d[y])
        swap(x,y);
    if(d[x]!=d[y])
        modify(1,1,n,dfn[y]+1,dfn[x]);
}

void third_dfs(int now){
    for(int i=head[now];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(edge[i].ok)
            continue;
        if(fa[to]==now)
            third_dfs(to);
        if(fa[now]!=to and d[to]<d[now])
            change(to,now);
    }
}

int query(int cur,int l,int r,int ql,int qr){
    if(ql<=l and r<=qr)
        return sum[cur];
    pushdown(cur);
    int mid=l+r>>1,now=0;
    if(ql<=mid)
        now+=query(cur<<1,l,mid,ql,qr);
    if(mid<qr)
        now+=query(cur<<1|1,mid+1,r,ql,qr);
    return now;
}

int ask(int x,int y){
    int now=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])
            swap(x,y);
        now+=query(1,1,n,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(d[x]<d[y])
        swap(x,y);
    now+=query(1,1,n,dfn[y],dfn[x]);
    now-=query(1,1,n,dfn[y],dfn[y]);
    return now;
}

signed main(){
    n=getint(),m=getint();
    for(int i=1;i<=m;i++){
        int x=getint(),y=getint();
        add(x,y); add(y,x);
    }
    while(1){
        int a=getint();
        if(a==-1) break;
        int b=getint(),c=getint();
        ques[++pos][1]=a;
        ques[pos][2]=b;
        ques[pos][3]=c;
        if(a==0)
            edge[mp[b*(n+1)+c]].ok=edge[mp[c*(n+1)+b]].ok=1;
    }
    d[1]=1;
    first_dfs(1);
    second_dfs(1,1);
    build(1,1,n);
    third_dfs(1);
    for(int i=pos;i;i--){
        if(ques[i][1])
            ans[i]=ask(ques[i][2],ques[i][3]);
        else
            change(ques[i][2],ques[i][3]);
    }
    for(int i=1;i<=pos;i++){
        if(ques[i][1]!=1) continue;
        printf("%d\n",ans[i]);
    }
    return 0;
}