-
分析
看到异或不难想到 01Trie。
不难想到，当两个数的值相等的时候，我们可以当这两个点是一个点，因为连边的费用为 \(0\)。
那么对于一个序列 \(n\)，若存在 \(m\) 种不同的权值，那么在 Trie 树上子节点数为 \(2\) 的节点就有 \(m-1\) 个（因为如果一个数新加进来与所有数都不同，那么一定会从已有的树上分出一条新链，使得一个节点的度数加 \(1\)，因为这个节点必是度数为 \(1\) 的非叶节点，所以会新产生一个度数为 \(2\) 的节点），然后我们发现我们实际要处理的边数也是 \(m-1\) 个，而且权值也是这 \(m\) 种。
我们肯定优先选取不连通而且异或值最小的两个数，所以很好想的是在 Trie 树上做 dfs，然后找到深度最大的点取 LCA。
但是这个做法由于要保证两个点不连通，所以不好直接贪心找两个点求LCA使答案最小。
发现有 \(m-1\) 个点的子树数为 \(2\)，而一个点是 LCA 的条件就是子树数为 \(2\)，而且我们只需要 \(m-1\) 个 LCA，同时Trie的左右两颗子树肯定不连通（因为 Trie 树也是一棵树），那么我们发现是 LCA 的点已经确定下来了，就是那些子树数为 \(2\)的点，接下来就是找连边花费最小的两个子节点。
因为是LCA，所以需要连边的两个节点一定是分局两个子树的，所以需要在左右子树各取一个点，保证这两个点的异或和最小。这个还是可以用枚举左左子树内的点在右子树中查询来解决。为了方便枚举，我们要保证子树内的点是连续的，所以我们要先排序。
那么最后的答案就是 \(\sum_{i\in\{x|x有两个子节点\}} \min_{x\in\{x|tr_{i,0}\},y\in\{y|tr_{i,1}\}} x \oplus y\)。、 -
代码
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
constexpr int MAXN(200007);
constexpr int INF(0x3f3f3f3f);
inline void read(int &temp) { cin >> temp; }
int tr[MAXN << 5][2], l[MAXN << 5], r[MAXN << 5], tot;
int a[MAXN], n;
struct Trie{
inline void insert(int x) {
int nw(0), tp(0);
int t = a[x];
for (int i(30); ~i; --i) {
tp = (t >> i) & 1;
if (!tr[nw][tp]) tr[nw][tp] = ++tot;
if (!l[nw]) l[nw] = x;
r[nw] = x;
nw = tr[nw][tp];
}
}
inline int query(int x, int nw, int k) {
if (k == -1) return 0;
int tp = (x >> k) & 1;
if (!tr[nw][tp]) return (1 << k) + query(x, tr[nw][tp ^ 1], k - 1);
return query(x, tr[nw][tp], k - 1);
}
}Kafu;
int dfs(int nw, int k) {
if (k == -1) return 0;
if (!tr[nw][0]) return dfs(tr[nw][1], k - 1);
if (!tr[nw][1]) return dfs(tr[nw][0], k - 1);
int ans(INF);
for (int i(l[tr[nw][0]]); i <= r[tr[nw][0]]; ++i) ans = min(ans, Kafu.query(a[i], tr[nw][1], k - 1) + (1 << k));
return dfs(tr[nw][0], k - 1) + dfs(tr[nw][1], k - 1) + ans;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
read(n);
for (int i(1); i <= n; ++i) read(a[i]);
sort(a + 1, a + n + 1);
for (int i(1); i <= n; ++i) Kafu.insert(i);
cout << dfs(0, 30) << endl;
return 0;
}