题解 POJ3764 The xor-longest Path

· · 题解

才疏学浅，不喜勿喷

题目大意

给定一棵的带权树，求树上两个点的最长异或和路径。

题目已经讲的足够清楚，这里就不再赘述。

解题思路

我们可以设 D_x 表示为节点 x 到根节点的异或和。然后我们可以用深度优先遍历求出。但是我们没事干求这个干嘛，其实他是有大用处的哩。

我们要知道 x 到 y 的异或和，其实只需要 D_x\ xor\ D_y 就可以了，那为什么呢， D_x ， D_y 不是到根节点的吗，不会有多的吗，其实按照异或的性质 (a\ xor\ b)\ xor\ (a\ xor\ c)=b\ xor\ c （自反性），他们重叠的路径被抵消掉了，所以这就是他们的异或和。

然后呢，知道怎么计算两点之间的异或和，但是我们要求最长异或和路径。然后呢，我们就可以用Trie了，想必大家都是做过The XOR Largest Pair的，这里就不再赘述如何通过0/1Trie计算最大异或和了，我们只需要计算 D 中的最大异或和就可以得出答案了。

实现细节

具体实现细节请看代码

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;// 因为是双向图，请开二倍题目数据
int n, d[N], tot = 0, trie[N * 32][2], root;

struct Edge {// 使用链式前向星建树
    int to, next, w;
}g[N];

int cnt = 0, head[N];

void add(int u, int v, int w) {// 建图
    g[++ cnt].next = head[u];
    g[cnt].to = v;
    g[cnt].w = w;
    head[u] = cnt;
}

void dfs(int u, int fa) {// 求D数组
    for (int i = head[u]; i; i = g[i].next) {
        int v = g[i].to;
        if (v == fa) continue;// 因为是双向图，防止回到父亲节点
        d[v] = d[u] ^ g[i].w;
        dfs(v, u);
    }
}

// 0/1Trie求最大异或和
void insert(int x) {
    int p = 0;
    for (int i = 31; i >= 0; i --) {
        int c = x >> i & 1;
        if (! trie[p][c]) trie[p][c] = ++ tot;
        p = trie[p][c];
    }
}

int search(int x) {
    int p = 0;
    long long sum = 0;
    for (int i = 31; i >= 0; i --) {
        int c = x >> i & 1;
        if (trie[p][c ^ 1]) p = trie[p][c ^ 1], sum += 1 << i;
        else p = trie[p][c];
    }

    return sum;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; i ++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }

    dfs(1, 1);

    for (int i = 1; i <= n; i ++)
        insert(d[i]);

    int ans = 0;
    for (int i = 1; i <= n; i ++)
        ans = max(ans, search(d[i]));

    printf("%d\n", ans);

    return 0;
}

讲的不好，勿喷