牛客多校第五场 B Graph

题意：

给你一颗树，给出边权，可以任意加边删边，要求时刻满足树联通， 且每个环的边权异或和为0， 求最后的最小边权

题解：

前置题目： cf 888G 姿势点: Boruvka 字典树

根据bxzy的题解得: 任意两点间的边权是固定的。因为图始终联通，那么所有点之间都至少有一条边，当通过加边使得超过一条边后，环的异或值为0，所以删掉原边后，剩下的边和原边等价，所以两点间边权固定

通过dfs为每个点分配权值，使得两点间异或值等与边权，就成了cf 888G的题目了，也就是最小异或生成树

完整代码

struct Node {
    int v, nex;
    ll w;
} node[Ma * 2];

int head[Ma], cnt;

void init() {
    memset(head, -1, sizeof head);
    cnt = 0;
}

void add(int u, int v, ll w) {
    node[cnt].v = v, node[cnt].w = w;
    node[cnt].nex = head[u], head[u] = cnt++;
}

const int base = 29;

struct Trie {
    int tr[Ma * base][2];
    vector<int> e[Ma * base]; int tot;
    void insert(int x) {
        int u = 0;
        for (int i = base; i >= 0; i--) {
            int t = (x >> i) & 1;
            if (!tr[u][t]) tr[u][t] = ++tot;
            u = tr[u][t];
            e[u].ep(x);
        }
    }
    int ask(int id, int d, int x) {
        if (d < 0) return 0;
        int t = (x >> d) & 1;
        if (tr[id][t]) return ask(tr[id][t], d - 1, x);
        return ask(tr[id][t ^ 1], d - 1, x) + (1 << d);
    }
    ll solve(int id, int d) {
        int l = tr[id][0], r = tr[id][1];
        ll ans = 0;
        if (l and r) {
            if (e[l].size() > e[r].size()) swap(l, r);
            int mi = numeric_limits<int>::max();
            for (size_t i = 0; i < e[l].size(); ++i)
                cmin(mi, ask(r, d - 1, e[l][i]));
            ans += mi + (1 << d);
        }
        if (l) ans += solve(l, d - 1);
        if (r) ans += solve(r, d - 1);
        return ans;
    }
} tri;

int col[Ma];

void dfs(int u, int fa) {
    qxx(i, u) if (node[i].v != fa) {
        col[node[i].v] = col[u] ^ node[i].w;
        dfs(node[i].v, u);
    }
}

signed main() {
    #if SYNC==0
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif
    init();
    int n; cin >> n;
    rep (i, n - 1) {
        int u, v; ll w; cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    dfs(0, 0);
    for (int i = 0; i < n; i++)
        tri.insert(col[i]);
    cout << tri.solve(0, base) << endl;

    return 0;
}