算法进阶指南---0x16(Trie) The xor-longest Path

题面

算法进阶指南---0x16(Trie)	The xor-longest Path

输入样例

4
0 1 3
1 2 4
1 3 6

输出样例

7

算法进阶指南---0x16(Trie)	The xor-longest Path

题解

算法进阶指南---0x16(Trie)	The xor-longest Path

  1. 如图,给定一颗树(不一定是二叉树),树中每条边都有对应的权值,任意两个点都是能互相到达的,让我们找两个点路径异或和最大,现在一看到异或和最大就想到了Trie,哈哈哈 ,看图,任取两个点a,b 对于ab两点之间的路径异或和我们可以分成两部分,就是他们分别到根节点路径和(图中蓝红两部分),然后将这两部分异或,就可以得到结果
  1. 那么如何找两点的最大呢,对于图中的树,我们可以用 dfs 算出所有点到根节点路径的异或和,用a数组存储,然后这样就转化成01异或和模板了(具体点这里),就是将这些存储的值建成一颗01字典树,对于每个ai,我们在字典树中找到异或最大,然后和结果比较更新答案即可

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 2e5 + 10;

int n;
//数组模拟邻接表存树
int h[N], e[N], c[N], ne[N], cnt;
bool st[N];
int a[N];
//Trie的存储
int tr[N * 30][2], id[N * 31], idx;

//添加a->b的边
void add(int u, int v, int w) {
    e[cnt] = v;
    c[cnt] = w;
    ne[cnt] = h[u];
    h[u] = cnt;
    cnt++;
}

//树的遍历
void dfs(int u, int sum) {
    a[u] = sum;
    st[u] = true;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) dfs(j, sum ^ c[i]);
    }
}

//Trie的插入
void insert(int x) {
    int p = 0;
    for (int i = 31; i >= 0; i--) {
        int v = x >> i & 1;
        if (!tr[p][v]) tr[p][v] = ++idx;
        p = tr[p][v];
    }
    id[p] = x;
}

//Trie的查询
int query(int x) {
    int p = 0;
    for (int i = 31; i >= 0; i--) {
        int v = x >> i & 1;
        if (tr[p][v ^ 1]) p = tr[p][v ^ 1];
        else p = tr[p][v];
    }
    return x ^ id[p];
}

int main() {

    memset(h, -1, sizeof h);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }

    dfs(0, 0);


    for (int i = 0; i < n; i++) insert(a[i]);

    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, query(a[i]));

    cout << res << endl;

    return 0;
}
上一篇:AT4996-[AGC034F]RNG and XOR【FWT,生成函数】


下一篇:位运算_233