Xor-MST

题意翻译

- 给定 $n$ 个结点的无向完全图。每个点有一个点权为 $a_i$。连接 $i$ 号结点和 $j$ 号结点的边的边权为 $a_i\oplus a_j$。 - 求这个图的 MST 的权值。 - $1\le n\le 2\times 10^5$，$0\le a_i< 2^{30}$。

题目描述

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}xora_{j} $ . Calculate the weight of the minimum spanning tree in this graph.

输入输出格式

输入格式

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}<2^{30} $ ) — the numbers assigned to the vertices.

输出格式

Print one number — the weight of the minimum spanning tree in the graph.

输入输出样例

输入样例 #1

5
1 2 3 4 5

输出样例 #1

8

输入样例 #2

4
1 2 3 4

输出样例 #2

8

题意翻译

- 给定 $n$ 个结点的无向完全图。每个点有一个点权为 $a_i$。连接 $i$ 号结点和 $j$ 号结点的边的边权为 $a_i\oplus a_j$。 - 求这个图的 MST 的权值。 - $1\le n\le 2\times 10^5$，$0\le a_i< 2^{30}$。