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

题意本身就已经够简洁的了，所以这里不再复述。 首先建一棵支配树（建法在最下面），那么一个点 $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$ 入队，然后重复进行如下操作： 1. 取出队头 $u$，对于所有受支配集中存在点 $u$ 的点，把 $u$ 从受支配集中删掉。 2. 对于所有没有入队并且受支配集中只剩下本身（支配集大小为 $1$ ）的点 $v$ 入队，连边 $(u,v)$。 等队列为空，就可以得到一颗支配树了！ 在放代码前，写一写在考场上的心路历程吧。 考场上读完三题，5分钟就想到了这题的大概做法，但是写完之后，对拍不断出错，于是我就陷入了出错，调试，出错，调试，出错...... 如此这样的死循环。 2.5h的时候，我绝望了，面对 $0$ 分的 T3 和压根都没来得及思考的 T1,T2 ，我头一次尝到的绝望，无助，想哭的感觉。可能每次水到渠成之时，命运总会像一块大石头，挡在我面前吧。 但我想，反正也进不了队了，豁出去了！我抖擞精神，想了一会儿 T1,T2 大概能拿 $50$，便直接回去肝 T3，终于在 $4h$ 的时候，对拍不断跳出 $AC$ 的字样，泪目。于是又花 $30$min 用手速优势敲完暴力，卡时间交题。 最后因为 T3 常数太大了，没通过民间数据，只拿到了 $75$ 分（upd:过了/se），前面两题也只有 $50$ 分。下考之后花 $10$ 分钟仔细想了想 T1，才发现是道送分题。可是命运总是这样，它不断地捉弄你，也许只有知道自己的考试策略太过激进，才能成为更稳的自己吧，也许只有经历大赛的磨炼，才能成长为更强的自己吧。 最后是稍作修(ka)改(chang)后的考场代码（要是没通过的话我会回来修锅的啊哈哈）： ```cpp #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$ 左右，所以不要被代码长度吓到啦！