Link

Sol

01 Trie 入门题

类似于在树上求路径和的方法,路径 $(u,v)$ 异或和也可以拆成 $u$ 到树根和树根到 $v$ 两段. 只要是满足结合律的性质的运算都可以这么做.

要让两段异或起来的值最大, 也就是尽可能地选 $1$. 并且高位上的 $1$ 要优先于低位上的 $1$. 所以,首先预处理所有节点到根路径上的异或和, 把它们插到 01 Trie 上, 然后询问每一个异或和, 如果那一位与 $1$ 异或存在一个 $1$ ,那么就要先选.比较所有的最大值即可.

Code

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

const int SIZE = 1e6 + 5;

int n, num, tot;
int head[SIZE], f[SIZE], ch[SIZE][2];

struct node {
    int to, v, nxt;
} edge[SIZE << 1];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
} using GTR::read;

void addEdge(int u, int v, int d) {
    edge[++ num] = (node) {v, d, head[u]}, head[u] = num;
}

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

int query(int x) {
    int p = 1, res = 0;
    for (int i = 30; ~i; -- i) {
        int opt = (x >> i) & 1;
        if (ch[p][opt ^ 1]) p = ch[p][opt ^ 1], res |= (1 << i); 
        else p = ch[p][opt];
    }
    return res;
}

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

int main() {
    n = read(), tot = 1;
    for (int i = 1, u, v, d; i < n; ++ i) {
        u = read(), v = read(), d = read();
        addEdge(u, v, d), addEdge(v, u, d);
    }
    dfs(1, 0); int mx = 0;
    for (int i = 1; i <= n; ++ i) insert(f[i]);
    for (int i = 1; i <= n; ++ i) mx = std::max(mx, query(f[i]));
    printf("%d\n", mx);
    return 0;
}
最后修改:2021 年 09 月 07 日
如果觉得我的文章对你有用,请随意赞赏