• 分析

    1. 根据题目可以看出这是一棵典型的01字典树，要求树上路径的异或最大值，n<=1e5。我们不可能O(n^2)扫过，我们画个图分析一下:

      图片说明

      当我们要求3与4之间的异或路径，第一个方法是倍增，但会超时。但是如果我们记录一个dis[i]表示i->1路径上的异或权值，那么3,4之间的异或权值就是dis[ 3 ] ^ dis[ 4 ] = 6 ^ 5 ^ 5 ^ 7,最近公共祖先的上面部分相当于被抵消了。

  1. 直接枚举每个点，在字典树上跑，求出答案。我们从高到低存入每一位的值，根据我们的贪心策略以及异或的性质，只要当前位数为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);
}