题目大意


题解

这个题的$75$分想法来自Codeforces的$888G$大家可以了解一下
这个题真的好神啊
首先我们先说$25$分
这里就很弱智了233333
对于$20$这个测试点,我们发现所有点的权值是一样的,这样的话$MST$的边权和也就是$0$(详见代码里面$subtask0$这一部分)
然后接下来前面四个测试点我们直接暴力建边跑一个$Kruskal$即可
(代码$subtask1$这一部分)
然后接下来考虑另外一个部分分:$p \leq 1000$
这样的话我们发现$v[i]$的取值很少,并且对于$v[i]=v[j]$,$i,j$这两个点显然已经被一条边长为$0$的边连起来了,这样的话我们只需要考虑$v[i]$不同的然后做一个$MST$即可,复杂度是$O(p^2 log(p))$(这一部分在代码里面的$subtask2$这一部分)
下面我们考虑$16,17$这两个测试点,这两个测试点性质看起来很强,满足$v[i]=i-1$,然后考虑到对于每一个点我们都必须要找到他的父亲并且连边,这样的话我们发现边权最小也只能是$lowbit(v[i])$,然后我们发现$v[i] \ xor \ (v[i]-lowbit(v[i]))=lowbit(v[i])$,这样的话我们从$1-n$扫一遍,每个点都能找到对应的$v[i]-lowbit(v[i])$,时间复杂度$O(n)$,详见代码$subtask3$
接下来考虑优化,也就是$18,19$这两个测试点,我们可以通过枚举$lowbit(v[i])$的取值来进行这个操作,时间复杂度降到了$O(logn)$,详见代码$subtask4$
接下来就是重点的部分
对于一般情况,我们取一个$k$,并将所有点分为两类,所有权值
小于$2^k$的点为$A$类,所有权值大于等于$2^k$的点为$B$类。

当$k$取能使得$AB$两类均非空的最大值时,连接同类点的边权值小
于$2^k$,连接异类点的边权值大于等于$2^k$。显然任意一种最小生成树
的所有边中连接异类点的边有且仅有一条。
这样的话我们可以通过枚举那条连接异类点的边的方式进行递归,显然枚举那条边之后递归成两个子问题,枚举那条边的时间复杂度是$O(n^2)$的
考虑最后的优化
上述的问题其实就是找到异或和的最小,这样我们可以把东西都扔到$Trie$树上面然后贪心向下走,也就是走$0/1$相同的节点,这样的话时间复杂度降到了$O(nlog^2n)$,可以通过$100$分
详见代码里面的$subtask5$

代码