这是道感觉很不错的题。武森09年的论文中有道题CowXor，求的是线性结构上的，连续序列的异或最大值，用的办法是先预处理出前n项的异或值，然后在这些值中找出两个值的异或值最大。是基于这样的一个原理，相同段的异或值为0。而这道题把它扩展到树上，这也提示了我们，在思考问题的时候，可以把它退化一维去考虑，即从一般到特殊，出题的时候把它升一维。当时比赛的时候，对这道题都不敢去思考，去分析。因此要习惯分析难题，学会去分析，当然多做题，多思考把自己的思维拓宽很重要。然后对于找两个值的异或值最大，最暴力就是枚举，n^2的复杂度，肯定不行，论文中给出了nlgn的复杂度，方法是枚举每个数，把数插入到一颗高度为logn的树中，这是个只有01的编码树，然后对于每个插入的数的二进制表示，在这颗树上匹配，由于数存放的时候是从高位到低位，因此，每次能走不同的就走不同的，这样能保证异或出来的值查询的数与树中的数最大的异或值。预处理的办法是对树DFS一般就可以，感觉这样的方法很巧妙，很多大牛都说显然，大牛就是大牛。
用静态数组吧，之前动态分配，TLE。
感谢：
http://blog.csdn.net/yuhailin060/archive/2010/05/10/5576255.aspx
代码 #include < iostream > #include < string > #include < vector > #include < math.h > using namespace std; const int MAX = 100005 ; struct NODE{ int to, value; // NODE* next; int next; NODE() {} // NODE(int vv, NODE* pp, int tt) : value(vv), next(pp), to(tt) {} NODE( int vv, int pp, int tt) : value(vv), next(pp), to(tt) {}}; // NODE node[ 3 * MAX]; int nodetop; struct newNODE{ // newNODE* to[2]; int to[ 2 ]; int end; newNODE() { // to[0] = to[1] = NULL; to[ 0 ] = to[ 1 ] = - 1 ; end = - 1 ; }}; // *root; newNODE newnode[ 20 * MAX]; int newtop; int root; // NODE* mm[MAX]; int mm[MAX]; int n, ans; void add( int a, int b, int c){ // NODE* p = mm[a]; int p = mm[a]; mm[a] = nodetop; node[nodetop ++ ] = NODE(c, p, b); // mm[a] = new NODE(c, p , b); } void insert( int myxor){ // newNODE* p = root; int p = root; for ( int i = 30 ; i >= 0 ; i -- ) { if (( 1 << i) & myxor) { // 当前位是1 // if(p->to[1] == NULL) p->to[1] = new newNODE(); if (newnode[p].to[ 1 ] == - 1 ) { newnode[p].to[ 1 ] = newtop; newnode[newtop ++ ] = newNODE(); } // p = p->to[1]; p = newnode[p].to[ 1 ]; } else { // 当前位是0 // if(p->to[0] == NULL) p->to[0] = new newNODE(); if (newnode[p].to[ 0 ] == - 1 ) { newnode[p].to[ 0 ] = newtop; newnode[newtop ++ ] = newNODE(); } // p = p->to[0]; p = newnode[p].to[ 0 ]; } } // 标记插入的数值 // p->end = myxor; newnode[p].end = myxor;} void query( int myxor){ // newNODE* p = root; int p = root; for ( int i = 30 ; i >= 0 ; i -- ) { if (( 1 << i) & myxor) { // 当前位是1 // if(p->to[0] != NULL) p = p->to[0]; if (newnode[p].to[ 0 ] != - 1 ) p = newnode[p].to[ 0 ]; // else p = p->to[1]; else p = newnode[p].to[ 1 ]; } else { // 当前位是0 // if(p->to[1] != NULL) p = p->to[1]; if (newnode[p].to[ 1 ] != - 1 ) p = newnode[p].to[ 1 ]; // else p = p->to[0]; else p = newnode[p].to[ 0 ]; } } // ans = max(ans, (myxor ^ (p->end))); ans = max(ans, myxor ^ newnode[p].end);} void dfs( int u, int f, int myxor){ // printf("#%d->%d\n", u, myxor); // 把值插入到树上 insert(myxor); // 到树上贪心查询 query(myxor); // for(NODE* i = mm[u]; i; i = i->next) for ( int i = mm[u]; i != - 1 ; i = node[i].next) { // int v = (*i).to; int v = node[i].to; // int w = (*i).value; int w = node[i].value; if (v != f) { dfs(v, u, (myxor ^ w)); } }} int go(){ ans = 0 ; // root = new newNODE(); nodetop = 0 ; newtop = 1 ; root = 0 ; newnode[root] = newNODE(); dfs( 0 , - 1 , 0 ); return ans;} int main(){ while (scanf( " %d " , & n) != EOF) { // memset(mm, NULL, sizeof(mm)); memset(mm, - 1 , sizeof (mm)); for ( int i = 1 ; i < n; i ++ ) { int a, b, c; scanf( " %d%d%d " , & a, & b, & c); add(a, b, c); add(b, a, c); } printf( " %d\n " , go()); } }
转载于:https://www.cnblogs.com/litstrong/archive/2010/07/29/1788218.html
