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

· · 题解

树链剖分+离线树转图

观察题面,我们发现关键边就是桥,如果没有删边操作,就是一道tarjan裸题了。虽然我们可以一边删边一边更新tarjan,但时间复杂度应该过不了。所以我们要换一种思路。

我们注意到题中一句话:"保证联通"。如果我们不断删边,又保证联通,那么整张图最后会变成什么样呢?明显会变成一棵树。树就是好东西了,很多数据结构都能在树上用。而且我们发现树上的边都是关键边,,所以我们可以先建一棵树,再在树上加边建图。

我们可以明显发现,只要在树上任意两点之间加了一条边就会形成一个环,而对于环上的边显然都不会是关键边。因为树上两点间路径确定,形成环后该路径上所有边就都不为关键边了,所以自然想到将整棵树的边权置为1,每次对于(u,v)加边就将u到v的路径上的所有边边权改为0。

边权转点权,树链剖分实现。查询就直接查询u到v路径上还有多少边边权为1就行了。

然后就是删边操作,删掉一条边又保证联通,显然只能删环上的边,即每次删边后关键边数量一定不减,(假设删边(u,v))若我们每次在u到v的路径上加1,显然无法最优,因为对于u到v路径上的边,不一定删掉(u,v)这条边就一定会让它变成关键边,有可能它还属于别的环。所以我们可以反向考虑,所有要删掉的边都先不加,相当于默认全部删完了,倒序查询询问后再一条一条加回去,这样就可以避免删边操作了。

离线所有操作再倒序实现。

当然删边并不一定会断掉所有环,还有的边连在树上形成环。所以在建树时用并查集维护保证只建出一棵树,再把没加但未来不会删掉的边用成环情况处理。

代码实现细节见代码。

#include <map>
#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct edge{
    int v,next;
}e[60001];
struct node{
    int t,a,b;
}dt[40001];//存查询,删边操作
int cnt,tot,head[30001],dep[30001],fa[30001],siz[30001],son[30001],top[30001],id[30001],dfn[30001],low[30001],x[100001],y[100001],add[120005],sum[120005];
bool vis[100001];//记录边是否在树中
map<pair<int,int>,bool> ma;//记录u到v的边会不会删
inline void adde(int u,int v)
{
    e[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
}
inline int findf(int x)
{
    return fa[x]==x?x:fa[x]=findf(fa[x]);
}
inline void find(int u)//树剖模板不解释
{
    siz[u]=1;
    for(int i=head[u];~i;i=e[i].next)
    {
        int v=e[i].v;
        if(v!=fa[u])
        {
            fa[v]=u;
            dep[v]=dep[u]+1;
            find(v);
            siz[u]+=siz[v];
            if(siz[v]>siz[son[u]])son[u]=v;
        }
    }
}
inline void dfs(int u,int fat)
{
    top[u]=fat;
    id[dfn[u]=++tot]=u;
    if(son[u])dfs(son[u],fat);
    for(int i=head[u];~i;i=e[i].next)
    {
        int v=e[i].v;
        if(v!=son[u]&&v!=fa[u])dfs(v,v);
    }
    low[u]=tot;
}
inline void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
inline void pushdown(int rt,int m)
{
    if(~add[rt])
    {
        add[rt<<1]=add[rt<<1|1]=add[rt];
        sum[rt<<1]=add[rt]*(m-(m>>1));
        sum[rt<<1|1]=add[rt]*(m>>1);
        add[rt]=-1;
    }
}
inline void build(int l,int r,int rt)//线段树初始赋值全为1
{
    add[rt]=-1;
    if(l==r)
    {
        sum[rt]=1;
        return;
    }
    int m=l+r>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
inline void update(int L,int R,int c,int l,int r,int rt)//线段树要建成区间赋值的类型
{
    if(L<=l&&r<=R)
    {
        add[rt]=c;
        sum[rt]=c*(r-l+1);
        return;
    }
    pushdown(rt,r-l+1);
    int m=l+r>>1;
    if(L<=m)update(L,R,c,lson);
    if(m<R)update(L,R,c,rson);
    pushup(rt);
}
inline int query(int L,int R,int l,int r,int rt)//线段树查询不解释
{
    if(L<=l&&r<=R)return sum[rt];
    pushdown(rt,r-l+1);
    int m=l+r>>1,ret=0;
    if(L<=m)ret+=query(L,R,lson);
    if(m<R)ret+=query(L,R,rson);
    return ret;
}
int main()
{
    memset(head,-1,sizeof head);
    int n=read(),m=read();
    for(int i=1;i<=m;++i)//记边
    {
        x[i]=read();
        y[i]=read();
    }
    int tim=0;
    while(1)//离线 处理
    {
        int t=read();
        if(!(~t))break;
        int a=read(),b=read();
        dt[++tim]=(node){t,a,b};
        if(!t)ma[make_pair(a,b)]=ma[make_pair(b,a)]=1;//要删掉的边先不建
    }
    for(int i=1;i<=n;++i)
        fa[i]=i;
    for(int i=1;i<=m;++i)
    {
        int u=findf(x[i]),v=findf(y[i]);
        if(!ma[make_pair(x[i],y[i])]&&fa[u]!=v)//建树,用并查集维护是否成树
        {
            fa[u]=v;
            adde(x[i],y[i]);
            adde(y[i],x[i]);
            vis[i]=1;//记录边已加入
        }//这样建树就会保证只生成一棵树,之后就可以直接加边成环,不需要像其他的做法一样修改树剖的dfs处和dfs3次。
    }
    memset(fa,0,sizeof fa);
    find(1);
    dfs(1,1);
    build(1,n,1);
    for(int i=1;i<=m;++i)
        if(!vis[i]&&!ma[make_pair(x[i],y[i])])//边未加入树中且未来不会被删加入图中成环处理
        {
            int a=x[i],b=y[i];
            while(top[a]!=top[b])
            {
                if(dep[top[a]]>dep[top[b]])swap(a,b);
                update(dfn[top[b]],dfn[b],0,1,tot,1);
                b=fa[top[b]];
            }
            if(dep[a]>dep[b])swap(a,b);
            update(dfn[a]+1,dfn[b],0,1,tot,1);
        }
    stack<int> q;
    for(int i=tim;i;--i)//倒序处理操作
    {
        int ans=0,t=dt[i].t,a=dt[i].a,b=dt[i].b;
        while(top[a]!=top[b])
        {
            if(dep[top[a]]>dep[top[b]])swap(a,b);
            if(t)ans+=query(dfn[top[b]],dfn[b],1,tot,1);
            else update(dfn[top[b]],dfn[b],0,1,tot,1);
            b=fa[top[b]];
        }
        if(dep[a]>dep[b])swap(a,b);
        if(t)q.push(ans+query(dfn[a]+1,dfn[b],1,tot,1));
        else update(dfn[a]+1,dfn[b],0,1,tot,1);
    }
    while(!q.empty())//因为是倒序处理操作,所以答案要倒序输出
    {
        printf("%d\n",q.top());
        q.pop();
    }
    return 0;
}

我是蒟蒻