题解

$Boruvka$算法流程：

先对于每个点，选择在所有与之相连的边中，权值最小的边，并将这条边加入到最小生成树中。显然这样连出来的边会形成一个森林，并且连边后连通块个数至少减半。然后我们将每个连通块再看成一个点，重复以上算法即可。时间复杂度$O(mlogn)$。

例题：

给定一个$n$个节点的完全图，每个节点有个编号$a_i$,节点$i$和节点$j$之间边的权值为$a_i⨁a_j$,求该图的最小生成树的权值和。

从高位往低位贪心。把所有点按当前位为$0$还是$1$分为两类。显然在执行$Boruvka$算法时，这两类点内部会先形成联通块，然后这两类点间再连一条尽可能小的连边。因此，只要利用$Trie$树得到两类点间的最小边，然后对于两类点内部的连边情况再进行递归处理即可。总复杂度$O(mlogn)$。

！注意！：对于异或问题，存在单调性的问题，利用数位动态规划的思想根据最高位取值为$0/1$将集合划分为两部分进行分治是很常用的做法。