支配树

为了方便本文的叙述，做出如下可能不严谨的定义：

对于一棵树，我们可以用$[x,y]$简洁的表示从$x$到$y$的路径上的所有点组成的集合，假如我们希望这个集合不包含$x$或$y$，只要将闭区间改为开区间即可。如$[x,y)$表示从$x$到$y$的路径上的所有点（不包含$y$）组成的集合。

我们从一道简单的板子题（在读完这篇文章以后就是了）开始：

给定一个$n$个点，$m$条边的有向图$G$，以及一个出发点$r$。询问$q$次，每次给定点$x$，$y$，保证从$r$出发可以到达$x$。问从$r$出发到达$x$的所有路径是否都需要经过$y$。

$n,m,q\le {10}^5$。

为了解决这个问题，我们定义有向图上的支配关系：对于一个固定的出发点$r$，如果从$r$出发到达$x$的所有路径都需要经过$y$，则称$y$是$x$的支配点，即$y$支配$x$。特别的，我们认为$x$不是$x$的支配点。

我们来研究一下支配关系有哪些性质：

首先，我们将以$r$为根的$dfs$树建立出来。容易发现，对于任意一个点$x$，它的所有支配点只可能是它的祖先——显然，对于不是它的祖先的任意一个点$y$，我们从$r$通过树边到达$x$就不需要经过$y$。

接着我们假设$y$是$x$的支配点中深度最大的（即距离$x$最近的），那么还可以发现：对于$z\ne y$，$z$是$x$的支配点当且仅当$z$是$y$的支配点。

证明如下：

首先证明充分性。如果$y$支配$x$，$z$支配$y$，那么假设$z$不支配$x$，即存在一条路径不经过$z$。那么显然由于这条路径必定经过$y$，于是我们就找到了一条不经过$z$到达$y$的路径，这与前提条件矛盾，于是假设不成立，充分性得证。

再证明必要性。如果$y$支配$x$，$z$不支配$y$，显然可以找到一条路径不经过$z$而到达$y$。此时由于$y$是深度最大的$x$的支配点，因此沿着树边一直走到$x$，必定不会经过$z$，于是$z$就不可能是$x$的支配点。

于是我们就可以知道，对于任意一个点$x$，我们只要找到它深度最大的支配点$y$，其余的支配点就都是$y$的支配点。不难发现，这样的支配关系形成了一个类似树的结构，将之前所说的$y$当作$x$的父亲的话，那么$x$的所有支配点就是这棵树上它的祖先。我们将这棵树叫做支配树，将这样的$y$记为$idom(x)$。

那么问题来了，如何求出$idom(x)$呢？

为了解决这个问题，我们先定义一个叫做半支配的东西：

对于任意一个点$x$，从$y$出发，只经过不是$x$的祖先的点就可以到达$x$（不包含$x$，$y$），则称$y$是$x$的半支配点，即$y$半支配$x$。

首先，我们可以发现$x$的深度最小的半支配点一定是$x$的祖先。因为假设$x$的深度最小的半支配点$y$不是$x$的祖先，那么显然我们可以沿着树边往回走，一直走到某个$x$的祖先$z$上。这其间肯定不会经过除$z$以外的$x$的祖先点，于是$z$的深度比$y$小，且也是$x$的半支配点，于是假设不成立，得证。

接着，如果$y$是$x$的深度最小的半支配点，那么树上路径$(x,y)$中的点就显然不是$x$的支配点——因为从$y$出发存在一条路不经过它们而到达$x$。我们将这样的$y$记为$sdom(x)$。

我们来考虑如果求得了半支配点，那么如何求支配点。考虑对于一个点$x$，树上路径$(x,sdom(x))$中的点一定不是$x$的支配点。并且对于任意一个$x$的祖先$y$，树上路径$(y,sdom(y))$中的点也一定不是$x$的支配点。反之，如果某个$x$的祖先$z$不被$(x,sdom(x))$和任何一个$(y,sdom(y))$包含，那么$z$一定是$x$的支配点——否则一定会存在一条不经过$z$的路径$S$到达$x$，$S$中一定存在两个$x$的祖先$a,b$使得树上路径$(a,b)$经过$z$而$a,b$之间不经过其它$x$的祖先，于是$z$一定会被某个区间包含。

于是$idom(x)$就是不被如上所述的这些区间包含的$x$的祖先中深度最大的。考虑递归解决这个问题，如果$y$是$[x,sdom(x))$中$sdom(y)$的深度最小的，那么如果$sdom(y)$就是$sdom(x)$，显然$sdom(x)$不会被任何区间包含了，那么$idom(x)$就是$sdom(x)$。否则我们就去掉区间$(x,sdom(x))$并求对于$y$来说这个问题的答案即可——而这就是$idom(y)$，已经求好了。

好，现在解决最后一个问题，如何求出$sdom(x)$。分两种情况讨论：

$1)$最后一条边为前向边或树边。显然另一端就是$x$的祖先，路径必须结束。这种情况可以直接得到半支配点。

$2)$最后一条边为横插边或后向边，设走到的点为$y$，而$x$，$y$在$dfs$树上的$lca$为$z$。由于$lca$为$z$，因此树上路径$[x,z)$中的点一定无法到达$[y,z)$中的点，于是对于$[y,z)$的$sdom$来说，不会有经过$[x,z)$中的点的路径，那么显然树上路径$[y,z)$中的点对于$x$来说都是合法的。于是用树上路径$[y,z)$中的点的$sdom$来更新$sdom(x)$即可。可以发现沿着时间戳反向求$sdom$的话，我们求$sdom$的顺序就不会冲突。

于是我们就解决了文章开头提到的那个问题。至于具体的实现，我们在反向求$sdom$的过程中可以用带权并查集维护一段树上路径的$sdom$最小值，在求完一个点的$sdom$以后将它的儿子与它合并即可。这样每次查询时并查集维护的恰好就是我们需要的那一条链。至于求$idom$的过程，我们需要知道$[x,sdom(x))$的信息，于是将请求接入$sdom(x)$的链表中。每一次求完$x$的$sdom$后，我们扫描其父亲的请求链表，对于链表中每一个$y$，可以发现带权并查集此时维护的就是我们要查询的区间$[y,sdom(y))$，直接从带权并查集上得知$sdom$最小的为哪一个并存下来并清空链表，在最后求$idom$时直接用即可。

时间复杂度$O((n+m)\log n)$。

有向图上还有类似的支配边的关系，容易发现只有树边能成为支配边。且如果一条边$y\to x$为$x$的支配边，需要$y$为$x$的支配点，且对于所有有非树边指向$x$的点$z$，都有$x$支配$z$。

有向图上还有割点、桥、点双、边双的定义。不过还是下次填坑吧...

参考链接：[https://zhuanlan.zhihu.com/p/30432617][1]