天天看點

P4606 [SDOI2018]戰略遊戲

圓方樹的定義

圓方樹是用來解決仙人掌圖的問題的,那什麼是仙人掌圖呢?

即不存在邊同時屬于多個環的無向連通圖是一棵仙人掌。

要介紹圓方樹,首先要介紹點雙連通分量。

一個點雙連通圖的一個定義是:圖中任意兩不同點之間都有至少兩條點不重複的路徑。

一種簡單的定義:不存在割點的圖。

但這種定義對于兩點一邊的圖時是沒用的,它沒有割點,但是并不能找到兩條不相交的路徑,因為隻有一條路徑。(也可以了解為那一條路徑可以算兩次,但的确沒有相交,因為不經過其他點)。

在點雙連通圖内,一個點可能屬于多個點雙,但是一條邊屬于恰好一個點雙。

更多關于有向圖的強連通分量的知識,請看我的部落格 \(\to\) ​​強連通分量​​

更多關于點雙連通分量的知識,請看我的部落格 \(\to\) ​​雙連通分量​​

關于圓方樹的建圖,也比較簡單,将一個點雙連通分量内的所有邊删去,再将一個點雙連通分量中的每個點向一個建立的點連邊,這個建立的點即是方點。

是以在圓方樹中有 \(n+c\) 個點,其中 \(n\) 是原圖點數,\(c\) 是原圖點雙連通分量的個數。

每個點雙都可以形成一個菊花圖,多個菊花圖通過原圖中的割點連接配接在一起(因為點雙的分隔點是割點)。

顯然,圓方樹中每條邊連接配接一個圓點和一個方點。

在下面這張圖中,\([1,2,3,4,5]\) 是圓點,\([6,7]\) 是方點。

P4606 [SDOI2018]戰略遊戲

而如果圓方樹連通,則有以下性質:

方點之間不會存在連邊。

原圖的割點就是圓方樹中度數大于 \(1\) 的圓點。

圓方數是一棵非常好的樹,即點數等于邊數加 \(1\)。

圓方樹上任意一條路徑上圓點方點間隔分布。

如果圓點的 \(size\) 為 \(1\),那麼一個圓點子樹的 \(size\) 和就是它下面的所有點的數量。

對于一個點雙中的兩點,它們之間簡單路徑的并集,恰好完全等于這個點雙,即同一個點雙中的兩不同點 \(u\),\(v\) 之間一定存在一條簡單路徑經過給定的在同一個點雙内的另一點 \(w\)。也就是說,考慮兩圓點在圓方樹上的路徑,與路徑上經過的方點相鄰的圓點的集合,就等于原圖中兩點簡單路徑上的點集。

如果原圖中某個連通分量隻有一個點,則需要具體情況具體分析,我們在後續讨論中不考慮孤立點。

注意一條邊連接配接兩個點的在這裡不算點雙。

普通圓方樹隻能解決仙人掌圖上的問題,而廣義圓方樹則可以将所有無向圖轉化為圓方樹處理。

廣義圓方樹性質:圓點方點相間,不存在兩個‘’相同形狀‘’的點相連。

與圓方樹不同的是,廣義圓方樹需要把一條邊連接配接兩個點也看成一個點雙,原本兩個圓點有一條邊相連,現在在中間插入一個方點間隔開就好了。

可以參照這張圖

圓方樹的應用

​​洛谷 P4606 [SDOI2018]戰略遊戲​​

給出一個無向圖,和 \(q\) 個詢問,每次給出 \(s\) 個點,問存在幾個點,使得這個點和他相連的邊被去除後,這 \(s\) 個點中,至少存在一對點互不相通。

首先考慮删掉哪些點才能使得圖上原本連通的兩點變為不連通。

顯然删掉兩點的簡單路徑中必經的割點可以使得圖上原本連通的兩點變為不連通。

而這在圓方樹上對應的就是兩點路徑上的圓點。

于是,我們輕松的想到一個辦法: 直接找出所有的圓點不就好了?

然而,我們的時間複雜度是過不去的。

那麼,如何快速求出所有圓點呢? 不妨換一種思路。 對于一個圓方樹,如果我們能找到其包含所有點的最小的連通塊,然後将其減掉 \(s\),就是我們的圓點的數量。

例如這張圖:

P4606 [SDOI2018]戰略遊戲

假設給出的 \(s\) 個點分别為:\(4、5、6、7\)。

則建完圓方樹就變成這樣:

P4606 [SDOI2018]戰略遊戲

圖中沒加深的點就是圓方樹中的方點。

易得,使用 ​<code>​Tarjan​</code>​ 算法建出圓方樹,然後答案就是圓方樹上包含所有關鍵點的最少點數聯通塊的圓點數量減去關鍵點的數量。

為了友善,我們設圓點的權值設為 \(1\) ,方點的權值為 \(0\) ,将點權放到這個點與其父節點的邊上。

然後畫一個圖,發現,如果由 ​<code>​dfs​</code>​ 序從小到大,以此走過所有的點,然後再從第 \(s\) 個點走回第 \(1\) 個點。

在走過路徑中,如果不考慮每相鄰兩個點的 ​<code>​LCA​</code>​(此時我們走的是樹上最短路徑,顯然會經過 ​<code>​LCA​</code>​,這裡說的不考慮就是不把它計入在内),每個點恰好被走了兩次,而這些被走過的點恰好就是我們要求的聯通塊。

不過這樣會有一個問題,就是第一個點和第 \(s\) 個點的 ​<code>​LCA​</code>​ 會不被統計,是以如果這個點是個圓點答案就再加 \(1\)。