The Xor-longest Path(trie树)

题目：

#10056. 「一本通 2.3 练习 5」The XOR-longest Path

解析：

做完#10051后就不是很难了
继续利用异或的性质有\(dis(u,v) = dis(1,u)\oplus dis(1,v)\)
把边权放到点上，然后字典树求最大异或值

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n, m, num, cnt, tot, ans;
int id[N], a[N], head[N], sum[N];

bool vis[N];

struct node {
    int v, nx, w;
} e[N];

struct trie {
    int nx[2];
} E[N];

inline void add(int u, int v, int w) {
    e[++num].nx = head[u], e[num].v = v, e[num].w = w, head[u] = num;
}

inline void insert(int x) {
    bitset<35>b(x);
    int rt = 0;
    for (int i = 30; i >= 0; --i) {
        int v = (int)b[i];
        if (!E[rt].nx[v]) E[rt].nx[v] = ++cnt;
        rt = E[rt].nx[v];
    }
}

inline int query(int x) {
    bitset<35>b(x);
    int rt = 0, ret = 0;
    for (int i = 30; i >= 0; --i) {
        int v = (int)b[i];
        if (E[rt].nx[v ^ 1]) ret = ret << 1 | 1, rt = E[rt].nx[v ^ 1];
        else ret <<= 1, rt = E[rt].nx[v];
    }
    return ret;
}

void dfs(int u, int w) {
    vis[u] = 1, a[u] = w;
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (!vis[v]) dfs(v, e[i].w ^ w);
    }
}

int main() {
    ios::sync_with_stdio(false);
    memset(head, -1, sizeof head);
    cin >> n;
    for (int i = 1, x, y, z; i < n; ++i) {
        cin >> x >> y >> z;
        add(x, y, z), add(y, x, z);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, query(a[i]));
        insert(a[i]);
    }
    cout << ans;
}
return 0;

原文链接:https://www.cnblogs.com/lykkk/p/11266965.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有