題敘

Link
有$N$個學生，已經分成了$k$組，
現在有$M$組關係表示兩個學生認識，
問有多少種在$k$種內選$2$組的可能，
使得這兩組的學生混合起來可以分成$2$組可以不等大小的隊伍，
並且同隊的學生互不認識。

提示

Hint 1

如果第$i$組跟第$j$組有一種合理的分法，
一定會滿足甚麼性質？
　

Hint 2

這種性質要怎麼樣快速的維護？
　

Hint 3

值域有沒有提示某些方法可能複雜度是爛的？ 　
$\newline$　

想法

有一個很重要的觀察是：
如果第$i$組跟第$j$組有合理的分法，
這樣他們連接起來的圖一定會是二分圖。

所以我們要快速的把一組合併，再刪掉。
比較合理的情況是對$M$處理，刪掉不合理的組合。
由於每一組關係只會剛好在一組組合裡有用，
所以目前初步的方法大概就是對該組有效的邊去維護是不是二分圖，

但這樣連接同一組的邊會被算到好幾次，
所以要對這種邊進行預處理，
可以先對這種情況預著色，
這樣把兩個連通塊連起來就須要解決一個問題：
預先著色可能是反的。

這個部分可以對每個區塊都計上一個標記：
這個區塊的預先著色有沒有反轉，
但是在合併的時候就會出狀況， 這時候可以考慮兩種做法：

• 用啟發式合併祖先關係的並查集，這樣合併的時候就只要訪問到根被反轉幾次就好。
• 用啟發式合併節點內容的並查集，把小的那一側全部暴力改掉他的反轉標記。

不管怎樣，這樣合併最壞複雜度會是$\mathcal{O}(M \log N)$，
所以做完所有的邊只要$\mathcal{O}(M \log N)$的複雜度，
做完之後要重置的點只有$2M$個，暴力改也會是好的。

整理一下想法：
首先先對每組都做一次預著色，把不合理的先扣除，
然後對每個有可能的兩組都做這件事：
不斷的加邊，有兩種 Case：

• 如果在同一個連通塊裡
  就判斷是不是有奇環，
  查詢時要記得加上原本的標記。
• 如果不在同一個連通塊裡
  就把兩個連通塊做啟發式合併，
  找大的那邊，看看小的頭會不會是相同的
  如果是相同的，就對小的那邊所有的連通塊都打上相反的記號

至此，複雜度是$\mathcal{O}(M \log M + M \log N)$。

AC Code

Link