The Xor-longest Path

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1930 字
树上异或距离转 01 Trie 最大异或
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1478
// 题意：给定一棵 n 个点的带边权树，求异或和最大的那条路径的异或和。
// 思路：DFS 求出根到各点的异或距离 d[u]，则任意两点路径的异或和等于 d[u]^d[v]，问题转化成在 d 数组中找两两异或最大值，用 01 Trie 贪心求解。
// 复杂度：O(n × 31) 时间 / O(n × 31) 空间
// 易错点：路径异或和是 d[u]^d[v] 而不是 d[u]+d[v]，两条路径的公共部分异或两次会抵消。
// 易错点：树可能很深，要写成非递归 DFS/BFS，递归容易爆栈。
#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int to;
    int w;
};
struct Node {
    int ch[2];
    Node(){
        ch[0] = ch[1] = 0;
    }
};
vector<Node> tr;
void insertVal(int x){
    int u = 0;
    for(int i = 30; i >= 0; i--){
        int b = (x >> i) & 1;
        if(!tr[u].ch[b]){
            tr[u].ch[b] = (int)tr.size();
            tr.push_back(Node());
        }
        u = tr[u].ch[b];
    }
}
int queryVal(int x){
    int u = 0;
    int res = 0;
    for(int i = 30; i >= 0; i--){
        int b = (x >> i) & 1;
        if(tr[u].ch[b ^ 1]){
            res |= (1 << i);
            u = tr[u].ch[b ^ 1];
        }else{
            u = tr[u].ch[b];
        }
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin >> n)) return 0;
    vector<vector<Edge>> g(n + 1);
    for(int i = 0; i < n - 1; i++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<int> d(n + 1, 0);
    vector<char> vis(n + 1, 0);
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(size_t i = 0; i < g[u].size(); i++){
            int v = g[u][i].to;
            if(vis[v]) continue;
            vis[v] = 1;
            d[v] = d[u] ^ g[u][i].w;
            q.push(v);
        }
    }
    tr.reserve((n + 1) * 31);
    tr.push_back(Node());
    int ans = 0;
    for(int i = 1; i <= n; i++){
        insertVal(d[i]);
        int v = queryVal(d[i]);
        if(v > ans) ans = v;
    }
    cout << ans << "\n";
    return 0;
}
The Xor-longest Path

正文

一本通·提高篇的其它内容
