[算法竞赛进阶指南] 最长异或值路径 (trie+深搜)

题目

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤100000,
0≤u,v<n,
0≤w<231

输入样例：

4
0 1 3
1 2 4
1 3 6

输出样例：

7

样例解释

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

分析：

• 这个题和求最大异或对的题很相似，只是他求的是一条路径上的最大异或值。
• 最大异或对链接：
• 我们知道相同值异或的结果是零，并且与零异或值不变，因此我们，可以先假设某一点为根节点，用深搜求出所有点到他的异或路径值a[i]。
• 那么我们发现对两个叶节点a[i]和a[j]异或的值，就是i到j的异或路径值。因为他们到根节点的那一段是相同的，或者他们的路径就是一起到根节点路径的和。那么相同的异或以后就会零，因此两个叶节点a[i]和a[j]异或的值，就是i到j的异或路径值。
• 那么这个题就成功的转化为了求两个最大异或对的题。

代码：

#include <iostream>
using namespace std;
const int N=1e5+5,NN=2e5+5,M=3e6,bitsum=30;

int head[N],tot;
struct egde{
	int to,w;
	int next;
}edge[NN];

//链式前向星 
void add(int x,int y,int w){ 
	edge[++tot].to=y;
	edge[tot].w=w;
	edge[tot].next=head[x];
	head[x]=tot;
}

int p[N],vis[N];
int trie[M][2],idx;
int n,m;

//深搜求所有节点到根节点的异或值 
void dfs(int x,int sum){
	vis[x]=1;
	for(int i=head[x];i;i=edge[i].next){
		int temp=edge[i].to,kk=edge[i].w;
		if(!vis[temp]) {
			p[temp]=sum^kk;
			dfs(temp,sum^kk);
		}
	}
}

//trie树插入 
void trie_insert(int x){
	int p=0;
	for(int i=bitsum;~i;i--){
		int &s=trie[p][x>>i&1];
		if(!s) s=++idx;
		p=s;
	}
}

//trie查询 
int trie_search(int x){
	int p=0;
	int ans=0;
	for(int i=bitsum;~i;i--){
		int s=x>>i&1;
		if(trie[p][!s]){
			ans+=1<<i;
			p=trie[p][!s];
		}else p=trie[p][s];
	}
	return ans;
}

int main()
{
	int x,y,w;
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>x>>y>>w;
		add(x,y,w);
		add(y,x,w);
	}
	dfs(0,0);
	int ans=0;
//	for(int i=0;i<n;i++){
//		cout<<p[i]<<" ";
//	}
	for(int i=0;i<n;i++){
		trie_insert(p[i]);
	}
	
	for(int i=0;i<n;i++){
		ans=max(ans,trie_search(p[i]));
	}
	cout<<ans<<endl;
	return 0;
}