题目链接

算法竞赛进阶指南-58.最长异或值路径

给定一个树，树上的边都具有权值。

树中一条路径的异或长度被定义为路径上所有边的权值的异或和：

$_{xor}lenth(p) = ⊕_{e\in p}w(e)$

$⊕$ 为异或符号。

给定上述的具有 $n$ 个节点的树，你能找到异或长度最大的路径吗？

输入格式

第一行包含整数 $n$，表示树的节点数目。

接下来 $n-1$ 行，每行包括三个整数 $u，v，w$，表示节点 $u$ 和节点 $v$ 之间有一条边权重为 $w$。

输出格式

输出一个整数，表示异或长度最大的路径的最大异或和。

数据范围

$1 \le n \le 100000$,
$0 \le u,v < n$,
$0 \le w <2^{31}$

输入样例：

4
0 1 3
1 2 4
1 3 6

输出样例：

7

样例解释

样例中最长异或值路径应为 0->1->2，值为 $7 (=3 ⊕ 4)$

Method : 位运算-二进制拆分

注意到$f(a, b) = f(a, root) \oplus f(b, root)$，因此
求出树上每个点到根结点的异或路径$A_i$(dfs)，然后存入Trie，就能转化成上一题 算法竞赛进阶指南-57.最大异或对

#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 7;
const int M = N * 31;
const int ALPHABETS_SIZE = 2;

struct Edge{
    int to;
    int w;  // 无权图，可以没有w或者w置为1
    int nxt;
};

struct Trie {
private:
    int son[M][ALPHABETS_SIZE], idx = 0;
public:
    void insert(int x) {
        int p = 0;
        for (int i = 30; i >= 0; i --) {
            int t = x >> i & 1;
            if (!son[p][t]) {
                son[p][t] = ++idx;
            }
            p = son[p][t];
        }
    }
    
    int query(int x) {
        int res = 0;
        int p = 0;
        for (int i = 30; i >= 0; i --) {
            int t = x >> i & 1;
            if (son[p][!t]) {
                p = son[p][!t];
                res = (res << 1) + !t;
            }
            else {
                p = son[p][t];
                res = (res << 1) + t;
            }
        }
        return res;
    }
};

int a[N];
Trie trie;
// 链式前向星
int head[N], idx = 0;
Edge edge[2 * N];

void add(int from, int to , int w) {
    edge[idx].to = to;
    edge[idx].w = w;
    edge[idx].nxt = head[from];
    head[from] = idx ++;
}

void dfs(int u, int father, int sum) {
    a[u] = sum;
    for (int i = head[u]; i != -1; i = edge[i].nxt) {
        int j = edge[i].to;
        if (j != father) dfs(j, u, sum ^ edge[i].w);
    }
}

int main() {
    int n;
    cin >> n;
    memset(head, -1, sizeof head);
    for (int i = 0; i < n - 1; i ++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }
    
    dfs(0, -1, 0);
    
    int res = 0;
    for (int i = 0; i < n; i ++) {
        trie.insert(a[i]);
        int t = trie.query(a[i]);
        res = max(res, a[i] ^ t);
    }
    
    cout << res << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：${O(31 * n)}$， 其中31是二进制位枚举，n是枚举a[i]。
• 空间复杂度：${O(M * ALPHABET\_SIZE)}$，M是字符串个数 * 单个字符串的最大长度。

本题同样卡vector<Trie*>，链表new动态分配内存导致MLE