[POJ3764 The xor-longest Path]【异或运算】【Trie树】

【题目大意】给定一棵树，然后一条树的路径的权和定义为路径上边权全部xor之后得出的值

【算法分析】树的话。设d[x]为从根到x这条路径的权。那么两点间的路径权就是d[x] xor d[y]。（LCA到根部分被两次xor抵消啦），然后就转化为给定n个数，求d[x]^d[y]最大。这个就和USACO第6章那个cowxor一模一样啦。利用Trie树求解。

【时间复杂度】O(30*N)

【空间复杂度】O(30*N)

【其它】1Y。在lcc大神空间看到有这题，然后一看题目。。。Orz，再次见面的题目就成水题啦。。。睡前一水。

【CODE】

#include #include #include const int N=100005; struct edge{int y,w;edge *next;}g[N*2],*ls[N]; int n,e,tot; int d[N],L[N],v[N],ch[N*32][2];
void addedge(int x,int y,int w){       g[++e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=&g[e];       g[++e].y=x; g[e].w=w; g[e].next=ls[y]; ls[y]=&g[e]; }
void init(){      int i,x,y,w;      for (e=i=0;i     for (i=1;i          scanf("%d%d%d",&x,&y,&w);           addedge(x,y,w);       } }
void bfs(){      int i,head=-1,tail=0;      for (i=0;i      v[0]=1; L[0]=d[0]=0;      while (head!=tail){             head++;            for (edge *t=ls[L[head]];t;t=t->next)              if (!v[t->y]){                 d[t->y]=d[L[head]]^t->w;                 v[t->y]=1;                 L[++tail]=t->y;               }       } }
void Insert(int x){      int s,p,t;      for (p=1,s=30;s>=0;s--){         t=( (1<       if (!ch[p][t]){           ch[p][t]=++tot;           ch[tot][0]=ch[tot][1]=0;         }         p=ch[p][t];       } }
int Get(int x){     int res=0,s,p,t;     for (p=1,s=30;s>=0;s--){        t=( (1<      if (ch[p][!t]) {p=ch[p][!t]; res|=!t<                else {p=ch[p][t];   res|= t<     }     return res^x; }
void work(){       tot=1;       ch[1][0]=ch[1][1]=0;       Insert(d[0]);      int i,ans=0,now;      for (i=1;i          now=Get(d[i]);          if (now>ans) ans=now;           Insert(d[i]);       }       printf("%dn",ans); }
int main(){     while (scanf("%d",&n)!=EOF){            init();            bfs();            work();      } }