题解 CF888G 【Xor-MST】

妙妙题…… ~~看到$MST$，想到$Kruskal$，看到异或，想到$Trie$~~ 首先我们模拟一下$Kruskal$的流程：找到最小边，如果联通就忽略，未联通就加边 我们把所有点权值加入$0-1\ Trie$中，然后画张图，可以发现有$n-1$个点是有两个儿子的，而其他点都是只有$0/1$个儿子 权值最小的边应该是$Trie$中，$LCA$深度最大的两个数 而且这$n-1$个节点是一些在$Trie$中结尾节点的$LCA$ 所以我们只需要遍历整颗$Trie$，然后对所有可能为$LCA$的点，找到一条最小的边，把它的两颗子树合并起来即可 一个小$trick:$我们可以把所有元素排好序，因为$Trie$上的点从左往右看是递增的，于是$Trie$的每一个节点就会对应排好序的数列中的一段区间，这样就不需要启发式合并之类的复杂操作了 ## $Code:$ ``` #include<bits/stdc++.h> using namespace std; #define int long long #define inf (1 << 30) #define rep(i, s, t) for(int i = s; i <= t; ++ i) #define maxn 200005 int n, m, a[maxn], L[maxn * 32], R[maxn * 32], ch[2][maxn * 32], rt, cnt; void insert(int&k, int id, int dep) { if(!k) k = ++ cnt; if(!L[k]) L[k] = id; R[k] = id; if(dep == -1) return; insert(ch[(a[id] >> dep) & 1][k], id, dep - 1); } int query(int k, int x, int dep) { if(dep == -1) return 0; int v = (x >> dep) & 1; if(ch[v][k]) return query(ch[v][k], x, dep - 1); return query(ch[v ^ 1][k], x, dep - 1) + (1 << dep); } int dfs(int k, int dep) { if(dep == -1) return 0; if(ch[0][k] && ch[1][k]) { int ans = inf; rep(i, L[ch[0][k]], R[ch[0][k]]) { ans = min(ans, query(ch[1][k], a[i], dep - 1) + (1 << dep)); } return dfs(ch[0][k], dep - 1) + dfs(ch[1][k], dep - 1) + ans; } else if(ch[0][k]) return dfs(ch[0][k], dep - 1); else if(ch[1][k]) return dfs(ch[1][k], dep - 1); return 0; } signed main() { scanf("%lld", &n); rep(i, 1, n) scanf("%lld", &a[i]); sort(a + 1, a + n + 1); rep(i, 1, n) insert(rt, i, 30); printf("%lld", dfs(rt, 30)); return 0; } ```