POJ 3764 The xor-longest Path

Description

In an edge-weighted tree, the xor-length of a path p is defined as the xor sum of the weights of edges on p:

​

⊕ is the xor operator.

We say a path the xor-longest path if it has the largest xor-length. Given an edge-weighted tree with n nodes, can you find the xor-longest path? 　

Input

The input contains several test cases. The first line of each test case contains an integer n(1<=n<=100000), The following n-1 lines each contains three integers u(0 <= u < n),v(0 <= v < n),w(0 <= w < 2^31), which means there is an edge between node u and v of length w.

Output

​ For each test case output the xor-length of the xor-longest path.

Sample Input

4
0 1 3
1 2 4
1 3 6

Sample Output

7

Hint

The xor-longest path is 0->1->2, which has length 7 (=3 ⊕ 4)

Solution

01Trie经典题，求树上两点路径xor和的最大值。

我们可以把问题转化一下，先dfs一遍求出这棵树的树上xor前缀和，设为\(d[i]\)。

那么两点之间路径的xor和其实就是\(d[i]\)^\(d[j]\)（因为xor的性质是a^a=0）

那么就是01Trie的经典操作了。。求两数的xor最大值。套板子即可。

我怎么又忘记POJ有多组数据啊，我怎么又多组数据又忘记清数组啊。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <queue>

#define ll long long
#define inf 0x3f3f3f3f
#define il inline

namespace io {

    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int ll
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar( F[ -- cnt ] ) ;
    }
    #undef I_int

}
using namespace io ;

using namespace std ;

#define N 100100

int n, ch[N * 32][2], tot;
int d[N];
int head[N], cnt;
struct edge {
    int to, nxt, v;
}e[N<<1];

void ins(int u, int v, int w) {
    e[++cnt] = (edge) {v, head[u], w};
    head[u] = cnt;
}

void dfs(int u, int fa) {
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(e[i].to == fa) continue;
        d[v] = d[u] ^ e[i].v;
        dfs(e[i].to, u);
    }
}

void insert(int x) {
    int u = 0;
    for(int i = 30; i >= 0; --i) {
        int c = (x >> i) & 1;
        if(!ch[u][c]) ch[u][c] = ++tot;
        u = ch[u][c];
    }
}

int query(int x) {
    int u = 0, ans = 0;
    for(int i = 30; i >= 0; --i) {
        int c = (x >> i) & 1;
        if(ch[u][c ^ 1]) u = ch[u][c ^ 1], ans += 1ll * (1 << i);
        else u = ch[u][c];
    }
    return ans;
}

int main() {
    while(~scanf("%d", &n)) {
        memset(head, 0, sizeof(head));
        memset(ch, 0, sizeof(ch));
        cnt = 0; tot = 0;
        for(int i = 1, u, v, w; i < n; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            ins(u, v, w); ins(v, u, w);
        }
        memset(d, 0, sizeof(d));
        dfs(0, 0);
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            insert(d[i]);
            ans = max(ans, query(d[i]));
        }
        printf("%d\n", ans);
    }
}