The XOR-longest Path

直接枚举每个点，在字典树上跑，求出答案。我们从高到低存入每一位的值，根据我们的贪心策略以及异或的性质，只要当前位数为c，在当前层数中存在一个权值为(bool)(c^1)的节点,那么答案就要加上(1<<i)。

• 代码

  #include<cstdio>
  #include<iostream>
  #include<cstring>
  #include<algorithm>
  #define R register
  #define ll long long
  #define inf INT_MAX
  using namespace std;
  const int N=1e5+10;
  int n,tot,cnt;
  int h[N],nex[N],ver[N],pri[N],dis[N],tr[2][N*30];
  inline void add(int x,int y,int z)
  {
  nex[tot]=h[x];
  ver[tot]=y;
  pri[tot]=z;
  h[x]=tot++;
  }
  inline void dfs(int u,int v)
  {
  for (int i=h[u];~i;i=nex[i])
  {
   int j=ver[i];
   if(j==v) continue;
  
   dis[j]=dis[u]^pri[i];
   dfs(j,u);
  }//求出从根节点到当前节点的异或权值
  }
  inline void insert(int s)
  {
  int rt=0;
  for (int i=30;i>=0;i--)
  {//从最高位开始贪 
   bool c=((s>>i)&1);
   if(!tr[c][rt]) tr[c][rt]=++cnt;
   rt=tr[c][rt];
  }
  }
  inline int ask(int x)
  {
  int ans=0,rt=0;
  for (int i=30;i>=0;i--)
  {
   bool c=((x>>i)&1);
   if(tr[c^1][rt]) ans+=(1<<i),rt=tr[c^1][rt];
   else rt=tr[c][rt];
  }//建立一棵字典树
  return ans;
  }
  int main()
  {
  memset(h,-1,sizeof(h));
  scanf("%d",&n);
  for (int i=1;i<n;i++)
  {
   int x,y,z;
   scanf("%d%d%d",&x,&y,&z);
   add(x,y,z),add(y,x,z);
  }
  dfs(1,0);
  for (int i=1;i<=n;i++) insert(dis[i]);
  int ans=0;
  for (int i=1;i<=n;i++) ans=max(ans,ask(dis[i]));
  //对于每一条路径，我们都可以找出与他异或的最大值
  printf("%d\n",ans);
  }