「SOL」支配 (2021省选A卷)

忽然觉得好像不是这么难……

# 题面

# 解析

一些记号

$u\to v$ 表示从 $u$ 到 $v$ 的有向边，$u\leadsto v$ 表示 $u$ 到 $v$ 的路径。

既然题目都叫「支配」，那还是先把支配树建出来。好在数据范围允许 $O(n^2)$ 建支配树。

我们发现支配关系是具有传递性的，即“若 $u$ 支配 $v$ 且 $v$ 支配 $w$，则 $u$ 支配 $w$”，由此可得我们可以把支配关系建成一棵树，树上每个点都支配它的整棵子树。特别的，$1$ 支配所有点，作为支配树的根。

具体怎么建？首先，只要会写暴力就知道怎么求一个点的支配集 —— 对每个 $u$ 确定 $u$ 能支配哪些 $v$：把 $u$ 从图上删去，若 $1$ 无法到达 $v$，则 $u$ 支配 $v$。于是枚举每个 $u$，删去后遍历一遍图，可以 $O(nm)$ 求出支配集。

求出支配集后，（隐式地）新建一个图，若 $u$ 支配 $v$ 则在新图上连有向边 $u\to v$。然后对这个新图求一个拓扑，拓扑到 $u$ 的上一个点即为 $u$ 在支配树上的父亲。

然后来考虑询问，设询问加入的边为 $s\to t$。

若点 $u$ 的支配集改变，则意味着存在一条路径 $P=1\leadsto s\to t\leadsto u$，且 $P$ 不经过 $u$ 的某一个支配点。也即 $P$ 不经过 $u$ 在支配树上的某个祖先。

但是如果仅是「不经过支配树上的某个祖先」，这道题也很难解决。我们可以发现，若 $u$ 的支配集改变，则 $u$ 原本支配的所有点的支配集都将改变。

这意味着我们只需要找到支配树上最靠上的一个支配集改变的点。而这个点（记为点 $u$）满足的性质就更强 —— 存在路径 $P=1\leadsto s\to t\leadsto u$ 使得 $P$ 不经过 $u$ 在支配树上的父亲。

有了这个性质，我们就可以较快地解决这道题了。我们只需要判断：

$t$ 能够不经过 $fa(u)$ 到达 $u$；
$1$ 能够不经过 $fa(u)$ 到达 $s$。

条件 2 相当于「$fa(u)$ 不支配 $s$」，因为我们已经处理出支配集，可以 $O(1)$ 判断。

如何处理条件 1？可以直接在原图上删去 $fa(u)$，然后看哪些点能够到达 $u$（或者说反图上删去 $fa(u)$，看 $u$ 能到哪些点）。可以 $O(nm)$ 预处理。

于是对每个询问，可以 $O(n)$ 判断哪些子树的支配集会改变，求出 DFS 序然后差分区间打标记即可。

总复杂度 $O\big(n(m+q)\big)$。

# 源代码

点击展开/折叠代码

/*Lucky_Glass*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 3005, M = 6005;
#define con(typ) const typ &

template<const int P, const int E>
struct Graph {
	int head[P], to[E], nxt[E], ncnt;
	void addEdge(con(int) u, con(int) v) {
		int p = ++ncnt;
		to[p] = v, nxt[p] = head[u];
		head[u] = p;
	}
	inline int operator [] (con(int) u) const {return head[u];}
};
Graph<N, M> gr, rg;
Graph<N, N> tre;

int n, m, nq, ndfn;
bool dom[N][N], rea[N][N];
int tag[N], que[N], deg[N], fa[N], ans[N], siz[N], dfn[N];

inline int rin(int &r) {
	int c = getchar(); r = 0;
	while ( c < '0' || '9' < c ) c = getchar();
	while ( '0' <= c && c <= '9' ) r = (r * 10) + (c ^ '0'), c = getchar();
	return r;
}
inline void write(con(int) w) {
	if ( w < 10 ) putchar(w ^ '0');
	else write(w / 10), putchar((w % 10) ^ '0');
}
void bfs(con(int) ban) {
	int ql = 1, qr = 1;
	que[1] = 1, tag[1] = ban;
	while ( ql <= qr ) {
		int u = que[ql++];
		for (int it = gr[u]; it; it = gr.nxt[it]) {
			int v = gr.to[it];
			if ( v != ban && tag[v] != ban )
				que[++qr] = v, tag[v] = ban;
		}
	}
	for (int i = 1; i <= n; i++)
		if ( tag[i] != ban )
			deg[i]++, dom[ban][i] = true;
}
void build() {
	int ql = 1, qr = 1; que[1] = 1;
	while ( ql <= qr ) {
		int u = que[ql++];
		for (int v = 1; v <= n; v++)
			if ( dom[u][v] && (--deg[v]) == 1 ) {
				fa[v] = u, que[++qr] = v;
				tre.addEdge(u, v);
			}
	}
}
void dfs(con(int) u) {
	dfn[u] = ++ndfn, siz[u] = 1;
	for (int it = tre[u]; it; it = tre.nxt[it])
		dfs(tre.to[it]), siz[u] += siz[tre.to[it]];
}
void getReach(con(int) s, con(int) ban) {
	int ql = 1, qr = 1; que[1] = s;
	rea[s][s] = true;
	while ( ql <= qr ) {
		int u = que[ql++];
		for (int it = rg[u]; it; it = rg.nxt[it]) {
			int v = rg.to[it];
			if ( v != ban && !rea[s][v] )
				rea[s][v] = true, que[++qr] = v;
		}
	}
}
int main() {
//	freopen("input\\input.in", "r", stdin);
	rin(n), rin(m), rin(nq);
	for (int i = 1, u, v; i <= m; i++) {
		rin(u), rin(v);
		gr.addEdge(u, v), rg.addEdge(v, u);
	}
	for (int i = 1; i <= n; i++)
		deg[i]++, dom[1][i] = true;
	for (int i = 2; i <= n; i++) bfs(i);
	build(), dfs(1);
	for (int i = 2; i <= n; i++) getReach(i, fa[i]);
	while ( nq-- ) {
		int s, t; rin(s), rin(t);
		for (int i = 2; i <= n; i++)
			if ( !dom[fa[i]][s] && rea[i][t] )
				ans[dfn[i]]++, ans[dfn[i] + siz[i]]--;
		int tot = 0;
		for (int i = 1; i <= n + 1; i++) {
			ans[i] += ans[i - 1];
			if ( ans[i] ) tot++;
			ans[i - 1] = 0;
		}
		write(tot), putchar('\n');
	}
	return 0;
}

THE END

Thanks for reading!

你走吧趁着落日长天
你走吧此去山遥路远
敢想你策马挥鞭绝尘不见

——《山遥路远（人声本家）》By ChiliChill

> Link 山遥路远(夏铜子 CuSummer)-网易云