题目链接
看到题目名称,我反手就是一个支配树,很快啊……哦我不会支配树啊,那没事了。
看一眼数据范围……\(n\) 只有 \(3\times10^3\)?那直接 \(O(n^2)\) 枚举删掉每个点大力求出支配集合就好了。
然后根据支配集合的大小关系建出支配树来。
考虑新加入一条边 \((x,y)\),会有哪些点 \(i\) 在支配树上的父亲发生变化,手玩可以发现充要条件是:
\(x\) 不是 \(fa_i\);
\(fa_i\) 不是 \(1\);
从 \(1\) 走到 \(x\) 不必须经过 \(fa_i\),即 \(fa_i\) 不支配 \(x\);
从 \(y\) 走到 \(i\) 不必须经过 \(fa_i\)。
前三个条件在求支配树的时候都已经求出来了,最后一个条件建出反图,然后从每个 \(i\) 出发,钦定不能走 \(fa_i\),看看哪些点能到就好了,也能在 \(O(n^2)\) 的时间内与处理出来。
这样我们得出了哪些点的 \(fa_i\) 发生了改变,又因为树上的支配关系改变是具有传递性的,然后再线性推一遍标记就好了,时间复杂度 \(O(n(n+q))\)。
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; struct edge { int nxt,to; }e[6001<<1]; int n,m,q,tot,h[3001],fa[3001],id[3001],ans; bool vis[3001][3001][2],tag[3001]; vector<int> domain[3001]; inline int read() { int x=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x; } void print(int x) { if(x>=10) print(x/10); putchar(x%10+'0'); } inline bool cmp(int x,int y) { return domain[x].size()<domain[y].size(); } inline void add(int x,int y) { e[++tot].nxt=h[x]; h[x]=tot; e[tot].to=y; } void dfs1(int k,int ban) { if(k==ban) return; vis[k][ban][0]=1; for(register int i=h[k];i;i=e[i].nxt) if(i&1) if(!vis[e[i].to][ban][0]) dfs1(e[i].to,ban); } void dfs2(int k,int s,int ban) { if(k==ban) return; vis[k][s][1]=1; for(register int i=h[k];i;i=e[i].nxt) if(!(i&1)) if(!vis[e[i].to][s][1]) dfs2(e[i].to,s,ban); } int main() { n=read(),m=read(),q=read(); for(register int i=1;i<=m;++i) { int x=read(),y=read(); add(x,y); add(y,x); } dfs1(1,0); for(register int i=1;i<=n;++i) { dfs1(1,i); for(register int j=1;j<=n;++j) if(vis[j][0][0]&&!vis[j][i][0]) domain[j].push_back(i); } /*for(register int i=1;i<=n;++i,puts("")) for(register int j=0;j<(int)domain[i].size();++j) printf("%d ",domain[i][j]);*/ for(register int i=1;i<=n;++i) id[i]=i; sort(id+1,id+n+1,cmp); for(register int i=2;i<=n;++i) for(register int j=0;j<(int)domain[i].size();++j) if(domain[domain[i][j]].size()==domain[i].size()-1) { fa[i]=domain[i][j]; break; } for(register int i=2;i<=n;++i) dfs2(i,i,fa[i]); while(q--) { ans=0; int x=read(),y=read(); for(register int i=1;i<=n;++i) if(fa[i]!=1&&x!=fa[i]&&vis[x][fa[i]][0]&&vis[y][i][1]) tag[i]=1; else tag[i]=0; for(register int i=1;i<=n;++i) ans+=(tag[id[i]]|=tag[fa[id[i]]]); print(ans); putchar('\n'); } return 0; }