#trie#loj 10056 poj 3764 The XOR Largest Path

本文主要是介绍#trie#loj 10056 poj 3764 The XOR Largest Path，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

在n个数中找两个数 $x, y$ ，使x到y的路径异或和最大

分析

可以用一种类似于差分的东西，用一个深搜求出点到根节点的异或值，然后就像The XOR Largest Pair就好了

代码

#include <cstdio>
#include <bitset>
#include <cstring>
struct node{int y,w,next;}e[200000]; std::bitset<31>s;
int ls[100001],d[100001],trie[3100001][2],tot,n,ans;
int in(){int ans=0; char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=ans*10+c-48,c=getchar();return ans;
}
void dfs(int x,int fa){for (int i=ls[x];i;i=e[i].next)if (e[i].y!=fa)d[e[i].y]=d[x]^e[i].w,dfs(e[i].y,x);
}
void add(int x,int y){int w=in();e[++tot]=(node){y,w,ls[x]}; ls[x]=tot;e[++tot]=(node){x,w,ls[y]}; ls[y]=tot;
}
int main(){while (scanf("%d",&n)==1){int x,p; memset(trie,0,sizeof(trie)); memset(ls,0,sizeof(ls)); memset(d,0,sizeof(d));//初始化for (register int i=1;i<n;i++) add(in()+1,in()+1);//建树dfs(1,0); tot=0; ans=0;for (register int i=1;i<=n;i++){s.reset();//初始化for (register int j=0;j<31;j++)if (d[i]&(1<<j)) s[j]=1; p=0;//二进制下d[i]的第j位是1for (register int j=30;j>=0;j--){if (!trie[p][s[j]]) trie[p][s[j]]=++tot;p=trie[p][s[j]];}//建trieint sum=0,p=0;for (register int j=30;j>=0;j--){if (trie[p][1-s[j]]) sum^=1<<j,p=trie[p][1-s[j]];else p=trie[p][s[j]];}//查找相反的边ans=std::max(ans,sum);}printf("%d\n",ans); tot=0;}return 0;
}