这道题涉及到最小异或生成树，要理解这个首先要明白 01字典树
关于01字典树呢，先来一道板子题hdu4825 ==》
不方便跳转的同学们可以看下面的题
Problem Description
Zeus 和 Prometheus 做了一个游戏，Prometheus 给 Zeus 一个 集合，集合中包含了N个正整数，随后 Prometheus 将向 Zeus 发起M次询问，每次询问中包含一个正整数 S ，之后 Zeus 需要在集合当中找出一个正整数 K ，使得 K 与 S 的异或结果最大。Prometheus 为了让 Zeus 看到人类的伟大，随即同意 Zeus 可以向人类求助。你能证明人类的智慧么？
Input
输入包含若干组测试数据，每组测试数据包含若干行。
输入的第一行是一个整数T（T < 10），表示共有T组数据。
每组数据的第一行输入两个正整数N，M（1<=N,M<=100000），接下来一行，包含N个正整数，代表 Zeus 的获得的集合，之后M行，每行一个正整数S，代表 Prometheus 询问的正整数。所有正整数均不超过2^32。
Output
对于每组数据，首先需要输出单独一行”Case #?:”，其中问号处应填入当前的数据组数，组数从1开始计算。
对于每个询问，输出一个正整数K，使得K与S异或值最大。
Sample Input
2 3 2 3 4 5 1 5 4 1 4 6 5 6 3
Sample Output
Case #1: 4 3 Case #2: 4
Source
2014年百度之星程序设计大赛 - 资格赛
题意：
开始先给你一n个数，然后后面有m个询问，问当前询问的数异或上之前的 n 个数中的哪一个值更大。
这就十分体现出了01字典树的优势，将开始的 n 个数按照二进制放到树中，然后在后面的 m 次查询的时候，选出这个数按照二进制每一位和之前存入树里面的 n 个数中每一位尽可能不同的数
这个题有个坑，int是在231范围内，但是这里有句话：所有正整数均不超过2^32。，因此就用long long了叭
code：
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const int maxn=3e6+7; int gen; int tree[maxn][2]; ll val[maxn]; void _add(ll x){ int pos=0; for(int i=32;i>=0;i--){ int op=(x >> i) & 1; if(!tree[pos][op]) tree[pos][op] = ++gen; pos = tree[pos][op]; } val[pos] = x;///当前位置存放的数是 x } ll _find(ll x){ int pos=0; for(int i=32;i>=0;i--){ int op = (x >> i) & 1; ///异或操作相同为零不同为1 if(tree[pos][op^1]) pos=tree[pos][op^1]; else pos = tree[pos][op]; } return val[pos];///返回当前位置的值 } int n,m; int main() { int T=read; int cnt=0; while(T--){ cnt++; printf("Case #%d:\n",cnt); gen=0; for(int i=0;i<=n;i++) val[i]=0; memset(tree,0,sizeof(tree)); n=read,m=read; for(int i=1;i<=n;i++) { ll tt=read; _add(tt); } for(int i=1;i<=m;i++){ ll ask=read; printf("%lld\n",_find(ask)); } } return 0; }
如果还是有的地方不是太懂的话，直接直接跳转 大佬博客 或者是 这篇博客 奉上 学长的博客
到这里其实就可以发现01字典树就是用来求异或最值问题的一种很巧妙的解题方法，算法也十分高效
再看一道这样的题
G. Xor-MST
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given a complete undirected graph with n vertices. A number a i is assigned to each vertex, and the weight of an edge between vertices i and j is equal to a i xor a j.
Calculate the weight of the minimum spanning tree in this graph.
Input
The first line contains n (1 ≤ n ≤ 200000) — the number of vertices in the graph.
The second line contains n integers a 1, a 2, …, a n (0 ≤ a i < 230) — the numbers assigned to the vertices.
Output
Print one number — the weight of the minimum spanning tree in the graph.
Examples
inputCopy
5 1 2 3 4 5
outputCopy
8
inputCopy
4 1 2 3 4
outputCopy
8
首先解释一波题目大意：
给出 n 个点，每个点有个点权，对于之前给出的 n 个数中如果对应的分别是a[ 1 ] ~ a[ n ]，而且连接的两个边是i 和 j 的情况下，那么这个边权就是a[ i ] ^ a[ j ]
题目要求是找到最小的异或生成树
写到这里，纪念下我的第一个跨天的博客诞生
对于上面那个体的代码，听了光光学长讲的，自己写了写，感觉没什么问题，然后非常成功的
然后发现问题之后
照着学长的374ms还是有一定的差距
首先奉上 学长的博客
code:
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const int maxn=3e6+7; ll a[maxn]; int n; struct node{ int gen; int tree[maxn][2];///存树 void init(){///初始化 gen=0; } int left[maxn],right[maxn]; void _add(ll x,int id){ int rt = 0;/// 默认从0开始 for(int i = 32;i >= 0;i --){ int op = (x >> i) & 1; if(!tree[rt][op]) tree[rt][op] = ++gen; rt = tree[rt][op];/// 根转移过去 if(!left[rt]) left[rt] = id; right[rt] = id; } } ///询问根rt下从pos开始与 x 异或得到的最小值 ll _RetPos(int rt,int pos,ll x){ ll ret=0; for(int i = pos;i>=0;i--){ int op=(x >> i) & 1L;/// ill? if(tree[rt][op]) rt = tree[rt][op]; else{ rt = tree[rt][!op]; ret += (1L << i); } } return ret; } /// 分治 ll _Divide(int rt,int pos){ ///在根rt下,左右两棵子树进行遍历 if(tree[rt][0]&&tree[rt][1]){///都存在的的情况下进行合并 ll mi = 0x3f3f3f3f; /// 左右子树 int x = tree[rt][0],y = tree[rt][1]; for(int j = left[x];j <= right[x];j ++){///遍历当前根节点下id范围 mi = min(mi,_RetPos(y,pos - 1,a[j])+(1L << pos)); } return mi+_Divide(tree[rt][0],pos - 1)+_Divide(tree[rt][1],pos - 1); } else if(tree[rt][0]){/// 仅是左面有 && !tree[rt][1] return _Divide(tree[rt][0],pos - 1); } else if(tree[rt][1]){/// 仅是右面有!tree[rt][0] && return _Divide(tree[rt][1],pos - 1); } /// 前面的都不符合 return 0L; } }wuyt; int main() { wuyt.init(); n = read; for(int i=1;i<=n;i++){ a[i] = read; ///wuyt._add(a[i],i); } /// 先排序后插入 sort(a + 1,a + 1 + n); for(int i = 1;i <= n;i ++){ wuyt._add(a[i],i); } printf("%lld\n",wuyt._Divide(0,32)); return 0; } /** 5 1 2 3 4 5 8 4 1 2 3 4 8 **/
01字典树的插入是没有顺序的，可以先将输入的数进行排序，然后进行插入，再插入的时候加上 id 这样一来，在后面 分治操作 _Divide()的时候就十分简便了
步入正题：
牛客第五场B Graph 链接
输入
6 0 1 1 1 2 4 1 3 3 0 4 5 0 5 2
输出
7
官方题解：
code:
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const int maxn=3e6+7; ll a[maxn]; int n,ct=1; struct node{ int gen; int tree[maxn][2];///存树 void init(){///初始化 gen=0; } int left[maxn],right[maxn]; void _add(ll x,int id){ int rt = 0;/// 默认从0开始 for(int i = 32;i >= 0;i --){ int op = (x >> i) & 1; if(!tree[rt][op]) tree[rt][op] = ++gen; rt = tree[rt][op];/// 根转移过去 if(!left[rt]) left[rt] = id; right[rt] = id; } ///val[pos] = x;///当前位置存放的数是 x } ///询问根rt下从pos开始与 x 异或得到的最小值 ll _RetPos(int rt,int pos,ll x){ ll ret=0; for(int i = pos;i>=0;i--){ int op=(x >> i) & 1L;/// ill? if(tree[rt][op]) rt = tree[rt][op]; else{ rt = tree[rt][!op]; ret += (1L << i); } } return ret; } /// 分治 ll _Divide(int rt,int pos){ ///在根rt下,左右两棵子树进行遍历 if(tree[rt][0]&&tree[rt][1]){///都存在的的情况下进行合并 ll mi = 0x3f3f3f3f; /// 左右子树 int x = tree[rt][0],y = tree[rt][1]; for(int j = left[x];j <= right[x];j ++){///遍历当前根节点下id范围 mi = min(mi,_RetPos(y,pos - 1,a[j])+(1L << pos)); } return mi+_Divide(tree[rt][0],pos - 1)+_Divide(tree[rt][1],pos - 1); } else if(tree[rt][0]){/// 仅是左面有 && !tree[rt][1] return _Divide(tree[rt][0],pos - 1); } else if(tree[rt][1]){/// 仅是右面有!tree[rt][0] && return _Divide(tree[rt][1],pos - 1); } /// 前面的都不符合 return 0L; } }wuyt; struct Edge{ int v,next; ll val;/// 边权 }edge[maxn]; int head[maxn]; void _AddEdge(int u,int v,ll val){ edge[++ct] = Edge{v, head[u] , val}; head[u] = ct;///链式前向星存图 } void DFS(int u,int zx,ll val){ a[u] = val;/// for(int j = head[u];j; j=edge[j].next){ int temp = edge[j].v; if(temp == zx) continue ; DFS(temp,u,val^edge[j].val); } } int main() { wuyt.init(); n = read; for(int i=1;i<n;i++){ ll x=read,y=read,val=read; x+=1,y+=1; _AddEdge(x,y,val); _AddEdge(y,x,val); } /// 先排序后插入 DFS(1,1,0);///此时a[]已经存入 sort(a + 1,a + 1 + n); for(int i = 1;i <= n;i ++){ wuyt._add(a[i],i); } printf("%lld\n",wuyt._Divide(0,32)); return 0; } /** 6 0 1 1 1 2 4 1 3 3 0 4 5 0 5 2 **/
