写在前面

---

今天亮神花了一早上给讲了支配树，但由于今天网（没）速（人）不（跟）好（上），我们残忍地看了他一眼后掉线了，于是又用了一下午开流量重新联网并结合缓（课）存（件）学习。

注：本文在原文的基础上加上了作者本人理解，不好勿喷。

就由一道题引入吧。

题目

---

HDU4694 Important Sisters

简单题意：一个有n$n$个点，m$m$条边的有向图，以n$n$为起点，若去掉点b$b$，n$n$就不能连到a$a$，则称b$b$是a$a$的important$important$ sister$sister$,求每个点的所有important$important$ sister$sister$的编号和。

欸好，这题一看我就不会。

暴力O(n2∗(n+m))$O(n^2\ast (n+m))$，所以我们需要一个更加优美的算法。进入正题~

定义新名词

---

支配：

在有向图中，固定起点r$r$，若r$r$~w$w$的每一条路径都必定经过v$v$且v≠w$v\ne w$，则v$v$支配w$w$。

最近支配点：

若v$v$支配w$w$，且w$w$的其余支配点全都支配v$v$，则称v$v$是w$w$的最近支配点，记 idom(w)=v$idom(w)=v$。

如上图中，idom(a)=r$idom(a)=r$ ，idom(b)=a$idom(b)=a$。

半支配点：

若在原图G$G$中有点v$v$，有一条路径 v=v0,v1,v2,...vk=w$v=v_0,v_1,v_2,...v_k=w$，使得 dfn[vi]>dfn[w]$dfn[v_i]>dfn[w]$ 对于1<=i<=k−1$1<=i<=k-1$ 成立 （即不包括点v$v$，w$w$），则记 sdom(w)=min(v)$sdom(w)=min(v)$ 。

好，上面突然提到 dfn$dfn$ ，解释一下。到了支配树最恶心的地方了

定理、引理、推论及其证明

---

定理一（支配树定理）

除r$r$外都有每个点都有唯一的 idom$idom$，且不成环，故所有的 (idom(w),w)$(idom(w),w)$ 边形成一棵树，v$v$支配w$w$当且仅当v$v$是树中w$w$的祖先，这棵树叫做支配树。

有了这个定理，就可以发现 important$important$ sisters$sisters$ 这个题目就是求解每个点在支配树上所有祖先的编号之和。只要求出支配树，问题就迎刃而解了。

引入算法

LengauerTarjan$Lengaue{r}_{T}arjan$ 算法： O(n∗α(n))$O(n\ast \alpha (n))$ 求出所有点的最近支配点，以及半支配点。（读作：兰高娃-塔儿尖算法）然后再等我证会儿再说

引理1（路径引理）

从r$r$开始 dfs$dfs$ 整张图，按照 dfs$dfs$序（即 dfn$dfn$值）给结点重新编号，得到的树称为搜索树（即后文的T$T$树）。

若 dfn[v]<=dfn[w]$dfn[v]<=dfn[w]$ ，则 v$v$~w$w$ 的任意路径都包含在它们在T$T$树中的一个公共祖先。

证明：

如图，结点标号即为其 dfn$dfn$ 值，黑边为树边，蓝边为原图边。

边(3,2)$(3,2)$的两个端点属于r$r$的不同子树（即u$u$不是v$v$的祖先，且v$v$不是u$u$的祖先），那么这样的边就叫做横叉边。

但是，根据 dfs$dfs$ 的顺序我们可以发现，如果原图有边(2,5)$(2,5)$，那么深搜时就会从2$2$直接走向5$5$，此时标号就会发生变化，故边(2,5)$(2,5)$不存在。

由上可知，横叉边只从 dfn$dfn$ 值大的点连向 dfn$dfn$ 值小的点。

因为题设中说 dfn[v]<=dfn[w]$dfn[v]<=dfn[w]$ ，那么不存在从点v$v$到点w$w$，且不经过任何 dfn[i]<dfn[v]$dfn[i]<dfn[v]$ 的点i$i$的路径，所以从v$v$到w$w$的路径中一定会经过一个dfn$dfn$值小的点，即它们的一个公共祖先。

引理2

记 v+−>w$v+->w$ 表示v$v$是w$w$在T$T$树中的祖先，且 v≠w$v\ne w$ （即完全祖先）。

记 v⋅−>w$v·->w$ 表示v$v$是w$w$在T$T$树中的祖先，但允许 v=w$v=w$ 。

则有

idom(w)+−>w$idom(w)+->w$

证明：

因为 idom(w)$idom(w)$ 在每一条r$r$~w$w$的路径上，那就必定在这一条树路径上，所以，必然有 idom(w)+−>w$idom(w)+->w$ 。

引理3

sdom(w)+−>w$sdom(w)+->w$

证明：

设w$w$在T$T$树中的父亲为 fa(w)$fa(w)$ ，则 (fa(w),w)$(fa(w),w)$ 是原图G$G$中的一条边。因 sdom$sdom$ 的定义，可以发现 fa(w)$fa(w)$ 符合要求，由 sdom$sdom$ 求的是最小的，那么至少可以有 sdom(w)=fa(w)$sdom(w)=fa(w)$ ，故可得 sdom(w)<=fa(w)<w$sdom(w)<=fa(w)<w$ 。（比较的是 dfn$dfn$ 值）

再有 sdom$sdom$ 的定义得，有一条路径 sdom(w)=v0,v1,v2,...,vk=w$sdom(w)=v_0,v_1,v_2,...,v_k=w$ 使得 dfn[vi]>dfn[w]$dfn[v_i]>dfn[w]$ 对于 1<=i<=k−1$1<=i<=k-1$ 成立。由引理1可知，因为 dfn[sdom(w)]<dfn[w]$dfn[sdom(w)]<dfn[w]$ ，路径上必有某一节点vi$v_i$是 sdom(w)$sdom(w)$ 和w$w$在T$T$树中的公共祖先，即必然有 dfn[vi]<=dfn[sdom(w)]$dfn[v_i]<=dfn[sdom(w)]$ 。这意味着只有使 i=0$i=0$，即 vi=sdom(w)$v_i=sdom(w)$ 才符合。

故有 sdom(w)$sdom(w)$ 是 sdom(w)$sdom(w)$ 和 w$w$ 的公共祖先，即 sdom(w)$sdom(w)$ 是 w$w$ 的完全祖先。

引理4

对于任意结点 w$w$，w≠r$w\ne r$，idom(w)⋅−>sdom(w)$idom(w)·->sdom(w)$ 。

证明：

由引理2、3得 idom(w)$idom(w)$ 和 sdom(w)$sdom(w)$ 都是w$w$的完全祖先。

用反证法，假定 sdom(w)⋅−>idom(w)$sdom(w)·->idom(w)$ ，则 dfn[sdom(w)<dfn[idom(w)]$dfn[sdom(w)<dfn[idom(w)]$ 。

我们在从r$r$到 sdom(w)$sdom(w)$ 的路径后面接上 sdom(w)$sdom(w)$ 中规定的路径 sdom(w)=v0,v1,v2,...,vk=w$sdom(w)=v_0,v_1,v_2,...,v_k=w$ （见上图）。

这条从r$r$到w$w$的路径避开了T$T$树中既是w$w$的完全祖先，也是 sdom(w)$sdom(w)$ 的完全后代（即不等于它自身的后代）的那些点(图中点2$2$)，那么我们假定的 idom(w)$idom(w)$ 就在这些点中。此时从r$r$到w$w$的路径没有全部经过点 idom(w)$idom(w)$ ，不符合 idom$idom$ 的定义。

因此 idom(w)$idom(w)$ 不在这些点中，即 idom(w)$idom(w)$ 一定是 sdom(w)$sdom(w)$ 的祖先。

引理5

若结点v$v$，w$w$满足 v⋅−>w$v·->w$，则有 v⋅−>idom(w)$v·->idom(w)$ 或者 idom(w)⋅−>idom(v)$idom(w)·->idom(v)$ 。

证明：

设x$x$是 idom(v)$idom(v)$ 的任意一个完全后代，且同时是v$v$的完全祖先，则必然有一条从r$r$到v$v$不经过x$x$的路径（若所有路径全都经过x$x$，则应该 idom(v)=x$idom(v)=x$，x$x$不能是 idom(v)$idom(v)$ 的完全后代）。

将这条路径和从v$v$到w$w$在T$T$树上的路径连接起来，就得到了一条从r$r$到w$w$不经过x$x$的路径。

idom[w]$idom[w]$ 不能在 idom[v]$idom[v]$ 到 v$v$ 之间（这段之间的路径至少有两条），所以 idom[w]$idom[w]$ 要么是v$v$的后代，要么是 idom[v]$idom[v]$ 的祖先。

v⋅−>idom(w)$v·->idom(w)$ 示例

idom(w)⋅−>idom(v)$idom(w)·->idom(v)$ 示例

好！重头戏来了~

定理2

设w≠r$w\ne r$，假设所有使得 sdom(w)+−>u⋅−>w$sdom(w)+->u·->w$ 的所有u$u$都满足 sdom(u)>=sdom(w)$sdom(u)>=sdom(w)$ ，那么 idom(w)=sdom(w)$idom(w)=sdom(w)$。

证明：

由引理4$4$： idom(w)⋅−>sdom(w)$idom(w)·->sdom(w)$ 可得，我们只要证明了 sdom(w)$sdom(w)$ 支配了w$w$,那么就可以得到 idom(w)=sdom(w)$idom(w)=sdom(w)$。

考虑任意一条从r$r$到w$w$的路径，记为p$p$。设x$x$为这条路径上最后一个满足 dfn[x]<dfn[sdom(w)]$dfn[x]<dfn[sdom(w)]$ 的点。

分类讨论。若无此x$x$，则有 sdom(w)=r$sdom(w)=r$ ，一定支配w$w$。若有x$x$，设y$y$为这条路径上在x$x$之后，满足 dfn[sdom(w)]⋅−>dfn[y]⋅−>dfn[w]$dfn[sdom(w)]·->dfn[y]·->dfn[w]$ 的第一个点。设路径 q=(x=v0,v1,v2,...,vk=y)$q=(x=v_0,v_1,v_2,...,v_k=y)$ 是路径p$p$中从x$x$到y$y$的部分。（如图）

（点a$a$只是用来体现 sdom(w)$sdom(w)$ 的，不要在意）

我们断言：对于 1<=i<=k−1$1<=i<=k-1$ 均满足 dfn[vi]>dfn[y]$dfn[v_i]>dfn[y]$ 。

继续大力反证法，我们假定存在有一个i$i$使得 dfn[vi]<dfn[y]$dfn[v_i]<dfn[y]$ 。由引理一得，应当有某个j$j$满足 i<=j<=k−1$i<=j<=k-1$ 且点 vj$v_j$ 是点 vi$v_i$ 和 y$y$ 的公共祖先（即vj⋅−>j$v_j·->j$）。根据x$x$的选择方式：路径上 dfn[x]<dfn[sedom(w)]$dfn[x]<dfn[sedom(w)]$ 的最后一点，又因为 vj$v_j$ 在路径上x$x$的后方，那么一定有 dfn[vj]>=dfn[sdom(w)]$dfn[v_j]>=dfn[sdom(w)]$ （即 sdom(w)⋅−>vj$sdom(w)·->v_j$ ）。综合式子，则有 sdom(w)⋅−>vj⋅−>y⋅−>w$sdom(w)·->v_j·->y·->w$ 。此时 y$y$ 就不符合是第一个点这个选择条件了。断言证毕。

由 x+−>y$x+->y$ 结合我们对半支配点 sdom(y)+−>y$sdom(y)+->y$ 的证明，可以得出 dfn[sdom(y)]<=dfn[x]$dfn[sdom(y)]<=dfn[x]$ （最多可以为x$x$）。再联系x$x$选择方式，得 dfn[sdom(y)]<=dfn[x]<dfn[sdom(w)]$dfn[sdom(y)]<=dfn[x]<dfn[sdom(w)]$ 。

再根据断言和点 sdom(w)$sdom(w)$ 一定在路径q$q$上，若 y≠sdom(w)$y\ne sdom(w)$ 那么点 sdom(y)$sdom(y)$ 就应当和点 sdom(w)$sdom(w)$ 重合，不满足 dfn[sdom(y)]<dfn[sdom(w)]$dfn[sdom(y)]<dfn[sdom(w)]$ 的条件，因此 y=sdom(w)$y=sdom(w)$ ，且点 sdom(w)$sdom(w)$ 必在路径p$p$上。由于路径p$p$是任意的，故 sdom(w)$sdom(w)$ 支配了w$w$。证毕。

定理3

若有点 w≠r$w\ne r$ ，u$u$是所有满足 sdom(w)+−>u⋅−>w$sdom(w)+->u·->w$ 的节点中 sdom(u)$sdom(u)$ 最小的那个，那么 sdom(u)<=sdom(w)$sdom(u)<=sdom(w)$ ,且 idom(u)=idom(w)$idom(u)=idom(w)$ 。

证明：

因为至少可以使 u=w$u=w$ ，所以很容易就可以发现 sdom(u)<=sdom(w)$sdom(u)<=sdom(w)$ 。

由引理四 idom(w)$idom(w)$ 是 sdom(w)$sdom(w)$ 的祖先，因此 idom(w)$idom(w)$ 也是u$u$的完全祖先。

因为 u⋅−>w$u·->w$，再由引理五可知，只能使 idom(w)⋅−>idom(u)$idom(w)·->idom(u)$ 。为了证明 idom(u)=idom(w)$idom(u)=idom(w)$ ，就应当证明点 idom(u)$idom(u)$ 就可以支配w$w$。

考虑任意一条从r$r$到w$w$的路径p$p$，设点x$x$是路径中最后一个满足 dfn[x]<dfn[idom(u)]$dfn[x]<dfn[idom(u)]$。

基本同定理二的证明思路，如果没有符合要求的点x$x$，则有 idom(u)=r$idom(u)=r$ 必然支配w$w$。否则，设点y$y$是路径上x$x$后满足 idom(u)⋅−>y⋅−>w$idom(u)·->y·->w$ 的第一个点，设路径 q=(x=v0,vq,v2,...vk=y)$q=(x=v_0,v_q,v_2,...v_k=y)$ 是路径p$p$中从x$x$到y$y$的一部分。同理可证，dfn[sdom(y)]<=dfn[x]$dfn[sdom(y)]<=dfn[x]$ 。再由引理四 idom(u)⋅−>sdom(u)$idom(u)·->sdom(u)$ 得 dfn[idom(u)]<=dfn[sdom(u)]$dfn[idom(u)]<=dfn[sdom(u)]$ ，结合所有式子得 dfn[sdom(y)]<=dfn[x]>dfn[idom(u)]>=dfn[sdom(u)]$dfn[sdom(y)]<=dfn[x]>dfn[idom(u)]>=dfn[sdom(u)]$ 。

由u$u$的选择方式得，为了使u$u$是 dfn$dfn$ 最小的点，y$y$不可能是 sdom(w)$sdom(w)$ 的完全后代，y+−>u$y+->u$。

假若y$y$是u$u$的祖先，也是 idom(u)$idom(u)$ 的完全后代。我们在r$r$到sdom(y)$sdom(y)$的树上路径后接上使 sdom(y)$sdom(y)$ 成立的那条路径 （sdom(y)=v0,v1,v2,...,vk=y$sdom(y)=v_0,v_1,v_2,...,v_k=y$ 其中对于 1<=i<k$1<=i<k$ 均满足 dfn[vi]>dfn[y]$dfn[v_i]>dfn[y]$），再接上从y$y$到u$u$的树上路径，就形成了一条从r$r$到u$u$而不经过 idom(u)$idom(u)$ 的路径，矛盾，故不可能y$y$既是u$u$的祖先，又是 #idom(u)$ 的完全后代。

由于 idom(u)⋅−>y+−>u⋅−>w$idom(u)·->y+->u·->w$ ，且 idom(u)⋅−>y⋅−>w$idom(u)·->y·->w$ ，只能使 y=idom(u)$y=idom(u)$ （其实证法和定理二的证明基本一样）。因此， idom(u)$idom(u)$（即y$y$）在从r$r$到w$w$的任意一条路径上，故 idom(u)$idom(u)$ 支配w$w$。证毕~（不想配图了qwq）

对比定理二，我们可以发现，使定理二中所有使得 sdom(w)+−>u⋅−>w$sdom(w)+->u·->w$ 的u$u$都满足 sdom(u)>=sdom(w)$sdom(u)>=sdom(w)$ ，即使 dfn[sdom(u)]$dfn[sdom(u)]$ 最小的点u$u$满足 sdom(u)>=sdom(w)$sdom(u)>=sdom(w)$ ，又因为定理三中 dfn[sdom(u)]$dfn[sdom(u)]$ 最小的点u$u$满足 sdom(u)<=sdom(w)$sdom(u)<=sdom(w)$。二者均成立时只能取等，故可将定理二变为：

设w≠r$w\ne r$，假设所有使得 sdom(w)+−>u⋅−>w$sdom(w)+->u·->w$ 的所有u$u$都满足 sdom(u)=sdom(w)$sdom(u)=sdom(w)$ ，那么 idom(w)=sdom(w)$idom(w)=sdom(w)$。

推论

设 w≠r$w\ne r$ ，u$u$是所有满足 sdom(w)+−>u⋅−>w$sdom(w)+->u·->w$ 的节点中 sdom(u)$sdom(u)$的最小者，那么成立：
1、若 sdom(u)=sdom(w)$sdom(u)=sdom(w)$ ，则 idom(w)=sdom(w)$idom(w)=sdom(w)$。
2、否则（即 sdom(u)<sdom(w)$sdom(u)<sdom(w)$），idom(w)=idom(u)$idom(w)=idom(u)$。

这个推论基本就是定理二、三的一个整合，这个推论可以使我们由 sdom$sdom$ 推到 idom$idom$，最后就要看怎么得到 sdom$sdom$ 了。

挖坑代填……