poj3764题解

题意

给定一个n个结点的树，树上每条边都有一个权值。从树中选择两个点 x 和y，把从x到y的路径上的所有边权值xor起来，得到的结果最大是多少？注意结点编号从0开始

问题转换

我们可以发现如果一条路径被异或了两次，是相当于没有异或的
也就是说树上任意一条路径的异或值都可以转化为经过根的两条路径的异或值（也就是将其LCA与根连一条边）
于是乎，我们从根做一遍dfs后，问题就变成了这样：
给定n个数，从中取两个数的异或和为多大
我们考虑对于一个数，异或什么数最大？
显然是对2^31-1取反，显然这是不可能的，是会有冲突的
所以我们可以用贪心的思想解决这个问题
我们可以发现2^n满足2^n>2^0+2^1…+2^(n-1)
所以说我们优先考虑当前最高位存不存在一个可以取反的数字即可
不可以就往下走，我们发现这个问题可以用字典树解决，于是乎，建立一颗01字典树
插入n个数
每次查询只要查询32位即可

代码

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

using namespace std;

typedef long long ll;
const ll INF=1e12;
const int MAXN=4e6+5;
int n,m,tot,ans;
int trie[MAXN][2];
int cnt[MAXN];
void iinsert(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 isearch(int x)
{
    int p=0,ans=0;
    for(int i=31;i>=0;i--){
        int c=(x>>i)&1,o=c^1;
        if(trie[p][o])
            p=trie[p][o],ans=ans<<1|1;
        else
            p=trie[p][c],ans<<=1;
    }
    return ans;
}

int main()
{
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        ans=max(ans,isearch(x));
        iinsert(x);
    }
    printf("%d\n",ans);
    return 0;
}