[NOI2021] 庆典题解

OUYE2020 · 2021-07-28 20:37:25 · 题解

我们先想想暴力做法怎么做。一个城市如果可以被算入答案里面，那么它一定既可以被起点通过正向边到达，又可以被终点通过反向边到达。所以我们每次可以走正向边标记起点可达的顶点，再走反向边标记终点可达的顶点，答案即为拥有双重标记的点的数量。

题目特别说了这个道路是有特点的，说明此处一定有性质，所以我们稍稍挖掘一下。如果我们把有向图缩点，就可以发现此图一定不存在 u\rightarrow y,v\rightarrow y 这样的路径，所以这个图一定有且仅有一个入度为 0 的点。以这个点为根，会发现整个图长得像一棵树，所有路径要么从父亲指向儿子，要么从祖先跨代指向儿孙。由于我们需要知道的是正图反图中起点和终点最多可以到达的节点，所以这种跨代的边显然没有任何用，删去或忽略即可。

关于如何建这棵树和去掉多余边，可以用拓扑排序，最后一条删掉的入边对应顶点即为父亲节点。

把这棵树建出来以后，起点可达的范围和终点跑反边可达的范围都十分规范了。起点可以到达的范围就是它的子树，终点跑反边可以到达的范围就是它到根节点的一条路径。

所以对于不额外加边的询问，我们就有了单次 O(1) 的解决办法：预处理每个点到根的路径上的节点总数（注意缩过点的一个节点可以包含多个原图上的点），然后每次先用DFS序判断终点是否在起点的子树内，然后简单地减一下即可。

那么对于额外加边的询问呢？假设加的一条边为 u\rightarrow v，如果 u 在起点的子树内，那么 v 所在的子树也可以从起点到达，也就是说，起点可达的范围可能会变成不包含的两棵子树。反过来对于终点，如果 v 在终点到根的路径上，那么点 u 到根的路径也会变为终点可达的范围，最终就有两条路径的范围。

我们通过这种添加范围的方法处理加入的两条边，并且把范围去重过后，起点可达的范围最多为三棵子树，终点可达的范围最多为三条到根的路径。这显然可以暴力枚举，把每棵子树下与路径重合的部分的贡献都算上。一次询问算上求 \rm LCA 的时间，最坏也就 O(27\cdot\log n)，好的话可以通过优化循环和 O(1)\,\rm LCA 做到 O(9)。

但是如果遇到上图的情况，先加入边 b 再加入边 a 的话，由于开始时 U_b 不在起点可达的范围，V_b 的子树不会算进去。这个好办，你把两条边来回多加入几次。反正只有两条边，做法多暴力都过得去。

总复杂度 O(n\log n+q\cdot 9)\sim O(n\log n+q\log n\cdot 27)。

代码

#include<bits/stdc++.h>//JZM yyds!!
#define ll long long
#define MAXN 300005
#define uns unsigned
using namespace std;
inline ll read(){
    ll x=0;bool f=1;char s=getchar();
    while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
    while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+s-'0',s=getchar();
    return f?x:-x;
}
int n,m,Q,k;
int u1,v1,u2,v2;
vector<int>G[MAXN],G_[MAXN],G__[MAXN];

int dfn[MAXN],NN,low[MAXN],bl[MAXN];
bool ist[MAXN];
stack<int>st;
int du[MAXN],num,siz[MAXN];

int fa[MAXN],f[MAXN][25],hd[MAXN],tl[MAXN],dp[MAXN],dep[MAXN],IN;

inline void tarjan(int x){
    low[x]=dfn[x]=++NN,st.push(x),ist[x]=1;
    for(uns i=0;i<G__[x].size();i++){
        int v=G__[x][i];
        if(!dfn[v])tarjan(v),low[x]=min(low[x],low[v]);
        else if(ist[v])low[x]=min(low[x],dfn[v]);
    }
    if(low[x]==dfn[x]){num++;
        while(!st.empty()&&dfn[st.top()]>=dfn[x])
            bl[st.top()]=num,ist[st.top()]=0,st.pop();
    }
}
queue<int>q;
int root;
inline void topu(){
    for(int i=1;i<=num;i++)if(!du[i])q.push(i),root=i;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(uns i=0;i<G_[u].size();i++){
            int v=G_[u][i];du[v]--;
            if(!du[v])
                G[u].push_back(v),fa[v]=u,q.push(v);
        }
    }
}
inline void dfs(int x){
    hd[x]=++IN,f[x][0]=fa[x];
    dp[x]=dp[fa[x]]+siz[x],dep[x]=dep[fa[x]]+1;
    for(int i=1;i<20;i++)f[x][i]=f[f[x][i-1]][i-1];
    for(uns i=0;i<G[x].size();i++)dfs(G[x][i]);
    tl[x]=IN;
}
inline int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=19;i>=0;i--)if(dep[f[u][i]]>=dep[v])u=f[u][i];
    if(u!=v){
        for(int i=19;i>=0;i--)
            if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
        u=fa[u];
    }
    return u;
}
vector<int>a,b;
inline void addedge(int u,int v){
    bool ok=0;
    for(uns i=0;i<a.size();i++)
        if(hd[u]>=hd[a[i]]&&hd[u]<=tl[a[i]])ok=1;
    if(ok){
        int h=0;
        for(uns i=0;i<a.size()&&h>=0;i++){
            if(hd[v]>=hd[a[i]]&&hd[v]<=tl[a[i]])h=-1;
            if(h>=0&&hd[a[i]]>hd[v]&&hd[a[i]]<=tl[v])h=1,a[i]=v;
        }
        for(uns i=0;i<a.size();i++){
            bool ok=1;
            for(uns j=0;j<i;j++)if(a[j]==a[i])ok=0;
            if(!ok)a.erase(a.begin()+i,a.begin()+i+1),i--;
        }
        if(h==0)a.push_back(v);
    }

    ok=0;
    for(uns i=0;i<b.size();i++)
        if(hd[b[i]]>=hd[v]&&hd[b[i]]<=tl[v])ok=1;
    if(ok){
        int h=0;
        for(uns i=0;i<b.size()&&h==0;i++){
            if(hd[b[i]]>=hd[u]&&hd[b[i]]<=tl[u])h=-1;
            if(h==0&&hd[u]>hd[b[i]]&&hd[u]<=tl[b[i]])h=1,b[i]=u;
        }
        if(h==0)b.push_back(u);
    }
}
signed main()
{
//  freopen("celebration.in","r",stdin);
//  freopen("celebration.out","w",stdout);
    n=read(),m=read(),Q=read(),k=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        G__[u].push_back(v);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(int x=1;x<=n;x++){
        siz[bl[x]]++;
        for(uns i=0;i<G__[x].size();i++){
            int v=G__[x][i];
            if(bl[v]!=bl[x])
                G_[bl[x]].push_back(bl[v]),du[bl[v]]++;
        }
    }
    topu(),dfs(root);
    for(int D=1;D<=Q;D++){
        int s=read(),t=read();
        a.clear(),b.clear(),u1=v1=u2=v2=0;
        a.push_back(bl[s]),b.push_back(bl[t]);
        if(k>0)u1=bl[read()],v1=bl[read()];
        if(k>1)u2=bl[read()],v2=bl[read()];
        if(u1==v1)u1=v1=0;
        if(u2==v2)u2=v2=0;
        if(u1)addedge(u1,v1);
        if(u2)addedge(u2,v2);
        if(u1)addedge(u1,v1);
        int ans=0;
        for(uns i=0;i<a.size();i++){
            for(uns j=0;j<b.size();j++){
                int c=a[i],d=b[j];
                if(hd[d]>=hd[c]&&hd[d]<=tl[c]){
                    int lc=fa[c],glc;
                    for(uns l=0;l<j;l++){
                        glc=lca(b[l],d);
                        if(dep[glc]>dep[lc])lc=glc;
                    }
                    ans+=dp[d]-dp[lc];
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

[NOI2021] 庆典 题解

代码

[NOI2021] 庆典题解