没有施工完，先放上来。

支配树

求出dfs序。

定义：\(y\)为\(x\)的半支配点，当且仅当存在一条\(y\rightarrow x\)的路径，且这条路径掐头去尾之后都有\(dfn>dfn_x\)，且\(y\)为满足这个条件的\(dfn\)最小的点，记为\(semi_x=y\)。

\(fa_x\)显然满足条件，所以有\(dfn_y\le dfn_{fa_x}\)。

定理：\(y\rightarrow x\)的路径必然经过\(lca(x,y)\)。

感性理解一下就好了qwq

由这个定理，可以得到\(y\)必定为\(x\)的祖先。

（为了写的方便，下文有的时候半支配点指满足条件但不是最小的点）

如何求\(semi_x\)？

分情况讨论：要么是\(semi_x\)一步走到了\(x\)；要么是\(semi_x\)先跳到了\(x\)的兄弟节点那里，然后再乱跳一通跳回来；要么是\(semi_x\)跳到了\(x\)的子树内，然后在子树内晃来晃去，最后跳回来。

第一种

建反图之后乱搞即可。

第二种

设\(w\)为\(semi_x\rightarrow x\)路径上的第一个点，那么就会有\(semi_x=semi_w\)。

证明：\(semi_w\)显然满足\(x\)的条件。若\(semi_x<semi_w\)，那么会发现\(semi_x\)满足\(w\)的条件，于是\(semi_w\)不是\(w\)最小的半支配点，矛盾。

所以\(semi_x\ge semi_w\)，所以\(semi_x=semi_w\)。

第三种

其实与第二种一模一样qwq

\(semi_x\)有什么用？

把非树边全都删掉，加上\((semi_x,x)\)的边，支配关系不变。

证明？感性理解一下吧qwq

然后这个图变成了一个DAG，\(O(n\log n)\)乱搞就好了。

支配树学习笔记

原文：https://www.cnblogs.com/p-b-p-b/p/10824905.html