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

发表于

2021-04-16 分类于 OI题解

热度： 12 Valine： 0

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

u→v 表示从 u 到 v 的有向边，u⇝v 表示 u 到 v 的路径。

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

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

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

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

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

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

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

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

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

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

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

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

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

点击展开/折叠代码

THE END

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

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