异或好啊，异或得学。
因为 yihan 总是学不会，所以决定让大伙一起体验一下这种感觉。但是由于 yihan 比较善良，于是决定不折磨大伙了。（出完发现有原题，但是不管了，相信大伙。）
题目给了一个 n，表示有 n 个点，每个点有一个属于自己的价值。
两个点之间可以花费两点的异或值的代价连一条边，例如（a和b，两个点可以花费a^b的代价在两点之间连一条边）。
请问将 n 个点连到一起要的最小代价和最大代价？（只能有n-1条边）
输入格式:

输入共 2 行。
第一行，一个整数 n （0≤n≤4000），表示总共有 n 个点。
第二行，n 个整数，代表每个点的价值 ai (1≤i≤n,1≤ ai ≤1000000000)，中间以空格隔开。
输出格式:

输出最小价值和最大价值，中间以空格隔开。
输入样例:

在这里给出一组输入。例如：

3
1 2 3

输出样例:

在这里给出相应的输出。例如：

3 5

#include <bits/stdc++.h>
using namespace std;
//kruskal算法解决最小生成树
struct Edge {
    int u, v;
    long long w;
    bool operator<  (const Edge& other) const {
        return w < other.w;
    }
};

struct UnionFind {
    vector<int> parent, rank;

    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x){
            parent[x] = find(parent[x]);
            return parent[x];
        }else  {
            return x;
        }      
    }

    void unite(int x, int y) {
        x = find(x), y = find(y);

        if (x == y) 
            return;

        if (rank[x] < rank[y]) {
            parent[x] = y;
        } else {
            parent[y] = x;
            if (rank[x] == rank[y])
                rank[x]++;
        }
    }
};

pair<long long, long long> kruskal(int n, vector<int>& points) {
    vector<Edge> edges;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            edges.push_back({i, j, (long long)(points[i] ^ points[j])});
        }
    }

    // 计算最小生成树
    sort(edges.begin(), edges.end());
    UnionFind uf_min(n);
    long long min_cost = 0;
    for (auto e = edges.begin(); e != edges.end(); e++) {
        if (uf_min.find(e->u) != uf_min.find(e->v)) {
            uf_min.unite(e->u, e->v);
            min_cost += e->w;
        }
    }

    // 计算最大生成树
    UnionFind uf_max(n);
    long long max_cost = 0;
    for (auto e = edges.rbegin(); e != edges.rend();e++) {
        if (uf_max.find(e->u) != uf_max.find(e->v)) {
            uf_max.unite(e->u, e->v);
            max_cost += e->w;
        }
    }

    return {min_cost, max_cost};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> points(n);
    for (int i = 0; i < n; ++i)
        cin >> points[i];

    auto ans = kruskal(n, points);
    cout<<ans.first<<" "<<ans.second<<endl;

    return 0;
}