The XOR Largest Pair

题目：在给定的N个整数中选出2个进行^运算，得到结果最大的是多少？

思路

• 将N个正数按照二进制位（从高位到低位）存到字典树中，求^ 的最大值，意思是每一位都尽量走反方向的，本来该位为0，树中有1就走1，没有则继续走0，这样求得的结果一定是最接近^的最大值，
• 可以变插入变询问^的最大值，然后更新ans,因为两两相互查询，前面的插入的数没有和后面的数比，但是后面的数会和前面所以插入的数相比较,

#include <iostream>
using namespace std;
const int maxn=1e5+10;//maxn是所有数的二进制位的总长度
//如果你知道trie的数组第一维的大小的含义，你就能只能maxn的意义
int trie[maxn*32][2];//每一步是一位二进制 1,0
int tot = 0;
void insertn(int num){
    int p=0,ch;
    for (int i=30;i>=0;i--) {
        ch = (num>>i) & 1;//从二进制高位开始建树
        if (!trie[p][ch]) trie[p][ch]=++tot;
        p = trie[p][ch];
    }
}
int query(int num){
    int p=0;
    int ans = 0;
    for (int i=30;i>=0;i--) {
        int ch = (num>>i) & 1;//取出第i位
        if ( trie[p][!ch] ) {//如果第i位存在相反的,就可以走,
        //与第i为相反的这一位存在，该位^的最大值存在，则^=1
            ans += (1<<i);//更新^的最大值
            p = trie[p][!ch];
        } else p = trie[p][ch];
    }
    return  ans;
}
int main() {
//    freopen("a.txt","r",stdin);
    int n;
    scanf("%d",&n);
    int ans = 0;
    for (int i=0;i<n;i++) {
        int temp;
        scanf("%d",&temp);
        insertn(temp);
        ans = max(query(temp),ans);
    }
    printf("%d",ans);
    return 0;
}

The XOR Longest Path

• d[x]表示从根节点到x的路径上边权的^和，d[cur]=d[father(cur)]^weight[father(cur),cur];
• 找出d[i]^d[j]中最大的,重叠的部分^后=0,抵消掉了
• 通过dfs找出d[i]，注意该图，是无向图，没有给出根节点，dfs随便找一个点作为根节点就行，

  #include <iostream>
  #include <vector>
  using namespace std;
  const int maxn =1e5+10;
   
  int a[maxn];
  bool vis[maxn];
  vector<pair<int,int> > num[maxn];
  int trie[maxn*32][2];
  int tot = 0;
  int dfs(int cur,int sum) {
      a[cur] = sum;//a[cur]代表从根节点到该点的^和
      for (int i=0;i<num[cur].size();i++) {
          int v=num[cur][i].first;
          int w=num[cur][i].second;
          if ( !vis[v] ) {//不走重复
              vis[v] = true;//标记
              dfs(v,sum^w);
          }
      }
      return 0;
  }
  void insertn(int num) {
      int p=0;
      for (int i=30;i>=0;i--) {
          int ch = (num>>i) & 1;//从二进制的最高位开始建树
          if ( !trie[p][ch] ) trie[p][ch] = ++tot;
          p = trie[p][ch];
      }
      return ;
  }
  int query(int num) {
      int p=0,ans =0;
      for (int i=30;i>=0;i--) {
          int ch = (num>>i) & 1;
          if ( trie[p][!ch] ) {
              ans += (1<<i);
              p = trie[p][!ch];
          } else p = trie[p][ch]; //该二进制位没有相反的，所以继续有需要查询的数
      }
      return ans;
  }
  int main() {
  //    freopen("a.txt","r",stdin);
      int n;
      scanf("%d",&n);
      for (int i=0;i<n-1;i++) {
          int a,b,c;
          scanf("%d%d%d",&a,&b,&c);
          num[a].push_back({b,c});//邻接表vector存储
          //md 原来是无向图，源点并不是0，真tm蠢
          num[b].push_back({a,c});
      }
      vis[0] = true;//无向图 非常容易忘记book第一个点，导致重复走
      dfs(0,0);//从0开始dfs,那么0被我们认为是根节点
   
      //开始建trie树
      //边建trie树，然后查询最大值
      int ans =0;
      for (int i=0;i<n;i++) insertn(a[i]);
      for (int i=0;i<n;i++) ans = max(ans,query(a[i]));
      printf("%d",ans);
      return 0;
  }