本文共 2483 字，大约阅读时间需要 8 分钟。
题目描述
给定一棵 n n n 个点的带权树，结点下标从 1 1 1 开始到 N N N 。寻找树中找两个结点，求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
输入格式
第一行一个整数 N N N ，表示点数。 接下来 n − 1 n-1 n−1 行，给出 u , v , w u,v,w u,v,w ，分别表示树上的 u u u 点和 v v v 点有连边，边的权值是 w w w 。输出格式
一行，一个整数表示答案。输入输出样例
输入 #141 2 32 3 42 4 6
输出 #1
7
说明/提示
最长异或序列是 1 − 2 − 3 1-2-3 1−2−3 ，答案是 7 ( = 3 ⊕ 4 ) 7 (=3 ⊕ 4) 7(=3⊕4)数据范围
1 ≤ n ≤ 100000 ; 0 < u , v ≤ n ; 0 ≤ w < 2 31 1\le n \le 100000;0 < u,v \le n;0 \le w < 2^{31} 1≤n≤100000;0<u,v≤n;0≤w<231题意：求出一棵带权树上最长的异或路径（所有边权的异或）。
解法 DFS+贪心+01字典树
树上所有点之间都有唯一的路径。设两个节点 i , j i, j i,j ，它们之间的路径上的边权异或值为 x i , j x_{i,j} xi,j ，于是题意转换为求出： max { x i , j ∣ 1 ≤ i , j ≤ N } \max \{\ x_{i,j}\ |\ {1\le i, j\le N}\} max{ xi,j ∣ 1≤i,j≤N}
我们知道，一个数异或同一个数两次等于没有异或，所以令根节点为 r o o t root root ，求 x i , j = x r o o t , i ⊕ x r o o t , j x_{i, j} = x_{root, i} \oplus x_{root, j} xi,j=xroot,i⊕xroot,j ，公共边上的权值被抵消掉了，得到的就是节点 i i i 到节点 j j j 的异或路径值。
因此，整个算法过程首先是，对 r o o t root root 进行DFS，记录它到每个点的异或路径值。然后问题转化为：给定一组数，从中选择两个数进行异或求最大值。也就是，对每一个数，分别解决从一组数中选出一个数与给定的这个数异或最大的子问题。
一般来说，一组数中选取任意个数求最大/最小异或和可以用线性基，选取一个数与给定数求最大/最小异或和则用01字典树解决。实际代码如下：
#includeusing namespace std;const int maxn = 1e5 + 10;struct node { int to, w; node(int a, int b) : to(a), w(b) { } };vector g[maxn];int n, a, b, c, father[maxn], root, xors[maxn], ans = 0; //xors[i]存储树到点i的异或路径值void dfs(int u, int val) { xors[u] = val; for (const node& tmp : g[u]) dfs(tmp.to, val ^ tmp.w);}struct Trie01 { Trie01 *next[2]; int val; Trie01() { memset(next, 0, sizeof(next)); val = 0; } void insert(int x) { Trie01 *cur = this; for (int i = 31; i >= 0; --i) { int v = (x >> i) & 1; if (cur->next[v] == nullptr) cur->next[v] = new Trie01; cur = cur->next[v]; } cur->val = x; } int getMaxXorVal(int x) { Trie01 *cur = this; for (int i = 31; i >= 0; --i) { int v = (x >> i) & 1; if (cur->next[v ^ 1]) cur = cur->next[v ^ 1]; else cur = cur->next[v]; } return cur->val; }};int main() { scanf("%d", &n); //结点数 for (int i = 0; i < n - 1; ++i) { scanf("%d%d%d", &a, &b, &c); g[a].push_back(node(b, c)); father[b] = a; } for (int i = 1; i <= n; ++i) if (!father[i]) { root = i; break; } dfs(root, 0); //在得到的数据xors[]中寻找两个节点,异或和最大 //即对于每一个给定的数xors[i],在xors[]中寻找和它异或后值最大的元素 Trie01 trie; for (int i = 1; i <= n; ++i) trie.insert(xors[i]); for (int i = 1; i <= n; ++i) { int x = trie.getMaxXorVal(xors[i]); if ((x ^ xors[i]) > ans) ans = x ^ xors[i]; } printf("%d\n", ans); return 0;}
一发就通过了：
转载地址：http://faotf.baihongyu.com/