「题解」「TJOI2008」通讯网破坏

一道 Tarjan 的好题,或者说 圆方树 的入门题?

题目链接:Luogu P3854/TJOI2008 D1T1。

题目

题目描述

$n$ 个点 $m$ 条边的无向连通图,$Q$ 次询问,求出删去编号为 $M_i$ 的点后 $S_i,T_i$ 是否连通。

数据范围

变量数据范围
$n$$1\leq n\leq 2\times 10^4$
$m$$1\leq m\leq 10^5$
$Q$$1\leq Q\leq 10^5$

时空限制

题目时间限制空间限制
Luogu P3854$$2\text{s}$$$$125\text{MiB}$$
TJOI2008 D1T1$$?\text{s}$$$$?\text{MiB}$$

题解

思路

先考虑 $S_i,T_i,M_i$ 的分布情况。

  • $M_i$ 在一个环上
    无论删不删都不会影响整个图的连通性。
  • $M_i$ 在普通的边上
    $S_i,T_i$ 在同侧,则连通。
    否则不连通。

当年的正解好像是这么做的(我一开始也是这么想的),但这样考虑太麻烦,于是神仙们发明了圆方树(对,元芳树)

把每个大小不为 $1$ 的点双连通分量进行转化,将每个点都与一个虚拟的节点连接,然后断开所有点双连通分量上原有的边,就在保留了上述性质的同时把图简化成了一颗树。

举个例子:

下面这个图:

转化后就变成了(虚线表示删掉的边)。

求点双连通分量的过程比较毒瘤,大家自己留意代码。

转化后只需要判断 $M_i$ 在不在 $S_i$ 到 $T_i$ 的路径上即可,我用的是树链剖分,标记整段路径,再单点查询(因为我懒)。

代码

代码的渐进时间复杂度为 $\Theta(Q\log_2^2n)$。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=20000+5;
const int MAXM=100000+5;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n,m;
int c[MAXM],d[MAXM];
vector<int> V[MAXN<<1];

inline void Add_Tube(int u,int v){
    V[u].push_back(v);
    V[v].push_back(u);
    return;
}

inline void Read(void){
    n=read(),m=read();
    for(reg int i=1;i<=m;++i){
        c[i]=read(),d[i]=read();
        Add_Tube(c[i],d[i]);
    }
    return;
}

int tim,dfn[MAXN<<1],low[MAXN<<1];
stack<int> S;
int fa[MAXN<<1];
int Tarjan_cnt;
vector<int> BCC[MAXN];

inline void Tarjan(int ID,int father){
    dfn[ID]=low[ID]=++tim;
    S.push(ID);
    for(reg int i=0,size=V[ID].size();i<size;++i)
        if(V[ID][i]!=father){
            if(!dfn[V[ID][i]]){
                Tarjan(V[ID][i],ID);
                low[ID]=min(low[ID],low[V[ID][i]]);
                if(low[V[ID][i]]>=dfn[ID]){
                    ++Tarjan_cnt;
                    while(S.top()!=V[ID][i]){
                        BCC[Tarjan_cnt].push_back(S.top());
                        S.pop();
                    }
                    BCC[Tarjan_cnt].push_back(S.top());
                    S.pop();
                    BCC[Tarjan_cnt].push_back(ID);
                }
            }
            else
                low[ID]=min(low[ID],dfn[V[ID][i]]);
        }
    return;
}

int dep[MAXN<<1];
int size[MAXN<<1],son[MAXN<<1];

inline void DFS1(reg int ID,reg int father){
    size[ID]=1;
    fa[ID]=father;
    dep[ID]=dep[father]+1;
    for(reg int i=0;i<(int)V[ID].size();++i)
        if(V[ID][i]!=father){
            DFS1(V[ID][i],ID);
            size[ID]+=size[V[ID][i]];
            if(size[V[ID][i]]>size[son[ID]])
                son[ID]=V[ID][i];
        }
    return;
}

int top[MAXN<<1];

inline void DFS2(reg int ID,reg int father,reg int topf){
    dfn[ID]=++tim;
    top[ID]=topf;
    if(son[ID])
        DFS2(son[ID],ID,topf);
    for(reg int i=0,size=V[ID].size();i<size;++i){
        if(V[ID][i]!=father&&V[ID][i]!=son[ID]){
            DFS2(V[ID][i],ID,V[ID][i]);
        }
    }
    return;
}

struct SegmentTree{
    #define lson ( (k) << 1 )
    #define rson ( (k) << 1 | 1 )
    #define mid ( ( (l) + (r) ) >> 1 )
    struct Node{
        int val,tag;
    };
    Node unit[MAXN<<3];
    inline void pushup(reg int k){
        unit[k].val=unit[lson].val+unit[rson].val;
        return;
    }
    inline void Add(reg int k,reg int l,reg int r,reg int val){
        unit[k].val+=(r-l+1)*val;
        unit[k].tag+=val;
        return;
    }
    inline void pushdown(reg int k,reg int l,reg int r){
        if(unit[k].tag){
            Add(lson,l,mid,unit[k].tag);
            Add(rson,mid+1,r,unit[k].tag);
            unit[k].tag=0;
        }
        return;
    }
    inline void Update(reg int k,reg int l,reg int r,reg int L,reg int R,reg int val){
        if(L<=l&&r<=R){
            Add(k,l,r,val);
            return;
        }
        pushdown(k,l,r);
        if(L<=mid)
            Update(lson,l,mid,L,R,val);
        if(R>mid)
            Update(rson,mid+1,r,L,R,val);
        pushup(k);
        return;
    }
    inline int Query(reg int k,reg int l,reg int r,reg int pos){
        if(l==r&&l==pos){
            return unit[k].val;
        }
        pushdown(k,l,r);
        reg int res=0;
        if(pos<=mid)
            res=Query(lson,l,mid,pos);
        if(pos>mid)
            res=Query(rson,mid+1,r,pos);
        return res;
    }
    #undef lson
    #undef rson
    #undef mid
};

SegmentTree T;

inline void Update(int x,int y,reg int val){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        T.Update(1,1,n+Tarjan_cnt,dfn[top[x]],dfn[x],val);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    T.Update(1,1,n+Tarjan_cnt,dfn[x],dfn[y],val);
    return;
}

inline int Query(reg int x){
    return T.Query(1,1,n+Tarjan_cnt,dfn[x]);
}

inline void Work(void){
    Tarjan(1,0);
    for(reg int i=1;i<=n;++i)
        V[i].clear();
    for(reg int i=1;i<=Tarjan_cnt;++i)
        for(reg int j=0;j<(int)BCC[i].size();++j)
            Add_Tube(n+i,BCC[i][j]);
    DFS1(1,0);
    tim=0;
    DFS2(1,0,1);
    reg int Q=read();
    while(Q--){
        static int s,t,m;
        s=read(),t=read(),m=read();
        Update(s,t,1);
        reg int ans=Query(m);
        puts(ans?"yes":"no");
        Update(s,t,-1);
    }
    return;
}