Codeforces 566E - Restoring Map（bitset 優化構造）

/qiao

Codeforces 題目傳送門 & 洛谷題目傳送門

本來說好的不做，結果今早又忍不住開了道題/qiao

我們稱度為 \(1\) 的點為葉節點，度大于 \(1\) 的點為非葉節點。

首先考慮如何求出葉節點及其連邊情況，這裡不妨假設葉節點個數 \(\ge 3\)​，對于 \(\le 2\)​ 的情況特判掉，具體如何特判見下文。可以發現，對于兩個非葉節點 \(x,y\)​，如果它們之間存在邊相連，那麼就一定存在兩個點，到它們之間距離 \(\le 2\)​ 的點的集合恰好是 \(\{x,y\}\)​，具體構造就是取一個與 \(x\)​ 相連且 \(\ne y\)​ 的點，再取一個與 \(y\)​ 相連且 \(\ne x\)​ 的點。而如果存在兩個點，滿足它們交集恰好是 \(\{x,y\}\)​，那 \(x,y\)​ 之間必然存在邊相連，否則如果 \(x,y\)​ 距離為 \(2\)​，那麼這兩點的交集中如果包含 \(x,y\)​，那麼必然包含 \(x,y\)​ 的公共鄰居，也就是 \(x,y\)​ 中間夾着的那個點，如果 \(x,y\)​ 距離為 \(3\)​，那麼道理也是類似的，如果這兩點的交集中如果包含 \(x,y\)​，那麼必然包含 \(x,y\)​ 的之間的兩個點，如果 \(x,y\) 距離 \(\ge 4\) 那麼不可能存在兩個點，到它們距離 \(\le 2\) 的點集中都包含 \(x,y\)​。這個可以使用 <code>bitset</code> 及其自帶 <code>_Find_first</code> 和 <code>_Find_next</code> 函數解決。

這樣我們可以知道非葉節點之間的連邊情況，接下來考慮如何将葉子挂上去。首先思考如何判斷一個點是否對應一個葉節點的集合，顯然對于一個非葉節點 \(x\) 及一個與其相連的葉節點 \(y\)，必然有 \(y\) 對應的集合完全包含在 \(x\) 對應的集合中，這樣我們周遊到一個點時，我們檢驗是否存在另一個集合完全包含在該集合中，如果有則跳過這個集合。這樣可以保證我們周遊到的所有集合要麼屬于一個葉節點，要麼屬于一個不與任何點相連的非葉節點，對于後者而言顯然不會對答案産生任何影響，是以我們不跳過它也罷。

接下來考慮如何判定一個葉節點的集合連向的是哪個非葉節點，我們去掉該集合中所有葉子節點（顯然在第一步中我們已經知道哪些是葉子節點，而哪些不是），那麼可以發現，去掉葉子節點後的集合，等于所有和與其相連的非葉節點的非葉節點組成的集合，而對于每個非葉節點，我們是知道哪些非葉節點與其相連的，這個同樣可以 <code>bitset</code> 優化。

接下來找出這個非葉節點之後我們就可以知道所有與這個非葉節點相鄰的葉節點了。具體方法就是找到這個集合中所有葉節點，顯然這些葉節點都與這個非葉節點相鄰。

這樣我們就完美地處理了非葉節點個數 \(\ge 3\) 的情況，那如果非葉節點個數 \(\le 3\) 怎麼辦呢？

顯然如果非葉節點個數 \(=1\)，那麼答案就是個菊花圖，随便構造一個菊花圖就行了。

如果非葉節點個數 \(=2\)，那麼所有葉子節點對應的集合大小都 \(&lt;n\)，而這種情況連向什麼非葉節點是不重要的，是以我們仿照上面的過程，即對于一個葉子節點對應的集合，我們找出集合中所有葉子節點，那麼這些葉子節點都應連向同一個非葉節點。

時間複雜度 \(\dfrac{n^3}{\omega}\)。