题目链接：http://poj.org/problem id=3764
题目大意：给定棵树，两节点间有权值，求一条路径，边上的权值异或值最大，并输出这个最大的异或值。
解题思路：挺好的一题，做完后对字典树和异或运算的理解变得更加清晰，a ^b = (a ^ c) ^ (b ^ c),根据树上两节点到根的路径可得两节点间的路径，这在树形题中经常用到。
本题需要静态数组建树，因为节点数最多有300万，动态开辟空间或者用vector肯定超时，vector和map慢得一B.建完树用一遍深搜，求出每个节点到根节点0的异或之和。有了这个信息之后，就很容易得到一条路径的异或值之和，i到根节点的异或值与j到根结点的异或值的异或和就是i节点到j节点路径上的异或值之和。我们用字典树来记录每个节点到根的距离，查询的时候可用贪心找高位不相同的next走(越高位，他们异或得到的值越到，1<<20 > (1<<19 + 1 <<18 ....1<<0))。利用这上面的几点就可以解本题。
测试数据：
4
0 1 3
1 2 4
1 3 6
5
0 1 2
0 2 3
0 3 4
0 4 5
5
1 0 2
2 0 3
3 0 4
4 0 5
代码：
[cpp]
#include
#include
#define MAX 110000
struct edge{
int v,len;
edge *next;
}*head[MAX*3],tr[MAX*3];
int n,ptr,trie[MAX*31][2];
int vis[MAX*3],xxor[MAX*3];
void AddEdge(int a,int b,int c) {
tr[ptr].v = b,tr[ptr].len = c;
tr[ptr].next = head[a],head[a] = &tr[ptr++];
tr[ptr].v = a,tr[ptr].len = c;
tr[ptr].next = head[b],head[b] = &tr[ptr++];
}
int QueryTrie(int orr) {
//传入异或值，返回与它异或最大的值，贪心
int i,j,result = 0,p = 0;
for (i = 30; i >= 0; --i) {
j = (orr >> i) & 1;
if (trie[p][!j] != -1)
result += 1 << i,p = trie[p][!j];
else if (trie[p][j] != -1) p = trie[p][j];
else break;
}
return result;
}
void InsertTrie(int orr) {
//将值or转为为二进制插入字典树
int i,j,k,p = 0;
for (i = 30; i >= 0; --i) {
j = (orr >> i) & 1;
if (trie[p][j] == -1)
trie[p][j] = ptr++;
p = trie[p][j];
}
}
int Solve() {
//找到最大值，并返回
int i,j,k,maxx = 0;
//建立字典树
ptr = 1;
for (i = 0; i < n; ++i) {
k = QueryTrie(xxor[i]);
if (k > maxx) maxx = k;
InsertTrie(xxor[i]);
}
return maxx;
}
void Dfs(int in,int res) {
//深搜，计算每个点到根节点的异或值
vis[in] = 1;
edge *now = head[in];
while (now != NULL) {
int v = now->v;
xxor[v] = res ^ now->len;
if (!vis[v]) Dfs(v,res^now->len);
now = now->next;
}
}
int main()
{
int i,j,k,t,a,b,c;
while (scanf("%d",&n) != EOF) {
memset(vis,0,sizeof(vis));
memset(xxor,0,sizeof(xxor));
memset(trie,-1,sizeof(trie));
memset(head,NULL,sizeof(head));
for (ptr = i = 0; i < n - 1; ++i){
scanf("%d%d%d",&a,&b,&c);
AddEdge(a,b,c);
}
Dfs(0,0);
int ans = Solve();
printf("%d\n",ans);
}
}
本文ZeroClock原创，但可以转载，因为我们是兄弟。
摘自 ZeroClock