poj 3764(Trie维护二进制数+Xor)

发表于 | 分类于 | | + s

poj 3764
题意：给定一棵$n$个点的带权无向树，求树上路径异或和的最大值。

利用 Xor 性质，我们发现路径异或和满足容斥 (即$[l,r]$可由$[1,r]，[1, l-1]$得出)
那么我们求根到每个点的异或和$d_i$，然后尝试如何异或出一条路径来
我们发现任意两个$d_i,d_j$的异或和为某条路径的异或和，且不漏解
那么问题转化为求序列$d_i$两两异或最大值。
因为 Xor 常用 Trie 维护，所以我们可以运用 Trie 求这个最大值。将所有$d_i$以二进制形式插入 Trie (高位在上，定一个最大位数，不够在前面补0)，边权为二进制位，然后对于每个二进制下的$d_i$在Trie树上走尽量相反的边，因为这样保证异或后大。树上没有最优边那就只能走另一条边。这样下来的路径就是$d_i$与其他$d_j$的最大异或值。$O(n \cdot len)$操作即可，$len$为二进制最大位数。

1、Trie 维护二进制 Xor
2、路径 - 用根分路径 (答案可以容斥) - 求根到每个点的信息 (类比 LCA 的距离数组)

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5, ML = 50;

    struct edge {
        int v, w, nxt;
    }ed[MAXN * 2];

    int n, hd[MAXN], en, sz, ch[MAXN * 55][2], arr[55];
    LL d[MAXN], ans;

    void ins(int u, int v, int w) {ed[++en] = (edge){v, w, hd[u]}, hd[u] = en;}

    void dfs(int u, int fa) {
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) d[e.v] = d[u] ^ e.w, dfs(e.v, u);
        }
    }
    void ins() {
        int now = 0;
        for (int i = 1; i <= ML; ++i) {
            int c = arr[i];
            if (!ch[now][c]) ch[now][c] = ++sz;
            now = ch[now][c];
        }
    }
    LL chk() {
        LL ret = 0;
        int now = 0;
        for (int i = 1; i <= ML; ++i) {
            int c = arr[i] ^ 1;
            if (ch[now][c]) ret += (1ll << (LL)(ML - i + 1ll - 1ll)), now = ch[now][c];
            else now = ch[now][c ^ 1];
        }
        return ret;
    }

    void clean() {
        ms(hd, -1), en = 0;
        ans = sz = 0, ms(ch, 0);
    }
    int solve() {
        clean();
        for (int u, v, w, i = 1; i < n; ++i) scanf("%d%d%d", &u, &v, &w), ++u, ++v, ins(u, v, w), ins(v, u, w);
        d[0] = 0, dfs(1, 0);
        //                                                for (int i = 1; i <= n; ++i) cerr << d[i] << endl;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= ML; ++j) {
                int gg = ML - j + 1;
                arr[j] = (bool)((LL)(1ll << (gg - 1ll)) & d[i]);
            }
            //                                                                for (int j = 1; j <= ML; ++j) cerr << arr[j]; cerr << endl;
            ins();
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= ML; ++j) {
                int gg = ML - j + 1;
                arr[j] = (bool)((LL)(1ll << (gg - 1ll)) & d[i]);
            }
            ans = max(ans, chk());
        }
        printf("%lld\n", ans);
        return 0;
    }
}
int main() {
    while (scanf("%d", &flyinthesky::n) == 1) flyinthesky::solve();
    return 0;
}
------ 本文结束 ------