codeforces888G Xor-MST

G. Xor-MST
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given a complete undirected graph with n vertices. A number ai is assigned to each vertex, and the weight of an edge between vertices i and j is equal to ai xor aj.
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 a1, a2, ..., an (0 ≤ ai 30) — the numbers assigned to the vertices.
Output
Print one number — the weight of the minimum spanning tree in the graph.
Examples
input
Copy

5
1 2 3 4 5

output

8

input
Copy

4
1 2 3 4

output

8

제목: n 개의 점 권 을 드 립 니 다. 두 점 을 연결 하 는 대 가 는 ai ^ aj 입 니 다. 최소 생 성 트 리 를 구 합 니 다.
우 리 는 위치 에 따라 계산 하여 0 과 1 을 나 누 어 재 귀 할 수 있 으 며, 만약 최저 위치 만 다르다 면 반드시 연결 해 야 한다.
합병 할 때 우 리 는 1 중의 한 수 와 0 중의 한 수 를 얻 을 수 있 는 차이 점 이나 최소 치 를 합 쳐 야 한다. 우 리 는 01trie 나무 로 조회 하면 된다. 각 층 의 폭력 으로 나 무 를 만 들 고 다음 층 은 나 무 를 없 애 야 한다.
이러한 욕심 은 옳 은 것 이다. 왜냐하면 이 진 은 하나의 숫자 가 지위 의 모든 숫자 보다 더 크기 때문이다.
우 리 는 매번 쓸 수 있 는 최소한 의 대 가 를 썼 기 때문에 틀 리 지 않 을 것 이다.
코드:

#include
using namespace std;
int nex[7000005][2],tot,a[200005],n;
long long ans=0;
void ins(int x)
{
    int now=0;
    for(int i=29;i>=0;i--)
    {
        int t=(x>>i)&1;
        if(nex[now][t]==0) nex[now][t]=++tot;
        now=nex[now][t];
    }
}
int ask(int x)
{
    int res=0,now=0;
    for(int i=29;i>=0;i--)
    {
        int t=(x>>i)&1;
        if(nex[now][t]) now=nex[now][t];
        else now=nex[now][t^1],res|=(1<=r) return;
    int mid=l-1;
    while(mid>dep&1)==0) mid++;
    dfs(l,mid,dep-1),dfs(mid+1,r,dep-1);
    if(mid==l-1||mid==r) return;
    for(int i=l;i<=mid;i++) ins(a[i]);
    int res=2147483647;
    for(int i=mid+1;i<=r;i++) res=min(res,ask(a[i]));
    ans+=res;
    for(int i=0;i<=tot;i++) nex[i][0]=nex[i][1]=0;
    tot=0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    dfs(1,n,29);
    cout<