做该题之前，至少要先会做这道题。
记 \(d[u]\) 表示 \(1\) 到 \(u\) 简单路径的异或和，该数组可以通过一次遍历求得。
\(~\)
考虑 \(u\) 到 \(v\) 简单路径的异或和该怎么求？
令 \(z=\operatorname{lca}(u,v)\) ，则 \(u\) 到 \(v\) 简单路径的异或和可以分成两段求解：一段是 \(z\) 到 \(u\) 简单路径的异或和，一段是 \(z\) 到 \(v\) 简单路径的异或和，二者异或一下即为 \(u\) 到 \(v\) 简单路径的异或和。
由于异或 "\(a \operatorname{xor} a=0\)" 的性质，两条路径重叠的部分异或起来即为 \(0\)，可得
\(z\) 到 \(v\) 简单路径的异或和为
\[d[u] \operatorname{xor} d[z]
\]
\]
\(z\) 到 \(v\) 简单路径的异或和为
\[d[v] \operatorname{xor} d[z]
\]
\]
进一步，可得
\(u\) 到 \(v\) 简单路径的异或和为
\[(d[u]\operatorname{xor}d[z])\operatorname{xor}(d[v]\operatorname{xor}d[z])
\]
\]
由于异或满足交换律，可化简为
\[d[u]\operatorname{xor}d[v]
\]
\]
由上述性质，答案即为 \(\max\limits_{1\leq i<j\leq n}\)\(\{d[i] \operatorname{xor} d[j]\}\)，又回到了这道题，字典树直接解决即可。
时间复杂度 \(\theta(32n)\) 。
CODE
#include<cstdio>
#include<algorithm>
#include<queue>
#define RI register int
using namespace std;
inline int read()
{
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}
while(s>='0'&&s<='9'){x=x*10-'0'+s;s=getchar();}
return x*f;
}
const int N=100100,M=200100;
int n;
int tot_E,head[N],ver[M],edge[M],Next[M];
void add(int u,int v,int w)
{
ver[++tot_E]=v; edge[tot_E]=w; Next[tot_E]=head[u]; head[u]=tot_E;
}
int d[N];
int vis[N];
void bfs()
{
queue<int>q;
q.push(1);vis[1]=1;
while(q.size())
{
int u=q.front();q.pop();
for(RI i=head[u];i;i=Next[i])
{
int v=ver[i],w=edge[i];
if(vis[v])continue;
vis[v]=1;
d[v]=d[u]^w;
q.push(v);
}
}
}
int trie[N*32+10][2],tot=1;
int ans;
void insert(int num)
{
int p=1;
for(RI k=31;k>=0;k--)
{
int ch=num>>k&1;
if(trie[p][ch]==0)trie[p][ch]=++tot;
p=trie[p][ch];
}
}
int search(int num)
{
int p=1,sum=0;
for(RI k=31;k>=0;k--)
{
int ch=num>>k&1;
if(trie[p][ch^1])p=trie[p][ch^1],sum+=1<<k;
else p=trie[p][ch];
if(p==0)return sum;
}
return sum;
}
int main()
{
scanf("%d",&n);
for(RI i=1;i<n;i++)
{
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
bfs();
for(RI i=1;i<=n;i++)
{
ans=max(ans,search(d[i]));
insert(d[i]);
}
printf("%d\n",ans);
return 0;
}