考虑 Kruskal 算法的过程，每次找到权值最小的两端点不连通的边并加入生成森林。

而我们面对的是一张完全图，所以考虑将所有点权放到 01-Trie 上，如果有两对点 LCA 深度不同，那么 LCA 较深的点对之间的边的权值一定较小。也就是说，Kruskal 过程中，所有边一定是按照两端点在 01-Trie 上对应的节点的 LCA 由深到浅被考虑的。

那么着眼于同一层之内，我们要对于这一层中的每个点 $u$，在以它的两个儿子为根的子树内，分别找到一个节点，使他们异或的结果最小。并且对于不同的 $u$，我们的选择之间是独立的。

那么我们遍历这颗 01-Trie，对于每个左右儿子都有的节点，枚举左儿子，在右儿子中查询与它异或后的最小值。这样一个叶子节点最多被 $O(\log v)$ 个父亲查询，每次查询 $O(\log v)$，总时间复杂度为 $O(n\log^2v)$。

我们考察 Kruskal 算法的过程：

将所有边按照边权分为一些等价类，按照边权从小到大，依次将等价类中所有边在保证无环的基础上尽量加到森林中，直到构成一棵树。

注意到等价类内部是无序的，那么同一等价类中的不同选法就导致了最小生成树的不同树形。

那么由此看出，在加入所有边权小于 $w$ 的等价类之后，等价类中不存在加入森林后能够使两棵树连接在一起，改变其连通性的边。此时的树的连通情况和将这些等价类中的所有边全部加入的图是一样的，也即，不论等价类内部如何选边，此时树的连通情况是确定的。

这也就是说，不同等价类之间选边方案是独立的。所以我们分别考虑每个等价类的选边方案。

加入所有边权小于 $w$ 的等价类之后，将已经形成的连通块缩点，边权等于 $w$ 的等价类的选边方案数可以运用矩阵树定理简单地求得。