本文共 2483 字，大约阅读时间需要 8 分钟。

题目描述

给定一棵 $n$ 个点的带权树，结点下标从 $1$ 开始到 $N$ 。寻找树中找两个结点，求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

输入格式

输出格式

输入输出样例

41 2 32 3 42 4 6

输出 #1

7

说明/提示

数据范围

题意：求出一棵带权树上最长的异或路径（所有边权的异或）。

解法 DFS+贪心+01字典树

树上所有点之间都有唯一的路径。设两个节点 $i,j$ ，它们之间的路径上的边权异或值为 $x_{i,j}$ ，于是题意转换为求出：$$\max \{$$

我们知道，一个数异或同一个数两次等于没有异或，所以令根节点为 $root$ ，求 $x_{i,j}=x_{root,i}\oplus x_{root,j}$ ，公共边上的权值被抵消掉了，得到的就是节点 $i$ 到节点 $j$ 的异或路径值。

因此，整个算法过程首先是，对 $root$ 进行DFS，记录它到每个点的异或路径值。然后问题转化为：给定一组数，从中选择两个数进行异或求最大值。也就是，对每一个数，分别解决从一组数中选出一个数与给定的这个数异或最大的子问题。

一般来说，一组数中选取任意个数求最大/最小异或和可以用线性基，选取一个数与给定数求最大/最小异或和则用01字典树解决。实际代码如下：

#include 
   
    using 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;}
    
   

一发就通过了：

转载地址：https://memcpy0.blog.csdn.net/article/details/108320622 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！