先抛出一个问题：给一个有向图，问从 \(1\) 节点出发，求每个节点的受支配集。
这里，支配的定义为：若从 \(1\) 结点出发到 \(v\) 节点的所有路径中，都必须经过 \(u\) 节点，则称 \(u\) 支配 \(v\)。
那么受支配集意思就是对于 \(v\) 点满足条件的 \(u\) 点的集合。那么根据支配的定义，我们可以推出一个结论：如果 \(u_0\) 支配 \(v\)，\(u_1\) 支配 \(v\)，那么必有 \(u_0\) 支配 \(u_1\)，或 \(u_1\) 支配 \(u_0\)。这是显然的， 因为如果它们两个点不互相支配的话，那这两个点都会存在另一条不经过自己并经过对方到达 \(v\) 的路径，并不能满足这两个点是 \(v\) 的支配点。
也就是说，这是一个树形结构。每个点的父亲为第一个支配他的点，那么这棵支配树中每个点的祖先和自己都是支配自己的点。现在，我们考虑求出这棵支配树。
考虑运用 dfs 序和生成树完成该问题，为了方便，以下的任意节点 \(u\) 的编号为 \(dfn_u\)。
于是发明支配树的强者建立了一个新的概念：半支配点。如果 \(u\) 半支配 \(v\)，那么 \(u\) 必须满足存在一条到 \(v\) 的路径使得，除了 \(u,v\) 两点以外路径中其它点 \(v_k\) 都要大于 \(v\)，并且 \(u\) 是满足上述条件的编号（dfs 序）最小的点。这跟支配点有什么关系？带着问题推导到后面就知道了。
我们先设点 \(u\) 的支配点为 \(idom(u)\)，半支配点为 \(sdom(u)\)。
结论 0：
显然能到达 \(u\) 的点集中，只有 \(u\) 的父亲小于 \(u\)，其余均大于 \(u\)。
结论 1：
\(sdom(u)\) 必然小于 \(u\)。
证明：考虑 \(u\) 的父亲就是满足条件的点。
结论 2：
在生成树中，\(idom(u)\) 必然是 \(u\) 的祖先（或本身）。
证明：考虑到从根到 \(u\) 就存在一条路径。
结论 3：
在生成树中，\(sdom(u)\) 必然是 \(u\) 的祖先。
证明：\(sdom(u)\) 小于 \(u\)，而在构建生成树的过程中，如果 \(v\) 小于 \(u\) 且存在 \(v\) 到 \(u\) 的路径，那么树中 \(v\) 一定是 \(u\) 的祖先。
结论 4：
在生成树中，\(idom(u)\) 必然是 \(sdom(u)\) 的祖先（或本身）。
证明：显然。
通过这些结论，我们可以得到第一个定理：
\[sdom(u)=\min(\{v|(v,u)\in E,v<u\}\cup\{sdom(w)|w>u\land\exists v>u,(u,v)\in E,\text{s.t.} w \text{是} v \text{的祖先或} w=v) \]证明：前一半是显然的，并且我们可以知道右边的式子显然要大于等于 \(sdom(u)\)。
然后，我们在半支配路径 \(sdom(u),v_1,v_2,\cdots,v_k,u\) 中找到 \(v_k\) 最小的祖先 （或 \(v_k\)），记为 \(v_j\)，我们接下来证明 \(sdom(u)\) 是满足 \(v_j\) 半支配点条件的点，即证明 \(\forall 1\le i<j,v_i>v_j\)。若存在 \(v_i<v_j\)，那么 \(v_i\) 显然不能作为 \(v_j\) 的祖先，而 \(v_i\) 能到达 \(v_j\)，则说明在建立生成树时，只有 \(2\) 种情况，一种是 \(v_i\) 是 \(v_j\) 的祖先，\(v_i<v_j\)，一种是 \(v_i\) 不为 \(v_j\) 祖先，且 \(v_i>v_j\)。而这两种情况与刚刚的条件不存在交集，故不存在 \(v_i<v_j\)。
所以该式子中包含了 \(sdom(u)\)，我们完成了证明。
于是，我们便有了一种快速求解半支配点的方法。我们按照 dfs 序从后往前做，利用带权并查集维护刚刚的式子即可。
求出来半支配点，我们就可以求解支配树了！
首先有个非常丑陋的方法，也比较难写，非常不推荐。
就是我们在生成树基础上将 \(sdom(u)\) 向 \(u\) 连边，这样会形成一个 DAG，而在 DAG 上跑支配树是简单的。那么为什么这样是对的呢？显然，我们对这种做法的第一感觉是我们丢掉了一些关系，也就是说我们成为支配点的条件较原图变得似乎更宽了。于是我们考虑严谨证明 DAG 上的每一个支配关系在原图中照样存在。
首先在建立生成树时，如果存在从 \(v\) 到 \(u\) 的路径，那么只有 \(2\) 种情况，一种是 \(v\) 是 \(u\) 的祖先，\(v<u\)，一种是 \(v\) 不为 \(u\) 祖先，且 \(v>u\)。
我们只考虑证明先经过一段树边，再经过一段非树边到 \(u\) 的情况（不经过 DAG 情况下的 \(idom(u)\)）。其他情况没有任何必要考虑，如果产生了多次树边和非树边的切换，为什么前面冗余的切换不能全走树边？所以只有这种情况有必要考虑。注意到，经过的这一段非树边可以形成一段符合条件的半支配路径，而半支配边已经建好了，且其支配点肯定是其半支配点的祖先，故在原图中也不可能存在不经过 \(idom(u)\) 就能到达 \(u\) 的情况。
所以，我们可以在这样一个 DAG 中求出支配树。
而第二种方法才是主流方法。这里需要另外两个定理。
定理 1：对于任意节点 \(u\)，设 \(v\) 是 \(sdom(u)\) 到 \(u\) 这条链上半支配点最小的点（不包括 \(u\) 和 \(sdom(u)\)），若 \(sdom(v)\ge sdom(u)\)，则 \(idom(u)=sdom(u)\)。
(注意！链是指树上的链，我学这个内容时理解错了，卡了很久！)
证明：考虑 \(sdom(u)\) 子树外一点 \(v\)，若 \(v\) 能到达 \(u\)，则 \(v>u>sdom(u)\)。所以，首先 \(v\) 不能为 \(sdom(u)\) 的祖先。然后，我们可以发现如果 \(v\) 能到达 \(u\)，会先到达 \(sdom(u)\) 与 \(u\) 之间的路径的一个点 \(w\)，然而如果是这样，\(sdom(w)\) 肯定会小于 \(sdom(u)\)，这并不满足条件。
定理 2：对于任意节点 \(u\)，设 \(v\) 是 \(sdom(u)\) 到 \(u\) 这条链上半支配点最小的点，若 \(sdom(v)<sdom(u)\)，则 \(idom(u)=idom(v)\)。
证明：首先，\(idom(u)\) 肯定是 \(idom(v)\) 的祖先（或 \(idom(v)\)），否则将存在一条路径 \(1\rightarrow idom(v)\rightarrow v\rightarrow u\)。故我们需要证明不存在从 \(1\) 出发不经过 \(idom(v)\) 的路径到 \(u\)。首先这条路径末端肯定会在 \(u\) 与 \(sdom(u)\) 之间（其实是在 \(u\) 和 \(v\) 之间，因为如果在 \(v\) 上面就说明有不经过 \(idom(v)\) 到达 \(v\) 的路径，这是不可能的），因为如果不在并直接到 \(u\)，则 \(sdom(u)\) 将会被更新。然而如果在这条链之间，则相当与 \(sdom(u)\) 到 \(u\) 这条链之间存在一点的半支配点小于 \(idom(v)\)，这绝对不可能。
于是，我们发现这样子就可以转移了。支配树的代码实现非常容易，我们整个按 dfs 序从后往前转移，\(idom\) 和 \(sdom\) 一起求。实现时，我们建立半支配树，每到一个点我们先帮以自己为半支配点的节点求出 \(idom\)，然后再求自己的 \(sdom\)，多么的无私啊，具体实现看代码：
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define eb emplace_back
#define inf 1000000000
#define linf 100000000000000
#define pii pair <int, short>
using namespace std;
constexpr int N = 2e5 + 5, P = 998244353;
inline int rd ()
{
int x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) { if (ch == '-') f = -1; ch = getchar (); }
while (isdigit (ch)) { x = (x << 1) + (x << 3) + ch - 48; ch = getchar (); }
return x * f;
}
int n, m;
vector <int> g[N], fg[N], vec[N];
int dfn[N], id[N], tim;
int idom[N], sdom[N], fa[N];
struct DSU
{
int fa[N], mn[N];
void init ()
{
rep (i, 1, n) fa[i] = mn[i] = i;
}
int find (int x)
{
if (x == fa[x]) return x;
int fx = find (fa[x]);
if (dfn[sdom[mn[x]]] > dfn[sdom[mn[fa[x]]]]) mn[x] = mn[fa[x]];
return fa[x] = fx;
}
} d;
void dfs (int u)
{
id[dfn[u] = ++ tim] = u;
for (auto v : g[u]) if (! dfn[v]) dfs (v), fa[v] = u;
}
int ans[N];
int main ()
{
n = rd (), m = rd ();
rep (i, 1, m)
{
int u = rd (), v = rd ();
g[u].eb (v);
fg[v].eb (u);
}
dfs (1);
rep (i, 1, n) sdom[i] = i;
d.init ();
rrp (i, 1, n)
{
int u = id[i];
if (! u) continue;
for (auto v : vec[u])
{
d.find (v);
if (sdom[d.mn[v]] == u) idom[v] = u;
else idom[v] = d.mn[v]; //为什么可以这样？考虑到最后的点一定会指向自己的sdom，递归过来即可
}
if (i == 1) continue;
for (auto v : fg[u])
{
if (! dfn[v]) continue;
if (dfn[v] < dfn[sdom[u]]) sdom[u] = v;
else
{
d.find (v);
if (dfn[sdom[u]] > dfn[sdom[d.mn[v]]]) sdom[u] = sdom[d.mn[v]];
}
}
vec[sdom[u]].eb (u);//建立半支配树
d.fa[u] = fa[u];//更新父亲，以便求祖先的最小sdom
}
rep (i, 1, n) if (idom[id[i]] ^ sdom[id[i]]) idom[id[i]] = idom[idom[id[i]]];
rrp (i, 2, n)
{
++ ans[id[i]];
ans[idom[id[i]]] += ans[id[i]];
}
++ ans[1];
rep (i, 1, n) printf ("%d ", ans[i]);
}
于是，我们便学会了支配树。
标签：sdom,支配,int,笔记,学习,fa,dfn,idom From： https://www.cnblogs.com/lalaouyehome/p/18303484