[省选联考 2021 A 卷] 支配题解

lindongli2004 · 2021-04-13 12:31:28 · 题解

题意本身就已经够简洁的了，所以这里不再复述。

首先建一棵支配树（建法在最下面），那么一个点 u 的受支配集 D_v 即为它到根的路径上的所有点组成的集合，那么如果我们连一条边使得某一个点 u 的支配集改变：首先，u 的支配集不会增大，那只能是 u 的某个支配树上的祖先不再支配 u 了。进一步地等价于，存在一条路径，不经过 u 的某个祖先可以直接到达 u。

那么如果只经过原图上的边，是不可能存在这样的路径的，所以一定要经过新加的有向边 (x,y) 才行。那么一个对答案有贡献的点 u，从 1 出发到它的路径都形如：1\to x \to y \to u （前后两个 \to 代表一条路径，中间一个 \to 代表一条边），且这条路径不经过 u 的某一个祖先。

祖先这个限制不好处理，那进一步地，如果可以转化为不经过 u 在支配树上的父亲就好了。很幸运，我们可以完成这个转化。具体地，对于一个点 u，我们找到这个点最浅的满足这个条件的祖先 v，那么 v 的支配集肯定会发生改变，v 子树内所有点的支配集也都会发生改变！所以一个点的支配集改变，会影响一个子树。

所以问题又转化为，如果存在一条路径 1\to x \to y \to u 不经过点 u 的父亲，那么 u 子树内所有点都会对答案产生贡献（支配集都会发生改变），问有多少个点会产生贡献。那么这个问题就很简单了，我们先预处理出一个点 u，把 u 的父亲从原图的反图（把原图的有向边取反）中删去，u 能到达哪些点。那么它就可能对这些点产生贡献。对于一组询问 (x,y)，我们只需要枚举所有可能对 y 产生贡献的点，如果它的父亲不在支配树上的 1\to x 这条路径上，它这棵子树就可以产生贡献，求出dfs序之后差分一下即可。

复杂度 O(nq) 。

支配树的建法：

因为 n=3000，所以允许我们使用 O(n^2) 的建法，而且在考场上感觉这种建法好写好调，性价比高。我们分别删掉 [1...n] 中的每一个点，从 1 开始跑 dfs，求出每个点的受支配集（如果删掉点 u 后 1 不能到达点 v 那么 u 支配 v）。

然后类似拓扑排序一样，首先把 1 入队，然后重复进行如下操作：

取出队头 u，对于所有受支配集中存在点 u 的点，把 u 从受支配集中删掉。
对于所有没有入队并且受支配集中只剩下本身（支配集大小为 1 ）的点 v 入队，连边 (u,v)。

等队列为空，就可以得到一颗支配树了！

在放代码前，写一写在考场上的心路历程吧。

考场上读完三题，5分钟就想到了这题的大概做法，但是写完之后，对拍不断出错，于是我就陷入了出错，调试，出错，调试，出错...... 如此这样的死循环。

2.5h的时候，我绝望了，面对 0 分的 T3 和压根都没来得及思考的 T1,T2 ，我头一次尝到的绝望，无助，想哭的感觉。可能每次水到渠成之时，命运总会像一块大石头，挡在我面前吧。

但我想，反正也进不了队了，豁出去了！我抖擞精神，想了一会儿 T1,T2 大概能拿 50，便直接回去肝 T3，终于在 4h 的时候，对拍不断跳出 AC 的字样，泪目。于是又花 30min 用手速优势敲完暴力，卡时间交题。

最后因为 T3 常数太大了，没通过民间数据，只拿到了 75 分（upd:过了/se），前面两题也只有 50 分。下考之后花 10 分钟仔细想了想 T1，才发现是道送分题。可是命运总是这样，它不断地捉弄你，也许只有知道自己的考试策略太过激进，才能成为更稳的自己吧，也许只有经历大赛的磨炼，才能成长为更强的自己吧。

最后是稍作修(ka)改(chang)后的考场代码（要是没通过的话我会回来修锅的啊哈哈）：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=3021;
int n,m,tot,tot2,tot1,Did,Tid,ans;
int v[N],v1[N],v2[N],stk[N*N],cnt[N],siz[N],fa[N],dfn[N],vis1[N],cf[N],vis2[N];
bool del[N],vis[N],dis[N][N],init[N],cg[N][N];
struct Edge{int to,next;}e[N<<3],e1[N<<3],e2[N<<3];
void add1(int x,int y){
    e1[++tot1].to=y; e1[tot1].next=v1[x]; v1[x]=tot1;
}
void add2(int x,int y){
    e2[++tot2].to=y; e2[tot2].next=v2[x]; v2[x]=tot2;
}
void add(int x,int y){
//  cerr<<"add "<<x<<" -> "<<y<<endl;
    e[++tot].to=y; e[tot].next=v[x]; v[x]=tot;
}
void dfs(int x){
    if(del[x])return; vis[x]=1;
    for(int p=v1[x];p;p=e1[p].next)
        if(!vis[e1[p].to])dfs(e1[p].to);
}
void dfs2(int x){
    if(del[x])return; vis[x]=1;
    for(int p=v2[x];p;p=e2[p].next)
        if(!vis[e2[p].to])dfs2(e2[p].to);
}
void dfs1(int x){
    siz[x]=1; dfn[x]=++Did;
    for(int p=v[x];p;p=e[p].next){
        int kp=e[p].to; fa[kp]=x;
        dfs1(kp); siz[x]+=siz[kp];
    }
}
bool Init(int x,int y){
//  cerr<<"Init "<<x<<" "<<y<<" "<<dfnendl;
    return (dfn[y]>=dfn[x] && dfn[y]<dfn[x]+siz[x]);
}
void getans(int x,int y){
//  if(ctt==3)cerr<<"getans "<<x<<endl;
    vis1[x]=vis2[x]=Tid;
    if(!Init(fa[x],y) && vis2[fa[x]]!=Tid)stk[++ans]=x;
    for(int p=v1[x];p;p=e1[p].next)
        if(vis1[e1[p].to]!=Tid)getans(e1[p].to,y);
    vis2[x]=Tid-1;
}
bool cmp(const int &x,const int &y){return dfn[x]<dfn[y];}
int read(){
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
//  freopen("dominator.in","r",stdin);
//  freopen("dominator.out","w",stdout);
    n=read(); m=read(); int aq=read();
    for(int x,y,i=1;i<=m;i++)
        x=read(),y=read(),add1(x,y),add2(y,x);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            del[j]=vis[j]=0; del[i]=1;
        dfs(1);
        for(int j=1;j<=n;j++)
            if(!vis[j])dis[j][i]=1,++cnt[j];
    }
//  for(int i=1;i<=n;i++)cout<<cnt[i]<<" ";cout<<endl;
//  for(int i=1;i<=n;i++,cout<<endl)
//      for(int j=1;j<=n;j++)cout<<dis[i][j]<<" ";
    int top; stk[top=1]=1; init[1]=1;
    for(int i=1;i<=top;i++){
//      cout<<"cnt[3]="<<cnt[3]<<" i="<<i<<endl;
//      if(i>n)break;
        int w=stk[i];
//      cout<<"w="<<w<<endl;
//      if(i==60){cout<<w<<endl;for(int j=1;j<=n;j++)cout<<cnt[j]<<" ";cout<<endl;}
        for(int j=1;j<=n;j++)
            if(dis[j][w])--cnt[j];
        for(int j=1;j<=n;j++)
            if(cnt[j]==1 && !init[j])
                init[j]=1,add(w,j),stk[++top]=j;
//      if(i==60){for(int j=1;j<=n;j++)cout<<cnt[j]<<" ";cout<<endl;}
    }
    fa[1]=1; dfs1(1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            del[j]=vis[j]=0;
        del[fa[i]]=1; dfs2(i);
        for(int j=1;j<=n;j++)
            cg[i][j]=vis[j];
    }
//  cerr<<"fa:";for(int i=1;i<=n;i++)cerr<<fa[i]<<" ";cerr<<endl;
//  cout<<"siz:";for(int i=1;i<=n;i++)cout<<siz[i]<<" ";cout<<endl;
//  int ctt=0;
    while(aq--){
        int x=read(),y=read(),x1=x;
        ans=0; ++Tid;
        while(x1!=1)vis1[x1]=Tid,x1=fa[x1]; vis1[1]=Tid;
        for(int i=1;i<=n+1;i++)cf[i]=0;
//      getans(y,x);
        for(int i=1;i<=n;i++)
            if(cg[i][y] && vis1[fa[i]]!=Tid)
                ++cf[dfn[i]],--cf[dfn[i]+siz[i]];
        for(int i=1;i<=n;i++)
            cf[i]+=cf[i-1],ans+=(cf[i]!=0);
//      sort(stk+1,stk+ans+1,cmp);
//      if(ctt==5){
//          cerr<<"stk:";for(int i=1;i<=ans;i++)cerr<<stk[i]<<" ";cerr<<endl;
//      }
//      int mxr=0,ct=0;
//      for(int i=1;i<=ans;i++){
//          if(dfn[stk[i]]<=mxr)continue;
//          mxr=dfn[stk[i]]+siz[stk[i]]-1; ct+=siz[stk[i]];
//      }
//      cout<<x<<" -> "<<y<<endl;
        printf("%d\n",ans);
    }
    return 0;
}

彩蛋？大样例是用脚造的，上面的代码保留了大部分我考场艰辛的调试信息，删掉调试信息也就 2k 左右，所以不要被代码长度吓到啦！

[省选联考 2021 A 卷] 支配 题解

[省选联考 2021 A 卷] 支配题解