P7520 [省选联考 2021 A 卷] 支配

https://www.luogu.com.cn/problem/P7520

考虑支配树，一个显然的结论是如果一个点的受支配集合发生改变，那么他在支配树上子树中的所有点的受支配集合都会发生改变
那么只要求出所有他的父亲不改变、他改变的点就可以了，然后往子树里推标记统计最终的标记个数即可

那么原本是要对每个询问 \((x,y)\) 找路径 \(1\rightarrow x \rightarrow y\rightarrow u\) 使得不经过 \(u\) 在支配树上的祖先，现在只要不经过他的父亲也就是 \(idom(u)\) 即可
那么对于 \(u\) 的判断就是：\(idom(u)\) 不是 \(x\) 在支配树上的祖先；\(v\) 可以在不经过 \(idom(u)\) 的情况下到达 \(u\)（在原图上）
第一个条件直接每次询问的时候判断，第二个预处理出 \(u\) 在不经过 \(idom(u)\) 情况下，从反图上走，能走到哪些点

#define N 3006
#define M 6006
struct Graph{
	int fir[N],nex[M],to[M],tot;
	inline void add(int u,int v){to[++tot]=v;nex[tot]=fir[u];fir[u]=tot;}
}G,T,H;
int dfscnt,dfn[N],id[N],fa[N];
int idom[N],sdom[N];
struct UnionSet{
	int fa[N],min[N];
	inline int find(int k){
		if(fa[k]==k) return k;
		int father=find(fa[k]);
		if(dfn[sdom[min[fa[k]]]]1;i--){
		u=id[i];
		for(int v,j=T.fir[u];j;j=T.nex[j])if(dfn[T.to[j]]){
			v=T.to[j];S.find(v);
			if(dfn[sdom[S.min[v]]]>> change: %d\n",i);
		for(int i=2;i<=dfscnt;i++) changed[id[i]]|=changed[idom[id[i]]];
		int ans=0;
		for(int i=1;i<=n;i++) ans+=changed[i];
		printEN(ans);
		__builtin_memset(changed,0,sizeof changed);__builtin_memset(tag,0,sizeof tag);
	}
	return RET;
};