洛谷2542 [AHOI2005]航线规划

题解 数据结构-树链剖分 图论-桥 省选/NOI-
题目链接 编辑文章

题意

给出一个无向图,有下列操作:

  1. $(1,a,b)$ ,查询 $a\rightarrow b$ 路径上桥的数量
  2. $(0,a,b)$ ,删除边 $(a,b)$ 。

保证无论航线如何被破坏,任意时刻任意两点都能够相互到达。

其中点数 $N\le 30000$ ,边数 $M\le 100000$ ,操作数 $Q\le 40000$ 。

题解

显然,桥的数量就是缩完点后两点间的树上距离,动态询问树上距离显然就是树剖了。

对于操作 $2$ ,可以通过离线逆向处理成加边操作。

在一棵树上,如果给没有边的两点加上了边,那就构成了环,相当于原先的桥都被取消掉了。可以通过把两点间边权修改为 $0$ 来实现。


对于样例:

5 5
1 2
1 3
3 4
4 5
4 2
1 1 5
0 4 2
1 5 1
-1

example

最初的状态 $(4,2)$ 是断开了的。所以 $5\rightarrow 1$ 距离显然是 $3$ 。

加上 $(4,2)$ 后就成环了,所以把 $4\rightarrow 2$ 距离消成 $0$ 。那么 $1\rightarrow 5$ 距离就只是 $1$ 了。


但显然最后的状态不一定是树,那么直接把环上距离全都消成 $0$ 即可。

具体的操作就是先对最后的状态忽略环跑出一棵树,然后用 $\text{dfs3}$ 把环上距离都消成 $0$ 。逆向遍历操作,对于操作 $1$ 直接查询距离,操作 $2$ 就把两点距离消为 $0$ 。

需要注意删边可能有重复,反过来说就是可能重复加边,所以用map去重。

剩下的就是标准的边权树剖模板了。

#include<bits/stdc++.h>
#define pr pair <int,int>

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*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to;
    bool ava;
} edge[200005];
struct Tree {
    int left,right,sum,delta;
} tree[120005];
map <pr,int> mp;
int cnt,head[30005],n,m,a,b,c,q[40005][3],qcnt,ans[40005],acnt;
int dfsord,id[30005],fa[30005],son[30005],deep[30005],top[30005],siz[30005];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].ava=1;
    head[u]=cnt;
    mp[make_pair(u,v)]=cnt;
}

inline void pushup(int x) { tree[x].sum=tree[x*2].sum+tree[x*2+1].sum; }

inline void pushdown(int x)
{
    tree[x*2].sum=tree[x*2+1].sum=0;
    tree[x*2].delta=tree[x*2+1].delta=1;
    tree[x].delta=0;
}

void build(int x,int l,int r)
{
    tree[x].left=l;
    tree[x].right=r;
    if (r-l==1) tree[x].sum=1;
    else
    {
        int mid=(l+r)>>1;
        build(x*2,l,mid);
        build(x*2+1,mid,r);
        pushup(x);
    }
}

void update(int x,int l,int r)
{
    if (l<=tree[x].left && r>=tree[x].right)
    {
        tree[x].sum=0;
        tree[x].delta=1;
    }
    else
    {
        if (tree[x].delta) pushdown(x);
        int mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) update(x*2,l,r);
        if (r>mid) update(x*2+1,l,r);
        pushup(x);
    }
}

int query(int x,int l,int r)
{
    if (l<=tree[x].left && r>=tree[x].right) return tree[x].sum;
    else
    {
        if (tree[x].delta) pushdown(x);
        int ans=0,mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) ans+=query(x*2,l,r);
        if (r>mid) ans+=query(x*2+1,l,r);
        return ans;
    }
}

void dfs1(int x,int f,int dep)
{
    fa[x]=f;
    deep[x]=dep;
    siz[x]=1;
    int mx=0;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (siz[y] || !edge[i].ava) continue;
        dfs1(y,x,dep+1);
        siz[x]+=siz[y];
        if (siz[y]>mx)
        {
            mx=siz[y];
            son[x]=y;
        }
    }
}

void dfs2(int x,int topf)
{
    top[x]=topf;
    id[x]=++dfsord;
    if (!son[x]) return;
    dfs2(son[x],topf);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (fa[y]!=x || y==son[x] || !edge[i].ava) continue;
        dfs2(y,y);
    }
}

inline void upRange(int u,int v)
{
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        update(1,id[top[u]],id[u]+1);
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    if (id[u]!=id[v]) update(1,id[u]+1,id[v]+1);
}

inline int qRange(int u,int v)
{
    int ans=0;
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        ans+=query(1,id[top[u]],id[u]+1);
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    if (id[u]!=id[v]) ans+=query(1,id[u]+1,id[v]+1);
    return ans;
}

void dfs3(int x) //找环把距离消为0
{
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (!edge[i].ava) continue;
        if (fa[y]==x) dfs3(y);
        if (deep[x]>deep[y] && fa[x]!=y) upRange(x,y);
    }
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    for (;;)
    {
        a=read(); if (a==-1) break; b=read(); c=read();
        if (!a) edge[mp[make_pair(b,c)]].ava=edge[mp[make_pair(c,b)]].ava=0; //删除
        q[++qcnt][0]=a; q[qcnt][1]=b; q[qcnt][2]=c;
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n+1);
    dfs3(1);
    for (int i=qcnt;i;i--)
    {
        int a=q[i][0],b=q[i][1],c=q[i][2];
        if (a) ans[++acnt]=qRange(b,c);
        else upRange(b,c);
    }
    for (int i=acnt;i;i--) printf("%d\n",ans[i]);
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。