这一篇是个人的集训题目心得，看到与洛谷上此题有较大关联，所以放上来了。
题面：
解析：
例图
首先我们要知道，要求出任意两点之间的路径异或和，
e.g.1:G——E:
可以得出G——E的路径异或和等于G——A的异或和异或上E——A的路径异或和。
证明：A——G的路径异或和：ABBDDG;
A——E的路径异或和：AC^CE;
把两个异或起来就是ABBDDGACCE;
e.g.2:G——H(换两个有重复的试试？
可以得出G——H的路径异或和等于G——A的异或和异或上H——A的路径异或和。
证明：A——G的路径异或和：ABBDDG;
A——H的路径异或和：ABBDDH;
把两个异或起来：DG^DH
？？？
为什么两个相同的异或可以抵消呢？
这其实就相当于求ABB=?
我们知道，异或就是按位不进位加法:
1^1=0;
1^0=1;
0^1=1;
0^0=0;
因为是二进制，所以说连续进行两次不进位加法就又返回了原值。
然后就可以得到70%的分数。
要得到100%的分数，我们就要使用一种叫01字典树的做法.
就是把每一个数都转换为二进制，然后转换为一颗字典树，从高位到低位贪心出最大异或和即可。
字典树？
如图：
PS:左下角被挡住的两个单词是inn和int
这是inn, int, at, age, adv, ant这六个单词组成的字典树，我们可以看到，他们每一个单词都有共同开头几个字母。
所以运用一棵字典树，就可以巧妙的按照从跟到其他任意一个节点的方案走出每一个单词。
到了数字里：
因为前文已经说明，要求出任何两个点之间的异或和都可以转换成两者与根之间的关系。
所以，也就可以构造成一颗：01字典树。
其变化就是把字母替换成了0或1，因为单词是又一些字母组成，而一个10进制的数是由一些0和1组成一样。
所以说这样转换后，就可以求贪心求最长异或和了。
比如从根开始找，一直找1就行。
此题与洛谷P4551 最长异或路径很像，但以下代码并不能AC.
代码
#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define maxn 100010
using namespace std
;
struct edge
{
int next
,to
,val
;
}e
[maxn
*2];
int point
[maxn
],cnt
,n
,xorval
[maxn
];
int t
[maxn
*32][2],root
,size
,ans
;
bool vis
[maxn
];
void addedge(int x
,int y
,int val
)
{
e
[++cnt
].next
=point
[x
];
e
[cnt
].to
=y
;
e
[cnt
].val
=val
;
point
[x
]=cnt
;
}
void dfs(int x
)
{
vis
[x
]=1;
for(int i
=point
[x
];i
;i
=e
[i
].next
)
{
int y
=e
[i
].to
;
if(!vis
[y
])
{
xorval
[y
]=xorval
[x
]^e
[i
].val
;
dfs(y
);
}
}
}
void insert(int val
)
{
int x
=root
;
for(int i
=30;i
>=0;i
--)
{
int tmp
=(val
>>i
)&1;
if(t
[x
][tmp
]==-1) t
[x
][tmp
]=++size
;
x
=t
[x
][tmp
];
}
}
void init()
{
memset(t
,-1,sizeof(t
));
memset(e
,0,sizeof(e
));
memset(point
,0,sizeof(point
));
memset(vis
,0,sizeof(vis
));
memset(xorval
,0,sizeof(xorval
));
ans
=cnt
=size
=root
=0;
}
void query(int val
)
{
int x
=root
;
int sum
=0;
for(int i
=30;i
>=0;i
--)
{
int tmp
=(val
>>i
)&1;
if(t
[x
][tmp
^1]==-1)
x
=t
[x
][tmp
];
else
{
x
=t
[x
][tmp
^1];
sum
+=(1<<i
);
}
}
ans
=max(ans
,sum
);
}
int main()
{
while(scanf("%d",&n
)!=EOF)
{
init();
for(int i
=1;i
<n
;i
++)
{
int x
,y
,z
;
scanf("%d%d%d",&x
,&y
,&z
);
x
++;
y
++;
addedge(x
, y
, z
);
addedge(y
, x
, z
);
}
dfs(0);
for(int i
=0;i
<n
;i
++)
insert(xorval
[i
]);
for(int i
=0;i
<n
;i
++)
query(xorval
[i
]);
printf("%d\n",ans
);
}
}
转载于:https://www.cnblogs.com/vercont/p/10210115.html
相关资源：JAVA上百实例源码以及开源项目
