2022/11/02 做题记录

支配树

定义点比较大小为 dfs 序。

定义 sdom[x] 为 x 的半支配点，其含义为最小的一个点使得存在一条从它开始到 x 的路径使得路径上除起点和终点的点都大于 x。

首先 sdom[x] 一定为 x 的祖先，要不然 sdom[x] 一定在 lca(sdom[x],x) 一个比 x dfs 序更大的子树内（否则因为不可能存在从小的子树到大的子树的横叉边，从 sdom[x] 到 x 的路径一定经过比 x 小的点），而这样的话 `lca(sdom[x],x) 一定更优。

考虑这东西的含义是什么，如果把 sdom[x] 割掉，无法从根不经过 sdom[x]->x 这条链（不含起点终点）到达 x。

求法就是 dfs 序从大到小遍历所有点，枚举路径上上一个点 y 是什么，如果 y 的 dfs 序小于 x 那么路径长度只能为 1，否则在 y 和 y 所有 dfs 序大于 x 的祖先（即已经求出 sdom）中找一个 sdom 最小的尝试更新答案，正确性就是因为不可能存在从小的子树到大的子树的横叉边，那么之后所有点的 dfs 序都一定大于这个子树中最小的点了），于是开一个带权并查集维护当前节点到所有已经加入的祖先的权值最小值即可。

然后考虑 idom 和 sdom 的区别是什么，只可能是 idom 通过某些方式到了一个 sdom->x 链上的点然后到了 x，于是考虑在上一个过程加入 x 时求解所有 sdom 为 x 的点 y 的 idom。

如果上面这种情况存在，那么 x-->y 上一定有一个点 k 能从上面到达（即 sdom[k] < x，否则 idom[y]=sdom[y]，考虑证明 idom[y]=idom[k]，如果 idom[k] 不支配 y 的话，那么考虑删除 idom[k] 后根到 y 的路径上经过 idom[k]->y 路径上的第一个点，如果这个点小于等于 k 那么说明 idom[k] 并不支配 k，否则说明这第一个点的 sdom 小于 sdom[k]，这个 k 并非 sdom 最小的，而 idom[y]>idom[k] 也是不可能的。

于是我们也用那个带权并查集求一下，但这时我们还没有 idom[k]，于是将 idom[y] 设为 k，之后 dfs 序从小往大扫如果 idom[k]!=sdom[k] 就将 idom[k] 设为 idom[idom[k]] 就行。