支配樹 瞎學筆記

poisonous

支配樹上支配集，支配樹下我和你。（騙人的，支配樹跟支配集毛關系沒有）

支配樹是用來求解有向圖必經點問題的算法。

（u1s1 算法的證明根本不展現支配樹的本質，學了也是白學，我是強迫症犯了才補上證明的，不要學我）

基礎概念

對于一個有向圖，標明 \(1\)​​​ 為起點（下文都假定 \(1\) 能到所有點，無自環，不失一般性），對節點 \(x,y\)，\(y\) 支配 \(x\) 當且僅當 \(y\) 是 \(1\to x\) 的必經點，稱為 \(x\) 的支配點。不難證明支配關系的自反性、反對稱性、傳遞性。

支配關系還有個類似傳遞性的神奇性質：若 \(x\neq y\) 都支配 \(z\)，則 \(x,y\) 必有支配關系。若不然，任找一條 \(1\to z\) 簡單路徑，由支配性知 \(x,y\) 都在上面：若 \(x\) 離 \(1\) 更近，由于 \(x\) 不支配 \(y\)，是以可以從 \(1\) 繞過 \(x\) 到 \(y\) 再到 \(z\)，與 \(x\) 支配 \(z\) 沖突；\(y\) 更近的情況類似。那麼易證（讀者自證不難）：任取一條 \(1\to x\) 簡單路徑，上面所有 \(x\) 的支配點按離 \(1\) 的距離從近到遠排列依次為 \(1=x_0\to x_1\to\cdots\to x_s=x\)，則對任意 \(i\in[0,s]\) 知道 \(x_i\) 的所有支配點是 \(x_{0\sim i}\)​​。

稱 \(x\) 的所有支配點當中除了自己離自己最近的那個為 \(x\) 的最近支配點，記作 \(idom_x\)，\(idom_1\) DNE。将所有點 \(x\neq 1\) 往 \(idom_x\) 連一條邊，得到一棵以 \(1\) 為根的内向樹。若不然，必定存在大小大于 \(1\) 的環，由傳遞性可知存在 \(x\) 支配 \(idom_x\)，與支配關系的反對稱性沖突。這棵樹就是原圖的支配樹。顯然，\(x\) 的全部支配點就是它在支配樹上的全部祖先，并且排列順序與在原圖任意一條 \(1\to x\) 簡單路徑中離 \(1\) 的距離從近到遠的順序一緻。

支配樹的求法

顯然，若對每個點 \(x\neq 1\)​​​ 都知道了 \(idom_x\)，那麼支配樹自然就求出來了。

外向樹

顯然，以 \(1\) 為根的外向樹的支配樹就是自己的反圖。

DAG

将 DAG 拓撲排序，那麼顯然，加入一個點對拓撲序在它之前的點的導出子圖的支配樹并沒有影響。是以考慮按拓撲序依次加入，每次隻要考慮目前點的最近支配點是誰，插到樹上就可以了。

加入點 \(x\)​ 的時候，考慮所有邊 \((y,x)\)​，由于是按照拓撲序，所有 \(y\)​ 在之前已經考慮過了。設 \(z\)​ 是所有 \(y\)​ 在支配樹上的 LCA，易證有且僅有 \(z\)​ 的所有支配點是 \(x\)​ 的所有支配點，即 \(idom_x=z\)​。

考慮實作。需要實時維護 LCA，考慮樹上倍增，每次接一個葉子，确實是可以動态維護倍增數組的，而且很好寫，複雜度線對。貼個 P2597 的闆子吧。

一般圖的 tarjan 算法

一般有向圖也是有線對複雜度的求支配樹的算法的，叫做 tarjan 算法（Tarjan 老爺子真是 nb，總能發明很難證的算法，而且他自己還總是會證）。雖然 DAG 的特殊求法複雜度跟 tarjan 算法複雜度一樣，但是好寫的很多，是以 DAG 一般還是寫特殊求法。

引入半支配點

找到原圖從 \(1\) 出發的一棵 dfs 樹（Tarjan 老爺子好像很喜歡 dfs 樹耶），不失一般性地，下文認為點 \(i\) 的 dfs 序就是 \(i\)​。對 \(y<x\)，若存在一條 \(y\to x\) 路徑滿足除端點外全程大于 \(x\)，則稱 \(y\) 是 \(x\)​​ 的半支配點。

引理：對 \(x<y\)​，\(x\to y\)​ 的任意一條路徑都必定經過它們在 dfs 樹上的某個公共祖先。證明：設 \(z=\mathrm{LCA}(x,y)\)​，則把 \(z\)​ 的祖先全删除之後 \(x,y\)​ 所在子樹就裂開了，前向邊和後向邊對連通性屁幫助沒有，而橫叉邊隻能是大号點到小号點，是以此時 \(x\)​ 是不能到達 \(y\)​ 的。

跟據引理，不是 \(x\)​​​​ 的祖先的節點 \(y\)​ 一定不是 \(x\)​​ 的半支配點，因為 \(y\to x\)​ 一定經過小于 \(x\)​ 的 \(x\)​ 的祖先（由于 \(y<x\)​，是以 \(y\)​ 不可能是 \(x\)​ 的後代）。

\(x\)​ 的所有支配點也一定是 \(x\)​ 在 dfs 樹上的祖先，若不然，删去之後顯然可以沿着 dfs 樹從 \(1\)​ 走到 \(x\)​。

\(x\)​ 所有支配點都是半支配點的祖先。證明：若存在半支配點 \(y\)​ 是支配點 \(z\)​ 的祖先，則可以先沿 dfs 樹 \(1\to y\)​，然後從 \(y\)​ 走一條全程大于 \(x\)​ 的路徑到 \(x\)​，自然地繞過了 \(z\)​，與支配性沖突。

設 \(x\)​ 的 dfs 序最小的半支配點為最遠半支配點，記作 \(sdom_x\)​，亦即在 dfs 樹上離 \(1\)​ 最近的半支配點。我們有 \(idom_x\leq sdom_x\)​，知道最遠半支配點是對最近支配點的一個良好近似，對求最近支配點有幫助。

最遠半支配點的求法

對點 \(x\neq 1\)​，枚舉所有半支配點到它的路徑的一切可能的前驅 \((y,x)\)：

• 若 \(y<x\) 則直接用 \(y\) 更新 \(sdom_x\)。正确性顯然，充分性的話，由于 \(y<x\)，是以 \(y\) 隻能是半支配點到 \(x\) 的路徑的端點。
• 若 \(y>x\)​，設 \(w=\mathrm{LCA}(x,y)\)​，則用樹上路徑 \(w\to y\)​（掐頭留尾）中所有 \(z\)​ 的 \(sdom_z\)​ 來更新 \(sdom_x\)​。證明：首先 \(x=w\)​ 的情況不證自證，下面考慮 \(x\neq w\)​ 的情況。首先想直接用 \(sdom_y\)​ 更新，但它有可能走區間 \((x,y)\)​ 之間的點 \(u\)​ 啊，這就沒考慮到。若 \(\mathrm{LCA}(u,y)=w\)​，則跟據引理，由 \(u<y\)​ 知道一旦走到了 \(u\)​，就一定要經過 \(w\)​ 的祖先才能到 \(y\)​，這是一定小于 \(x\)​ 的，是以 \(x\)​ 的半支配點到 \(y\)​ 的路徑上小于 \(y\)​ 的隻能是 \(w\to y\)​（掐頭留尾）中所有的 \(z\)​。設從 \(x\)​ 半支配點走到 \(y\)​ 的路徑上第一次交到這條直鍊上交的是 \(z_0\)​，由于是第一次交上，顯然之前走的都大于 \(y\)​，那自然也大于 \(z_0\)​，交上去之後可以直接沿着 dfs 樹走到 \(y\)​，最後走到 \(x\)​。是以這個用所有 \(sdom_z\)​​ 的更新方案是既正确又充分的。​​​

通過最遠半支配點求最近支配點

對點 \(x\neq 1\)​​​​​，我們設路徑 \(p=1\to sdom_x\)​​（留頭去尾），\(q=sdom_x\to x\)​​（掐頭留尾），\(y\)​​ 是 \(q\)​​ 中最遠半支配點最遠（亦即 dfs 序最小）的點，顯然有 \(sdom_y\leq sdom_x\)​​​​​。分成兩種情況：

• 若 \(sdom_y=sdom_x\)​​，則 \(idom_x=sdom_x\)​​。證明：如果 \(sdom_x=1\)​​ 那根據 \(idom_x\leq sdom_x\)​​ 就顯然了，下面考慮 \(sdom_x\neq 1\)​​ 的情況。此時顯然對任意 \(i,j\)​​，\(p_i\)​​ 不半支配 \(q_j\)​​。假設存在 \(1\to x\)​​ 的不經過 \(sdom_x\)​​​ 的簡單路徑，由于 \(1\)​​ 不半支配 \(x\)​​，一定經過小于 \(x\)​​ 的點 \(z\)​​。而由于 \(z<x\)​​，跟據引理 \(z\to x\)​​ 必經過 \(fa_x\)​​ 的祖先。如果祖先為 \(q_i\)​​，那就對 \(1\to q_i\)​​ 重新使用上述分析一直到祖先為 \(p_i\)​​ 為止（一定可實作，因為不能經過 \(sdom_x\)​​​ 哦）。然後又可以對 \(p_i\to x\)​​ 重新施加上述分析得到一個新的 \(p_j\)​​，如此往複得到 \(p_k,p_o,\cdots\)。注意到我們考慮的是簡單路徑，\(p\) 裡所有點遲早都會被得到一遍，就不能繼續了，而我們的分析是可以一直持續下去的，沖突。至此我們知道了 \(sdom_x\) 是 \(x\) 的支配點之一，即 \(sdom_x\leq idom_x\)，結合 \(idom_x\leq sdom_x\)​​，得證。

• 若 \(sdom_y<sdom_x\)​，則 \(idom_x=idom_y\)​​​。證明：顯然有 \(sdom_x<y\)，由 \(idom_x\leq sdom_x\) 知 \(idom_x<y\)。而若 \(idom_x>idom_y\)，此時 \(idom_x\) 一定不支配 \(y\)（否則 \(idom_y\) 應該調整到 \(idom_x\) 這麼近），那麼有避開 \(idom_x\) 的路徑 \(1\to y\)，再沿 dfs 樹走到 \(x\)，與 \(idom_x\) 支配 \(x\) 沖突。是以一定有 \(idom_x\leq idom_y\)，隻要證 \(idom_y\) 支配 \(x\) 則有 \(idom_x=idom_y\)​。

  類似上面，假設存在 \(1\to x\) 的不經過 \(idom_y\) 的簡單路徑。既然不經過 \(idom_y\) 了，那麼直鍊 \(idom_y\to y\) 上面的點都不能經過了，因為一旦交上去便可沿 dfs 樹走到 \(y\)，繞開了 \(idom_y\)，與支配性沖突。由于 \(idom_y\leq sdom_y,y>sdom_x\)，是以 \(sdom_x\) 以上半支配 \(q\)​​ 的點都不能經過了，剩下來的相當于上面那種情況的局面，可以類似上面無限循環來歸謬。

實作

求 \(sdom\)​ 的部分，按 dfs 序從後往前更新顯然是無後效性的。查詢上開下閉的鍊上最值怎麼維護？樹剖？可以巧妙地使用帶權并查集（Tarjan 又一次使用自己的成果！），每更新完一個點就把它往父親合并，易證更新到 \(x\)​ 的時候，\(y\)​ 已經合并到了 \(\mathrm{LCA}(x,y)\)​。​并查集隻能路徑壓縮，不能按秩合并，是以複雜度是一個 \(\log\)。

求 \(idom\) 的部分恰好也涉及上開下閉的鍊上最值查詢，可以竊取之前的并查內建果。但是查詢完之後需要更新的 \(idom\) 資訊應當是按 dfs 序從前往後更新才是沒有後效性的。是以我們可以先把并查集該查的查好存起來（在更新到 \(sdom_x\) 的時候恰好是 \(x\) 的可查狀态，可以用

vector

記錄 todo-list），結束之後再從前往後掃一遍。

注意點：\(1\) 有可能不能到達所有點，枚舉 dfs 序的時候一定是到

nowdfn

instead of

n

。初始化的時候應該把所有點的 dfs 序賦為 \(+\infty\)​，這樣在選取「dfs 序最小的半支配點」時比較函數不會出錯。

支配樹求必經邊

珍愛生命，遠離抄襲！