山月記

給定 \(n\) 個點(diǎn)，\(m\) 條邊的圖 \(G\) 和他的一個生成樹 \(T\)。圖 \(G\) 可能有多個最小生成樹。

詢問是否存在一個點(diǎn) \(x\) 使得 \(T\) 上所有以 \(x\) 為端點(diǎn)的路徑 \(p\)，至少存在一個最小生成樹包含 \(p\)。

一個重要觀察：

在 Kruskal 的過程中，對于任意邊集 \(E=\{e\}\)，不管處理順序如何，最終得到的生成森林連通性相同。

令 \(E\) 取邊權(quán) \(\le w\) 的所有邊，可以得到一個推論：處理完所有邊權(quán) \(\le w\) 的邊之后得到的生成森林 \(G_w\) 連通性相同。

這啟發(fā)我們，不同權(quán)值的邊實(shí)際上是獨(dú)立的。因此我們可以分別考慮每一種權(quán)值的邊。

假如我們想判斷一條路徑是否合法，對于每一種 \(w\)，我們找出路徑上所有權(quán)值為 \(w\) 的邊 \(E_w=\{e\}\)。

這條路徑是合法的，實(shí)際上等價于 \(E_w\) 并上所有邊權(quán) \(\le w-1\) 的邊的最小生成森林 \(G_{w-1}\) 后得到的圖 \(G_w'\) 上無環(huán)。

假如對于每個 \(w\)，\(G_w'\) 無環(huán)都成立，可以通過將 \(E_w\) 內(nèi)的邊放到所有其他權(quán)值為 \(w\) 的邊之前，由于權(quán)值相等，權(quán)值之和保持最小，同時 \(E_w\) 之內(nèi)的邊一定會被選入最小生成樹中。

否則，取出 \(G_w'\) 中任意一個環(huán)，其上最晚被處理到的邊必然權(quán)值為 \(w\)。在處理到這條邊時其兩端的點(diǎn)已經(jīng)連通，其必然會被跳過。那么最終的最小生成樹就不可能包含這條邊。

于是我們現(xiàn)在為了檢查路徑是否合法，只需要維護(hù) \(w\) 個并查集。其中的第 \(i\) 個初始時表示 \(G_{i-1}\) 的連通性。在其中加入權(quán)值為 \(i\) 的所有邊，并維護(hù)環(huán)存在性即可。

更進(jìn)一步地，為了檢查點(diǎn) \(x\) 是否是答案，可以從 \(x\) 開始深搜，改為使用可撤銷并查集維護(hù)加/刪邊。

于是可以得到 \(O(n^2\log n)\) 的解法。

另外一個觀察是：假如一條路徑不合法，那么所有包含它的路徑也不合法。

假如我們?nèi)稳∫粋€根 \(R\)，并依次檢查它到每個兒子的子樹內(nèi)不合法路徑的存在性。

假如 \(R\) 的一個兒子 \(r\) 的子樹中某個點(diǎn) \(r_0\) 滿足路徑 \(R\rightarrow r_0\) 不合法，那么答案只可能在 \(R\rightarrow r_0\) 的路徑上。假如答案不在的話，一定存在某個從答案出發(fā)的路徑完整包含 \(R\rightarrow r_0\) 這條路徑，不合法。

這實(shí)際上允許我們通過點(diǎn)分治解決這個問題。

對于當(dāng)前連通塊，我們找出中心 \(R\)，并 \(O(n\log n)\) 地檢查上述條件。如果不滿足，答案只會在至多一個子樹內(nèi)，遞歸處理即可。

時間復(fù)雜度 \(O(n\log^2 n)\)。