POJ 3764--The xor-longest Path---DFS + Trie(最大异或值)

POJ 3764 The xor-longest Path

Time Limit: 2000MS Memory Limit: 65536K

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:

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)

思路

        先选一个根节点dfs遍历获得各个点的dp值，每两个点的路径异或值中相同的路径会因为(a ^ a = 0)而直接忽略，所以我们遍历完后，把dp值中导入Trie中，最后每个点都选取最大异或路径，然后在选取其中的最大值。

#include<iostream>

using namespace std;

const int maxn = 1e5 + 3;

struct Edge {
    int v, w, next;
    Edge(int v = 0, int w = 0, int next = 0): v(v), w(w), next(next) {}
}edge[maxn << 1];

struct Trie {
    int val, next[2];
    void reset() {
        val = next[0] = next[1] = 0;
    }
}tree[maxn << 5];

int dp[maxn], head[maxn];
int ans, cnt;

void init() {
    ans = 0, cnt = 0;
    tree[cnt].reset();
    memset(head, 0, sizeof(head));
    memset(dp, 0, sizeof(dp));
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

void dfs(int now, int father) {
    for (int i = head[now]; i ; i = edge[i].next) {
        if (edge[i].v == father) continue;
        dp[edge[i].v] = dp[now] ^ edge[i].w;
        dfs(edge[i].v, now);
    }
}

void insert(int x) {
    int now = 0, v;
    for (int i = 31; i >= 0; i--) {
        // 取出第i位
        v = (x >> i) & 1;
        // 如果没有遍历过这个点
        if (!tree[now].next[v]) {
            tree[++cnt].reset();
            tree[now].next[v] = cnt;
        }
        now = tree[now].next[v];
    }
    tree[now].val = x;
}

int find(int x) {
    int now = 0, v;
    for (int i = 31; i >= 0; i--) {
        // 取出第i位
        v = (x >> i) & 1;
        // 优先看不一样的点
        if (tree[now].next[v ^ 1]) {
            now = tree[now].next[v ^ 1];
        }
        else {
            now = tree[now].next[v];
        }
    }
    return x ^ tree[now].val;
}

int main() {
    int n, u, v, w;
    while (cin >> n) {
        init();
        for (int i = 1, cnt = 0; i < n; i++) {
            u = read();
            v = read();
            w = read();
            edge[++cnt] = Edge(v, w, head[u]);
            head[u] = cnt;
            edge[++cnt] = Edge(u, w, head[v]);
            head[v] = cnt;
        }
        dfs(0, -1);
        // 建立字典树
        for (int i = 0; i < n; i++) insert(dp[i]);
        // 各自寻找最大异或路径
        for (int i = 0; i < n; i++) ans = max(ans, find(dp[i]));
        cout << ans << endl;
    }
    return 0;
}