欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

The Xor-longest Path(trie树)

程序员文章站 2023-02-07 15:27:59
题目: " 10056. 「一本通 2.3 练习 5」The XOR longest Path" 解析: 做完 " 10051" 后就不是很难了 继续利用异或的性质有$dis(u,v) = dis(1,u)\oplus dis(1,v)$ 把边权放到点上,然后字典树求最大异或值 代码 cpp inc ......

题目:

#10056. 「一本通 2.3 练习 5」the xor-longest path

解析:

做完后就不是很难了
继续利用异或的性质有\(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;