HDU3794+字典树

字典树;
这里字典树用于存储dis这些数。。。然后对于某个数x来说，要使得它变大，就要找到一个与它能“合适”与它异或的数。
View Code
  1 /*
  2 字典树+异或
  3 a^b = (a^c)^(b^c)
  4 */
  5 #include<stdio.h>
  6 #include<string.h>
  7 #include<stdlib.h>
  8 const int maxn = 100005;
  9 const int maxm = 31;
 10 int tree[ maxn*maxm ][ 2 ];
 11 int dis[ maxn ],vis[ maxn ];
 12 struct node{
 13     int u,next,val;
 14 };
 15 node edge[ maxn<<2 ];
 16 int cnt,head[ maxn ];
 17 int tree_index;
 18 
 19 void init(){
 20     memset( dis,0,sizeof( dis ));
 21     memset( vis,0,sizeof( vis ));
 22     cnt = 0;
 23     memset( head,-1,sizeof( head ) );
 24     memset( tree,-1,sizeof( tree ) );
 25 }
 26 
 27 void addedge( int a,int b,int c ){
 28     edge[ cnt ].u = b;
 29     edge[ cnt ].val = c;
 30     edge[ cnt ].next = head[ a ];
 31     head[ a ] = cnt++;
 32 }
 33 
 34 void dfs( int now ){
 35     for( int i=head[ now ];i!=-1;i=edge[ i ].next ){
 36         int u = edge[ i ].u;
 37         if( vis[ u ] == 0 ){
 38             vis[ u ] = 1;
 39             dis[ u ] = dis[ now ]^edge[ i ].val;
 40             dfs( u );
 41         }
 42     }
 43     return ;
 44 }//求出其他点到根的异或值
 45 
 46 int find_the_max( int aim ){
 47     int res = 0;
 48     int id = 0;
 49     for( int i=30;i>=0;i-- ){
 50         int one_bit = (aim>>i)&1;
 51         if( one_bit==0 ){
 52             if( tree[ id ][ 1 ]!=-1 ){
 53                 res += 1<<i;
 54                 id = tree[ id ][ 1 ];
 55             }
 56             else if( tree[ id ][ 0 ]!=-1 ) id = tree[ id ][ 0 ];
 57             else break;
 58         }
 59         else if( one_bit==1 ){
 60             if( tree[ id ][ 0 ]!=-1 ){
 61                 res += 1<<i;
 62                 id = tree[ id ][ 0 ];
 63             }
 64             else if( tree[ id ][ 1 ]!=-1 ) id = tree[ id ][ 1 ];
 65             else break;
 66         }
 67     }
 68     return res;
 69 }/*贪心，对于当前一个数x，异或某个数y之后变大，必须求一个数从高位到低位和x不同的。。*/
 70 
 71 void rebuild_tree( int aim ){
 72     int id = 0;
 73     for( int i=30;i>=0;i-- ){
 74         int one_bit = (aim>>i)&1;
 75         if( tree[ id ][ one_bit ]==-1 ){
 76             tree[ id ][ one_bit ] = tree_index++;
 77         }
 78         id = tree[ id ][ one_bit ];
 79     }
 80     return ;
 81 }//把dis[]变为2进制，存入字典数（从当前的tree_index开始存储）        
 82 
 83 void solve( int n ){
 84     int ans = 0;
 85     tree_index = 1;
 86     for( int i=0;i<n;i++ ){
 87         int tmp_ans = find_the_max( dis[ i ] );
 88         if( tmp_ans>ans ) ans = tmp_ans;
 89         rebuild_tree( dis[i] );
 90     }
 91     printf("%d\n",ans);
 92     return ;
 93 }
 94 
 95 int main(){
 96     int n;
 97     while( scanf("%d",&n)!=EOF ){
 98         int a,b,c;
 99         init();
100         for( int i=0;i<n-1;i++ ){
101             scanf("%d%d%d",&a,&b,&c);
102             addedge( a,b,c );
103             addedge( b,a,c );
104         }
105         
106         vis[ 0 ] = 1;
107         dfs( 0 );
108         //for( int i=0;i<n;i++ )
109         //    printf("dis[%d]=%d\n",i,dis[i]);
110         solve( n );
111         
112     }
113     return 0;
114 }
keep moving...