这道题涉及到最小异或生成树，要理解这个首先要明白 01字典树
关于01字典树呢，先来一道板子题hdu4825 ==》Xor Sum
不方便跳转的同学们可以看下面的题
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是在2³¹范围内，但是这里有句话：所有正整数均不超过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;///异或操作相同为零不同为1if(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
84
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

官方题解：

未完待续，天亮再肝 20200801 00:25
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
**/