[Codeforces] 1444C
Team-Building
題敘
有 $N$ 個學生，已經分成了 $k$ 組， 現在有 $M$ 組關係表示兩個學生認識， 問有多少種在 $k$ 種內選 $2$ 組的可能， 使得這兩組的學生混合起來可以分成 $2$ 組可以不等大小的隊伍， 並且同隊的學生互不認識。
提示
Hint 1
如果第 $i$ 組跟第 $j$ 組有一種合理的分法， 一定會滿足甚麼性質？
Hint 2
這種性質要怎麼樣快速的維護？
Hint 3
值域有沒有提示某些方法可能複雜度是爛的？
想法
有一個很重要的觀察是： 如果第$i$組跟第$j$組有合理的分法， 這樣他們連接起來的圖一定會是二分圖。
所以我們要快速的把一組合併，再刪掉。 比較合理的情況是對$M$處理，刪掉不合理的組合。 由於每一組關係只會剛好在一組組合裡有用， 所以目前初步的方法大概就是對該組有效的邊去維護是不是二分圖。
但這樣連接同一組的邊會被算到好幾次， 所以要對這種邊進行預處理， 可以先對這種情況預著色， 這樣把兩個連通塊連起來就須要解決一個問題： 預先著色可能是反的。
這個部分可以對每個區塊都計上一個標記： 這個區塊的預先著色有沒有反轉， 但是在合併的時候就會出狀況。
這時候可以考慮兩種做法：
- 用啟發式合併祖先關係的並查集，這樣合併的時候就只要訪問到根被反轉幾次就好。
- 用啟發式合併節點內容的並查集，把小的那一側全部暴力改掉他的反轉標記。
不管怎樣，這樣合併最壞複雜度會是 $\mathcal{O}(M \log N)$， 所以做完所有的邊只要 $\mathcal{O}(M \log N)$的複雜度， 做完之後要重置的點只有 $2M$ 個，暴力改也會是好的。
整理一下想法： 首先先對每組都做一次預著色，把不合理的先扣除， 然後對每個有可能的兩組都做這件事： 不斷的加邊，有兩種 Case：
- 如果在同一個連通塊裡
就判斷是不是有奇環， 查詢時要記得加上原本的標記。 - 如果不在同一個連通塊裡
就把兩個連通塊做啟發式合併， 找大的那邊，看看小的頭會不會是相同的 如果是相同的，就對小的那邊所有的連通塊都打上相反的記號
至此，複雜度是 $\mathcal{O}(M \log M + M \log N)$。