支配树
CarroT1212
·
·
算法·理论
## “支配”
+ $x$ 支配 $y$（$xDy$）：从有向图上一个**固定起点** $s$ 出发，到 $y$ 的路径全部经过 $x$。多个起点的情况可以建超级源。
+ 支配是一种偏序关系。
+ 如果对每个 $y$ 只保留最近的 $x$，支配关系可以形成一棵树，称其为支配树。$x$ 称为 $y$ 的直接支配点 $idom_y$。
容易 $O(n^2)$ 构建一般图的支配树。
DAG 的支配树构建：按拓扑序遍历，每次一个点的 $idom$ 就是，它在原图上的所有前驱在支配树上的 LCA。正确性显然。
## Lengauer-Tarjan 算法构建一般图支配树
### 一些定义和性质
先以起点为根建一棵 dfs 树。把所有点按 dfn 重标号。以下“祖先”等概念均在 dfs 树上定义。
+ 横叉边或返祖边 $x\to y$ 一定满足 $x>y$。
+ $idom_x$ 是 $x$ 的祖先。
+ 若 $x<y$，那么 $x\too y$ 的所有路径一定都经过了 $lca(x,y)$。
+ $x$ 每次通过返祖边或横叉边上移都不可能让它们的 lca 变大。
定义 $x$ 的半支配点 $sdom_x$：最小的点满足，存在一条路径从 $sdom_x\too x$，且路径上除两端外的所有点都 $>x$。称一条满足上述条件的路径为好路径。
+ $sdom_x<x$ 且 $sdom_x$ 是 $x$ 的祖先。
+ $sdom_x\too x$ 的树上路径中，除两端外的所有点都不可能成为 $x$ 及其后代的支配点。
+ $idom_x$ 一定是 $sdom_x$ 的祖先或者 $sdom_x$ 本身。
### 求解半支配点
$$sdom_x=\min(\{u\mid u<x,(u,x)\in E\}\bigcup\{sdom_y\mid y>x,\exist u:(u,x)\in E,y\in anc(u)\})$$
也就是说 $sdom_x$ 为此两者的最小值：
+ $<x$ 且有 $u\to x$ 连边的 $u$。
+ 满足“点 $y>x$ 且 $y$ 为某个有 $u\to x$ 连边的点 $u$ 的祖先”的 $sdom_y$。
> 对于前者，显然处理了 $sdom_x\too x$ 没有中间点的情况。
>
> 否则在后者处理。这么做的想法是考虑 $sdom_x\too x$ 中最后一条边 $v\to x$，$v>x$。用 $sdom_v$ 直接更新可以保证合法性，但是会漏解，因为这样只考虑了 $sdom_x\too x$ 路径上点 $\ge v$ 的情况，而要求只是 $>x$。
>
> 考虑 $sdom_x\too x$ 的最小点实际上出现在什么地方，设其为 $y$。那它应满足 $x<y\le v$。事实上 $y$ 一定是 $v$ 的祖先。否则，$y\too v$ 一定会经过 $lca(y,v)\le y$，和 $y$ 的最小性矛盾。那么就得到了上述式子。
于是可以快速实现半支配点 $sdom_x$ 的求解：倒序遍历 $n\to 1$，用带权并查集维护每个点的祖先中已经更新过的 $sdom$ 最小值。
### 求解直接支配点
有一种直接的做法是，直接在 dfs 树上添加所有 $sdom_x\to x$ 得到一个 DAG，对此 DAG 求支配树即可。不过普遍不这么做。
考虑之前的这么一条性质：“$sdom_x\too x$ 的树上路径中，除两端外的所有点都不可能成为 $x$ 及其后代的支配点。”
也就是说对于点 $x$，$y$ 为 $x$ 的祖先，如果存在 $u$ 为 $x$ 的祖先（或 $x$ 自身），使点 $y$ 被 $sdom_u\too u$ 的树上路径（不含两端）覆盖，那么 $y$ 就不可能成为点 $x$ 的支配点。
那反过来，如果 $y$ 没有被任何一个 $sdom_u\too u$ 覆盖，那它是不是就可以作为 $x$ 的支配点了呢？
这是对的。
> 考虑如果存在不经过 $y$ 的路径 $s\too x$，那这样的路径中一定有满足如下形式的：在 $s\too x$ 的树上路径中，$u,v$ 为 $y$ 两侧的某两个点，那么路径形如 $s\too u\too v\too x$。其中 $u\too v$ 除 $u,v$ 外，没有经过 $s\too x$ 树上路径中的任何一个点。
>
> 如果 $u\too v$ 这一段经过了除 $u$ 外 $<v$ 的点 $z$，那根据之前的性质，它在走到 $v$ 之前一定到过 $lca(v,z)$。这不符合上面的限制。否则，$y$ 就被 $sdom_v\too v$ 盖住了，矛盾。
于是一个易于求解的描述形式出现了：设 $v$ 为 $sdom_x\to x$（不含 $sdom_x$）上 $sdom_v$ 最小的点。有：
$$idom_x=\begin{cases}sdom_x&sdom_v=sdom_x\\idom_v&\text{otherwise.}\end{cases}$$
实现方面，$v$ 的预处理可以在 $sdom$ 的部分一起做。把每个 $i$ 的求 $v$ 挂到 $sdom_i$ 上。
### 代码
```cpp
ll n,m,dfn[N],cnn,co[N],fa[N],sd[N],id[N],sz[N];
vector<ll> e[N],e1[N],qv[N];
void dfs(ll p) {
dfn[p]=++cnn,co[cnn]=p;
for (ll i:e[p]) if (!dfn[i]) fa[i]=p,dfs(i);
}
struct dsu {
ll f[N],ps[N];
void ini(ll n,ll *a) { iota(f+1,f+n+1,1); for (ll i=1;i<=n;i++) ps[i]=a[i]; }
ll fnd(ll x) {
if (f[x]==x) return x;
ll ff=f[x]; f[x]=fnd(f[x]);
if (sd[ps[ff]]<sd[ps[x]]) ps[x]=ps[ff];
return f[x];
}
ll get(ll x) { return fnd(x),ps[x]; }
void mrg(ll x,ll y) { f[fnd(x)]=fnd(y); }
} D;
void mian() {
scanf("%lld%lld",&n,&m);
for (ll i=1,x,y;i<=m;i++) {
scanf("%lld%lld",&x,&y);
if (x!=y) e[x].pb(y),e1[y].pb(x);
}
dfs(1),D.ini(n,co);
for (ll i=1;i<=n;i++) sd[i]=J;
for (ll ii=n;ii;ii--) { ll i=co[ii];
for (ll j:qv[i]) id[j]=D.get(dfn[j]);
sd[i]=ii;
if (ii==1) break;
for (ll j:e1[i]) {
if (dfn[j]<dfn[i]) sd[i]=min(sd[i],dfn[j]);
else sd[i]=min(sd[i],sd[D.get(dfn[j])]);
}
D.mrg(dfn[i],dfn[fa[i]]),qv[co[sd[i]]].pb(i);
}
for (ll ii=2;ii<=n;ii++) { ll i=co[ii]; id[i]=sd[id[i]]==sd[i]?sd[i]:id[id[i]]; }
for (ll ii=n;ii;ii--) { ll i=co[ii]; sz[i]++,sz[co[id[i]]]+=sz[i]; }
for (ll i=1;i<=n;i++) cout<<sz[i]<<" ";
}
```