【每日一题】The XOR-longest Path 题解

Description

给定一棵n个点的带权树，求树上最长的异或和路径。

Solution

由异或的性质得到
即根据题目要求，只需要找到一个根节点，然后贪心找跟当前二进制位不同的点即可。
于是先dfs预处理出根节点到每个节点的异或值，同时建立起字典树
然后每次枚举节点 ，在字典树上找最大的匹配结果。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5; 
vector<pair<int, int> > G[N];
int sum[N];
int tot = 0;
int tree[N * 32][2];
void dfs(int u, int par) {
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].first;
        if(v == par) continue;
        sum[v] = (sum[u] ^ G[u][i].second); 
        dfs(v, u);
    }
}
void build(int val, int id) {
    for(int i = (1 << 30); i; i >>= 1) {
        bool p = (val & i);
        if(!tree[id][p]) {
            tree[id][p] = ++tot;
        }
        id = tree[id][p];
    }
}
int query(int val, int id) {
    int ans = 0;
    for(int i = (1 << 30); i; i >>= 1) {
        bool p = (val & i);
        if(tree[id][!p]) {
            ans += i;
            id = tree[id][!p];
        } else id = tree[id][p];
    }
    return ans;
}
int main() {
    int n; cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back({v, w}), G[v].push_back({u, w});
    }
    dfs(1, -1);
    //abort();
    for(int i = 1; i <= n; i++) {
        build(sum[i], 0);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        ans = max(ans, query(sum[i], 0));
    }
    cout << ans << "\n";
    return 0;
}