我们不妨设置一个数组D[x]表示根节点到x的路径上所有的边权的xor值,那么很显然,D[x]=D[father(x)] xor weight(x,father(x)) 也就是D[x节点的父亲]异或上x节点到他父亲的路径.既然如此的话,我们明显发现这道题目D数组是可以通过深度优先搜索求出.
求出所有的D数组,那么x节点到y节点上所有的异或权值就是D[x] xor D[y],换句话来说就是,从根节点到x节点的xor值,和根节点到y节点的xor值,这两条路径重叠了,然后这两条路径就抵消了,因为a xor a=0.本身和本身xor值是0的.
因此我们原问题就转换成为D[1]~D[n]中选择任意两个数,xor的结果值就会变成最大.也就是上一道题目.
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100010];
int son[3000100][2],idx;
void insert(int x)
{
int p=0;
for(int i=30;i>=0;i--)
{
int &s=son[p][x>>i&1];
if(!s)s=++idx;
p=s;
}
}
int query(int x)
{
int res=0,p=0;
for(int i=30;i>=0;i--)
{
int s=x>>i&1;
if(son[p][!s])
{
p=son[p][!s];
res+=1<<i;
}
else
p=son[p][s];
}
return res;
}
int main()
{
int n;scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[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;
}