2020牛客暑期多校训练营（第五场）B - Graph （异或 最小生成树 分治 Trie）

B - Graph

题目链接

1. 每次操作不会改变两点之间的路径异或和
2. 以 1 号点为起点，算出任意一点到 1 号点的异或值 dis[i]（把该值当做 i 号点权值）, 那么任意两点的异或值为 \(dis[i]~xor~ dis[j]\)，该值也是 i, j两点的边权。
3. 计算xor最小生成树即可（模版题），具体来说，将每个点的权值二进制表示后，优先考虑高bit位，分成两组，组内递归解决子问题，组与组之间要找两个异或结果最小的点连边（可以用Trie在O(n*30)实现）。

为什么可以这么做，因为优先考虑了高bit位，比如说我们考虑了第29位，将第29位是1的点分为一组，另外的点分为一组，组与组之间只会连一个边，该边是整个图里面唯一一条含有 \(2^{29}\) 的一条边。如果不这么做，那么一定不止有一条含有\(2^{29}\) 的边。

复杂度\(O(30*n\log n)\)，不到1e8

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)

void err() { cout << "\033[39;0m" << endl; }

template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }

const int N = 100000 + 5;

int n, head[N], ver[N<<1], nxt[N<<1], edge[N<<1], tot;

int dis[N], tr[N*30][2], totn;

ll res;

void add(int x, int y, int z){

    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;

}

void dfs(int x, int fa){

    for(int i = head[x];i;i=nxt[i]){

        int y = ver[i];if(y == fa) continue;

        dis[y] = dis[x] ^ edge[i];

        dfs(y, x);

    }

}

void insert(int x){

    int p = 0;

    for(int i=29;i>=0;i--){

        int c = x >> i & 1;

        if(tr[p][c] == 0) tr[p][c] = ++totn;

        p = tr[p][c];

    }

}

int get(int x) {

    int p = 0, res = 0;

    for(int i=29;i>=0;i--){

        int c = x >> i & 1;

        if(tr[p][c]) {

            p = tr[p][c];

        } else {

            res += 1 << i;

            p = tr[p][c^1];

        }

    }

    return res;

}

void get(int l, int r, int dep) {

    if(dep == -1 || l > r) return;

    int R = dis[r] >> dep & 1;

    int L = dis[l] >> dep & 1;

    if(L == R){ // 整个组按照 dep 位分组，整组一样。

        get(l, r, dep - 1);

        return;

    }

    int mid = l;

    for(int i=l;i<=r;i++) {

        if(dis[i] >> dep & 1) {

            mid = i - 1; break;

        }

    }

    // 子问题递归求解

    get(l, mid, dep-1);

    get(mid+1, r, dep-1);

    for(int i=l;i<=mid;i++) {

        insert(dis[i]); // 插入字典树

    }

    int Min = INT_MAX;

    for(int i=mid+1;i<=r;i++){

        Min = min(Min, get(dis[i]));

    }

    res += Min;

    // 清空

    for(int i=0;i<=totn;i++) tr[i][0] = tr[i][1] = 0;

    totn = 0;

}

int main(){

#ifndef ONLINE_JUDGE

freopen("i.in","r",stdin);

//  freopen("o.out","w",stdout);

#endif

    scanf("%d", &n);

    for(int i = 1;i<n;i++){

        int x, y, z;scanf("%d%d%d", &x, &y, &z);

        x ++; y++;

        add(x, y, z);

        add(y, x, z);

    }

    dfs(1, 0); // 求出所有点到 1 号点的异或和

    sort(dis + 1, dis + 1 + n);

    get(1, n, 29);

    printf("%lld\n", res);

    return 0;

}