一個mst算法。
其用于求解一些特殊的mst問題。
例題1：CF888F
我們要求一個集合到外面的最小邊。
對于每個集合維護一個trie表示這個集合內的所有數。
維護一個整體trie，表示所有數。
對于每個集合，枚舉這個集合的所有點。然后詢問整體trie減去這個集合trie的最小異或和即可。
時間復雜度\(O(n\log_2^2n)\)
當然還有一個做法：考慮按位分治。把高位為\(1,0\)的都遞歸下去，然后詢問兩個集合的最小異或和。
例題2：at3611
考慮直接套用boruvka算法。
考慮樹上dp。
每個點要記錄最大值，與最大值顏色不同的次大值。
然后這樣子就能求出和一個點距離最近的點。
然后就能用boruvka了。
另一個做法：把所有邊集做若干次mst，排除一定不會選擇的邊。
然后全局做一個mst，答案不變。
考慮點分，考慮跨越重心的路徑。
設\(d_x\)表示\(x\)點到重心的距離。
則我們兩個點\(x,y\)的點權可以被表示成\(d_x+a_x+d_y+a_y\)
令\(p_x=d_x+a_x\)，則連接兩個點\(x,y\)的代價可以被表示成\(p_x+p_y\)
容易發現只要我們求出\(p_x\)的最小值位置\(y\)，把所有點和\(y\)連邊。
這樣子就把跨過分治中心的路徑的mst求出來了。
然后最后做一次mst即可。
例題3：病毒實驗
其實這道題不是boruvka。但是運用了這個算法的思想。
考慮我們怎么判定一個點是否能被拓展。預處理出\(f_s\)表示有\(s\)集合內的方向，最長連續段的長度。
可以在常數時間*\(O(n)\)內預處理。
考慮把矩陣劃分成若干個連通塊，每個連通塊內有一關鍵點\(c\)。從連通塊任意點都能拓展到\(c\)。
一個顯然的性質：如果一個連通塊關鍵點\(b\)能夠走到\(c\)，那么\(b\)所在連通塊不能用于更新答案。
考慮使用這個性質進行bfs?？上r間復雜度沒有改進。
考慮boruvka算法的時間復雜度證明。
每次給一個連通塊通過bfs找到其不在連通塊的出邊。
然后把它和這個出邊所指向的連通塊合并。
如果bfs到一個已經被合并的區域就跳出，不用bfs了
可以發現時間復雜度是\(O(RC\log_2 RC)\)
會發現一個點到的合并只有兩種：
1.和一個區域合并。
2.bfs到一個被合并過的區域。
會發現1情況使兩個連通塊變成一個，2情況使一個連通塊變成\(0\)個。
所以時間復雜度有保證。
例題4：lg6199
考慮在\(T2\)上進行樹分治。
設\(d_x\)表示\(x\)到重心的距離。
連接兩個點的代價就是\(d_x+d_y+T1dis(x,y)\)
建立連通塊在\(T1\)上的虛樹，就轉化成例題2了
例題5：http://www.rzrgm.cn/ctmlpfs/p/14333369.html